C語(yǔ)言實(shí)現(xiàn)手寫Map(全功能)的示例代碼

更新時(shí)間：2022年08月25日 14:18:03 作者：胡安民

這篇文章主要為大家詳細(xì)介紹了如何利用C語(yǔ)言實(shí)現(xiàn)手寫Map(全功能)，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C語(yǔ)言有一定幫助，需要的可以參考一下

為啥需要Map結(jié)構(gòu)

假設(shè)，數(shù)據(jù)很少，十個(gè)指頭就能數(shù)過(guò)來(lái)，就不需要數(shù)據(jù)結(jié)構(gòu)了。隨便存就行了。既然數(shù)據(jù)多的問(wèn)題不可避免，數(shù)據(jù)多了怎么存儲(chǔ)。最簡(jiǎn)單的就是把一個(gè)一個(gè)的數(shù)據(jù)排成一排。這就是數(shù)組。數(shù)組這種結(jié)構(gòu)，又稱為列表List。數(shù)組是最簡(jiǎn)單和直觀的數(shù)據(jù)結(jié)構(gòu)。數(shù)組的容量很大，排列緊密，最節(jié)省空間，但數(shù)組的缺點(diǎn)是查找困難。假設(shè)你把100個(gè)個(gè)人信息放在一個(gè)列表里，當(dāng)需要用到某個(gè)人的時(shí)候，就會(huì)出現(xiàn)“只在此山中，云深不知處”的問(wèn)題。不知道第幾個(gè)才是你需要的，所以需要從頭開(kāi)始一個(gè)一個(gè)的檢查，直到找到了你需要的那個(gè)人。這個(gè)查找花費(fèi)的時(shí)間長(zhǎng)度是和人數(shù)成正比的。運(yùn)氣最不好的時(shí)候，可能找到最后一個(gè)人，才找到了你需要的那個(gè)人。你看這個(gè)查找多慢呀。列表中的總量越多，你的查找時(shí)間就可能越長(zhǎng)。如果一百萬(wàn)，一千萬(wàn)，甚至更多，可能就根本查不出來(lái)了。因?yàn)闀r(shí)間太久了。所以這里需要解決這個(gè)查找難慢的問(wèn)題。

我們分析一下為什么會(huì)出現(xiàn)查找難的問(wèn)題，是因?yàn)樵诖嫘畔⒌臅r(shí)候，根本就沒(méi)有考慮未來(lái)有一天我查的時(shí)候，怎么能夠方便一點(diǎn)。因?yàn)闆](méi)有瞻前顧后，導(dǎo)致查找時(shí)的困難。所以，這次我們存儲(chǔ)的時(shí)候，就要想好了，怎么能夠快速查出來(lái)。首先確定一個(gè)問(wèn)題，將來(lái)要用什么信息去作匹配。這個(gè)信息一定要具備唯一性。比如說(shuō)查尋人的信息，身份證id就是一個(gè)唯一性的信息，因?yàn)槊總€(gè)人的身份證號(hào)碼都不一樣。比方說(shuō)有100個(gè) 個(gè)人信息，將來(lái)我們要用他們的身份證號(hào)去查詢。所以存儲(chǔ)的時(shí)候，不應(yīng)該一股腦的放進(jìn)一個(gè)列表中，這樣不方便查，如果把這100個(gè)信息放入列表的位置和他們的身份證號(hào)有一個(gè)關(guān)系。這樣當(dāng)要用身份證號(hào)查詢時(shí)，就能更快的知道存在什么地方了。

還有一個(gè)問(wèn)題是，時(shí)間和空間。我們的理想是查詢時(shí)間最快和用最小的空間。但是實(shí)踐中發(fā)現(xiàn) 魚(yú)和熊掌不可兼得。不可能使用的空間最小，還能查的又最快。只能浪費(fèi)一些空間，去獲得更快的查詢體驗(yàn)，或者使用最少的空間，但是查詢慢。就像100個(gè)信息，如果只給100個(gè)空間的話，正好能裝滿，一點(diǎn)空間都不浪費(fèi)，但是查詢時(shí)間就慢了。但是往往是空間比較便宜，而時(shí)間比較寶貴。如果說(shuō)現(xiàn)在愿意拿出5倍的空間來(lái)存儲(chǔ)數(shù)據(jù)，如何能夠讓查詢的時(shí)間更快一些呢？

現(xiàn)在將100個(gè)信息，存儲(chǔ)在500個(gè)空間里。我們的目標(biāo)是，在將數(shù)據(jù)存入500個(gè)空間時(shí)，不再順序放了，因?yàn)檫@樣找的話，就需要一個(gè)一個(gè)挨著看。每個(gè)信息都有一個(gè)唯一的信息，如身份證id，如果有一個(gè)函數(shù)，輸入是身份證號(hào)，輸出是存儲(chǔ)位置的索引。那么，在存入時(shí)，我們先用這個(gè)函數(shù)，算出存儲(chǔ)的位置索引，并存入，當(dāng)需要取時(shí)，只需要將身份號(hào) 放到這個(gè)函數(shù)中，就可以算出是在哪兒存的索引，直接去取就可以了。這樣查找時(shí)間就是1次就找到了，只需要花費(fèi)計(jì)劃索引的時(shí)間就可以了，這個(gè)函數(shù)叫哈希函數(shù)Hash。哈希的過(guò)程是一個(gè)映射關(guān)系的計(jì)算。

就拿上面的例子來(lái)說(shuō)，我們知道有100個(gè)元素要存儲(chǔ)，并且準(zhǔn)備了500個(gè)空間。也就意味著，哈希函數(shù)計(jì)算出來(lái)的值必須要在 0-499 之間。但是輸入是一個(gè)18位的身份證號(hào)。18位數(shù)字的所有可能的組合要遠(yuǎn)大于500個(gè)。就可能出現(xiàn)碰撞的問(wèn)題。也就是兩個(gè)不同的初始值，經(jīng)過(guò)哈希函數(shù)后，算出來(lái)的值是一樣的。碰撞是不可避免的，但是好的哈希函數(shù)是能夠?qū)⑴鲎部刂频揭粋€(gè) 非常小的比例。這也取決與元素的個(gè)數(shù) 和總的空間的比例。顯然，空間越大，碰撞的問(wèn)題就會(huì)越少，但是浪費(fèi)的空間就越多。這又是一個(gè) 魚(yú)和熊掌的問(wèn)題。

最后設(shè)計(jì)出來(lái)的Map可以實(shí)現(xiàn)無(wú)論多少數(shù)據(jù)都能基本上完成 O(1) 復(fù)雜度的查找效率?？植腊?這也是每門高級(jí)語(yǔ)言必備的數(shù)據(jù)結(jié)構(gòu),但是在C語(yǔ)言中沒(méi)有,需要我們自己設(shè)計(jì)

主流Map結(jié)構(gòu)

上圖的數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單就是數(shù)組的每個(gè)節(jié)點(diǎn)都是鏈表頭,當(dāng)有hash沖突或者取模相同的時(shí)候就會(huì)進(jìn)行鏈表的掛載

上圖的數(shù)據(jù)結(jié)構(gòu)就比較復(fù)雜了,數(shù)組+鏈表+紅黑樹(shù), 分為2個(gè)等級(jí), 鏈表長(zhǎng)度達(dá)到 8 就轉(zhuǎn)成紅黑樹(shù)，而當(dāng)長(zhǎng)度降到 6 就轉(zhuǎn)換回去,這體現(xiàn)了時(shí)間和空間平衡的思想.

為啥是8按照泊松分布的計(jì)算公式計(jì)算出了桶中元素個(gè)數(shù)和概率的對(duì)照表，可以看到鏈表中元素個(gè)數(shù)為8時(shí)的概率已經(jīng)非常小，再多的就更少了，所以原作者在選擇鏈表元素個(gè)數(shù)時(shí)選擇了8，是根據(jù)概率統(tǒng)計(jì)而選擇的。

數(shù)組+鏈表的Map

結(jié)構(gòu)

typedef struct entry {
    char * key;             // 鍵
    void * value;           // 值
    struct entry * next;    // 沖突鏈表
} Entry;

typedef int boolean;//定義一個(gè)布爾類型
#define TRUE 1
#define FALSE 0
// 哈希表結(jié)構(gòu)體
typedef struct hashMap {
    int size;           // 集合元素個(gè)數(shù)
    int capacity;       // 容量
    int nodeLen;       //節(jié)點(diǎn)長(zhǎng)度
    Entry **list;         // 存儲(chǔ)區(qū)域
    int dilatationCount;  //擴(kuò)容次數(shù)
    int dilatationSum;  //擴(kuò)容總次數(shù)

} HashMap;

// 迭代器結(jié)構(gòu)
typedef struct hashMapIterator {
    Entry *nextEntry;// 迭代器當(dāng)前指向
    int count;//迭代次數(shù)
    HashMap *hashMap;
    int index; //位置
}HashMapIterator;

hash函數(shù)

//最好的char類型的hash算法,沖突較少,效率較高
static unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131;
    unsigned int hash = 0;

    while (*str)
    {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

//hash值長(zhǎng)度取模最后獲取實(shí)際位置的下標(biāo)
static  unsigned int defaultHashCode(HashMap hashMap, char * key){
    return BKDRHash(key)% hashMap.capacity;
}

創(chuàng)建Map集合

HashMap *createHashMap(int capacity) {
    //創(chuàng)建哈希表
    HashMap *hashMap= (HashMap *)malloc(sizeof(HashMap));
    //創(chuàng)建存儲(chǔ)區(qū)域
    if(capacity<10){
        capacity=10;
    }
    hashMap->size=0;
    hashMap->dilatationCount=0;
    hashMap->dilatationSum=0;
    hashMap->nodeLen=0;
    hashMap->capacity=capacity;
    hashMap->list = (Entry **)calloc(capacity,sizeof(Entry));
    return hashMap;
}

擴(kuò)容基數(shù)

//擴(kuò)容基數(shù)
static int  expansionBase( HashMap *hashMap){
    int len = hashMap->capacity;
    int dilatationCount= hashMap->dilatationCount;
    hashMap->dilatationSum++;
    //基礎(chǔ)擴(kuò)容
    len+= (len>=100000000?len*0.2:
          len>=50000000?len*0.3:
          len>=10000000?len*0.4:
          len>=5000000?len*0.5:
          len>=1000000?len*0.6:
          len>=500000?len*0.7:
          len>=100000?len*0.8:
          len>=50000?len*0.9:
          len*1.0);
    hashMap->dilatationCount++;
    //頻率擴(kuò)容
    if(dilatationCount>=5){
        len+= (len>=100000000?len*1:
              len>=50000000?len*2:
              len>=10000000?len*3:
              len>=5000000?len*4:
              len>=1000000?len*5:
              len>=500000?len*6:
              len>=100000?len*7:
              len>=50000?len*8:
              len>=10000?len*9:
              len>=1000?len*10:
              len*20);
        hashMap->dilatationCount=0;
    }

???????    return len;
}

擴(kuò)容Map集合

//擴(kuò)容Map集合
static  void dilatationHash(HashMap *hashMap){
    //原來(lái)的容量
    int capacity = hashMap->capacity;
    //擴(kuò)容后的容量
    hashMap->capacity=expansionBase(hashMap);
    //節(jié)點(diǎn)長(zhǎng)度清空
    hashMap->nodeLen=0;
    //創(chuàng)建新的存儲(chǔ)區(qū)域
    Entry **newList=(Entry **)calloc(hashMap->capacity,sizeof(Entry));
    //遍歷舊的存儲(chǔ)區(qū)域,將舊的存儲(chǔ)區(qū)域的數(shù)據(jù)拷貝到新的存儲(chǔ)區(qū)域
    for(int i=0;i<capacity;i++){
        Entry *entry=hashMap->list[i];
        if(entry!=NULL){
            //獲取新的存儲(chǔ)區(qū)域的下標(biāo)
            unsigned int newIndex=defaultHashCode(*hashMap,entry->key);
            if(newList[newIndex]==NULL){
                Entry *newEntry = (Entry *)malloc(sizeof(Entry));
                newEntry->key = entry->key;
                newEntry->value = entry->value;
                newEntry->next = NULL;
                newList[newIndex] = newEntry;
                hashMap->nodeLen++;
            }else{//那么就是沖突鏈表添加鏈表節(jié)點(diǎn)
                Entry *newEntry = (Entry *)malloc(sizeof(Entry));
                newEntry->key = entry->key;
                newEntry->value = entry->value;
                //將新節(jié)點(diǎn)插入到鏈表頭部(這樣的好處是插入快,但是不能保證插入的順序)
                newEntry->next = newList[newIndex];
                newList[newIndex] = newEntry;
            }
            //判斷節(jié)點(diǎn)內(nèi)鏈表是否為空
            if(entry->next!=NULL){
                //遍歷鏈表,將鏈表節(jié)點(diǎn)插入到新的存儲(chǔ)區(qū)域
                Entry *nextEntry=entry->next;
                while(nextEntry!=NULL){
                    //獲取新的存儲(chǔ)區(qū)域的下標(biāo)
                    unsigned int newIndex=defaultHashCode(*hashMap,nextEntry->key);
                    if(newList[newIndex]==NULL){
                        Entry *newEntry = (Entry *)malloc(sizeof(Entry));
                        newEntry->key = nextEntry->key;
                        newEntry->value = nextEntry->value;
                        newEntry->next = NULL;
                        newList[newIndex] = newEntry;
                        hashMap->nodeLen++;
                    }else{//那么就是沖突鏈表添加鏈表節(jié)點(diǎn)
                        Entry *newEntry = (Entry *)malloc(sizeof(Entry));
                        newEntry->key = nextEntry->key;
                        newEntry->value = nextEntry->value;
                        //將新節(jié)點(diǎn)插入到鏈表頭部(這樣的好處是插入快,但是不能保證插入的順序)
                        newEntry->next = newList[newIndex];
                        newList[newIndex] = newEntry;
                    }
                    nextEntry=nextEntry->next;
                }
            }
        }
    }
    //釋放舊的存儲(chǔ)區(qū)域
    free(hashMap->list);
    //將新的存儲(chǔ)區(qū)域賦值給舊的存儲(chǔ)區(qū)域
    hashMap->list=newList;
}

給Map集合添加元素

void putHashMap(HashMap *hashMap, char *key, void *value) {
    //判斷是否需要擴(kuò)容
    if(hashMap->nodeLen==hashMap->capacity){
        dilatationHash(hashMap);
    }
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];

    //如果節(jié)點(diǎn)是空的那么直接添加
    if(entry==NULL){
        Entry *newEntry = (Entry *)malloc(sizeof(Entry));
        newEntry->key = key;
        newEntry->value = value;
        newEntry->next = NULL;
        hashMap->list[hashCode] = newEntry;
        hashMap->size++;
        hashMap->nodeLen++;
        return;
    }

    //判斷是否存在該鍵,并且一樣的話,更新值
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        entry->value = value;
        return;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要添加到鏈表中
    //添加前需要先判斷鏈表中是否存在該鍵
    while (entry != NULL) {
        //如果存在該鍵,那么更新值
        if (strcmp(entry->key, key) == 0) {
            entry->value = value;
            return;
        }
        entry = entry->next;
    }
    //如果鏈表中不存在,那么就創(chuàng)建新的鏈表節(jié)點(diǎn)
    Entry *newEntry = (Entry *)malloc(sizeof(Entry));
    newEntry->key = key;
    newEntry->value = value;
    //將新節(jié)點(diǎn)插入到鏈表頭部(這樣的好處是插入快,但是不能保證插入的順序)
    newEntry->next = hashMap->list[hashCode];
    hashMap->list[hashCode] = newEntry;
    hashMap->size++;

}

打印Map集合

void printHashMap(HashMap *hashMap) {
    for (int i = 0; i < hashMap->capacity; i++) {
        Entry *entry = hashMap->list[i];
        while (entry != NULL) {
            printf("%s:%s\n", entry->key, entry->value);
            entry = entry->next;
        }
    }
}

獲取Map集合中的指定元素

void *getHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];
    //如果節(jié)點(diǎn)是空的那么直接返回
    if(entry==NULL){
        return NULL;
    }
    //判斷是否存在該鍵,并且一樣的話,返回值
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        return entry->value;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要查詢鏈表
    while (entry != NULL) {
        //如果找到該鍵,那么返回值
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    return NULL;
}

判斷鍵是否存在

boolean containsKey(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];
    //如果節(jié)點(diǎn)是空的那么直接返回FALSE
    if(entry==NULL){
        return FALSE;
    }
    //判斷是否存在該鍵,并且一樣的話,返回TRUE
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        return TRUE;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要查詢鏈表
    while (entry != NULL) {
        //如果找到該鍵,那么返回TRUE
        if (strcmp(entry->key, key) == 0) {
            return TRUE;
        }
        entry = entry->next;
    }
    return FALSE;
}

判斷值是否存在

//判斷值是否存在
boolean containsValue(HashMap *hashMap, void *value) {
    for (int i = 0; i < hashMap->capacity; i++) {
        Entry *entry = hashMap->list[i];//獲取節(jié)點(diǎn)
        while (entry != NULL) {
            if (entry->value == value) {//如果找到該值,那么返回TRUE
                return TRUE;
            }
            entry = entry->next;//否則查詢節(jié)點(diǎn)鏈表內(nèi)部
        }
    }
    return FALSE;
}

刪除Map集合中的指定元素

void removeHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];
    //如果節(jié)點(diǎn)是空的那么直接返回
    if(entry==NULL){
        return;
    }
    //判斷是否存在該鍵,并且一樣的話,刪除該節(jié)點(diǎn)
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        hashMap->list[hashCode] = entry->next;
        free(entry);
        hashMap->size--;
        return;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要查詢鏈表
    while (entry != NULL) {
        //如果找到該鍵,那么刪除該節(jié)點(diǎn)
        if (strcmp(entry->key, key) == 0) {
            Entry *next = entry->next;
            entry->next = next->next;
            free(next);
            hashMap->size--;
            return;
        }
        entry = entry->next;
    }
}

修改Map集合中的指定元素

void updateHashMap(HashMap *hashMap, char *key, void *value) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];
    //如果節(jié)點(diǎn)是空的那么直接返回
    if(entry==NULL){
        return;
    }
    //判斷是否存在該鍵,并且一樣的話,修改該節(jié)點(diǎn)的值
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        entry->value = value;
        return;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要查詢鏈表
    while (entry != NULL) {
        //如果找到該鍵,那么修改該節(jié)點(diǎn)的值
        if (strcmp(entry->key, key) == 0) {
            entry->value = value;
            return;
        }
        entry = entry->next;
    }
}

迭代器

HashMapIterator *createHashMapIterator(HashMap *hashMap){
    HashMapIterator *hashMapIterator= malloc(sizeof(HashMapIterator));;
    hashMapIterator->hashMap = hashMap;
    hashMapIterator->count= 0;//迭代次數(shù)
    hashMapIterator->index= 0;//迭代位置
    hashMapIterator->nextEntry= NULL;//下次迭代節(jié)點(diǎn)

    return hashMapIterator;
}
boolean hasNextHashMapIterator(HashMapIterator *iterator){
    return iterator->count < iterator->hashMap->size ? TRUE : FALSE;
}
Entry *nextHashMapIterator(HashMapIterator *iterator) {
    if (hasNextHashMapIterator(iterator)) {
        //如果節(jié)點(diǎn)中存在hash沖突鏈表那么就迭代鏈表
        if(iterator->nextEntry!=NULL){//如果下次迭代節(jié)點(diǎn)不為空,那么直接返回下次迭代節(jié)點(diǎn)
            Entry *entry = iterator->nextEntry;
            iterator->nextEntry = entry->next;
            iterator->count++;
            return entry;
        }

        Entry *pEntry1 = iterator->hashMap->list[iterator->index];
        //找到不是空的節(jié)點(diǎn)
        while (pEntry1==NULL){
            pEntry1 = iterator->hashMap->list[++iterator->index];
        }
        //如果沒(méi)有hash沖突節(jié)點(diǎn),那么下次迭代節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)向后繼續(xù)搜索
        if(pEntry1->next==NULL){
            Entry *pEntry2= iterator->hashMap->list[++iterator->index];
            while (pEntry2==NULL){
                pEntry2 = iterator->hashMap->list[++iterator->index];
            }
            iterator->nextEntry =pEntry2;
        }else{
            iterator->nextEntry = pEntry1->next;
        }
        iterator->count++;
        return pEntry1;
    }
    return  NULL;
}

獲取所有的key

需要借助我之前文件寫的List集合,有興趣的可以去看看

//獲取所有的key ,返回一個(gè)自定義的List集合
CharList *getKeys(HashMap *hashMap){

    CharList *pCharlist = createCharList(10);
    HashMapIterator *pIterator = createHashMapIterator(hashMap);
    while (hasNextHashMapIterator(pIterator)) {
        Entry *entry = nextHashMapIterator(pIterator);
        addCharList(&pCharlist,entry->key);
    }
    return pCharlist;
}

獲取所有的value

//獲取所有的value,返回一個(gè)自定義的List集合
CharList *getValues(HashMap *hashMap){
    CharList *pCharlist = createCharList(10);
    HashMapIterator *pIterator = createHashMapIterator(hashMap);
    while (hasNextHashMapIterator(pIterator)) {
        Entry *entry = nextHashMapIterator(pIterator);
        addCharList(&pCharlist,entry->value);
    }
    return pCharlist;
}

復(fù)制一個(gè)Map

HashMap *copyHashMap(HashMap *hashMap){
    HashMap *pHashMap = createHashMap(hashMap->capacity);
    HashMapIterator *pIterator = createHashMapIterator(hashMap);
    while (hasNextHashMapIterator(pIterator)) {
        Entry *entry = nextHashMapIterator(pIterator);
        putHashMap(pHashMap,entry->key,entry->value);
    }
    return pHashMap;
}

將一個(gè)map集合合并到另一個(gè)map集合里

//將一個(gè)map集合,合并到另一個(gè)map集合里   hashMap2合并到hashMap1
void mergeHashMap(HashMap *hashMap1,HashMap *hashMap2){
    HashMapIterator *pIterator = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator)) {
        Entry *entry = nextHashMapIterator(pIterator);
        putHashMap(hashMap1,entry->key,entry->value);
    }
}

合并兩個(gè)Map集合,返回一個(gè)新的Map集合

HashMap *mergeHashMapNewMap(HashMap *hashMap1,HashMap *hashMap2){
    HashMap *pHashMap = createHashMap(hashMap1->capacity+hashMap2->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        Entry *entry = nextHashMapIterator(pIterator1);
        putHashMap(pHashMap,entry->key,entry->value);
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        Entry *entry = nextHashMapIterator(pIterator2);
        putHashMap(pHashMap,entry->key,entry->value);
    }
    return pHashMap;
}

差集

//差集,返回一個(gè)新的Map集合,返回hashMap2的差集
HashMap *differenceHashMap(HashMap *hashMap1,HashMap *hashMap2){
    HashMap *pHashMap = createHashMap(hashMap1->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        Entry *entry = nextHashMapIterator(pIterator1);
        if(!containsKey(hashMap2,entry->key)){
            putHashMap(pHashMap,entry->key,entry->value);
        }
    }
    return pHashMap;
}

交集

//交集,返回一個(gè)新的Map集合
HashMap *intersectionHashMap(HashMap *hashMap1,HashMap *hashMap2){
    HashMap *pHashMap = createHashMap(hashMap1->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        Entry *entry = nextHashMapIterator(pIterator1);
        if(containsKey(hashMap2,entry->key)){
            putHashMap(pHashMap,entry->key,entry->value);
        }
    }
    return pHashMap;
}

補(bǔ)集

//補(bǔ)集,返回一個(gè)新的Map集合
HashMap *complementHashMap(HashMap *hashMap1,HashMap *hashMap2){
    HashMap *pHashMap = createHashMap(hashMap1->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        Entry *entry = nextHashMapIterator(pIterator1);
        if(!containsKey(hashMap2,entry->key)){
            putHashMap(pHashMap,entry->key,entry->value);
        }
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        Entry *entry = nextHashMapIterator(pIterator2);
        if(!containsKey(hashMap1,entry->key)){
            putHashMap(pHashMap,entry->key,entry->value);
        }
    }
    return pHashMap;
}

并集

HashMap *unionHashMap(HashMap *hashMap1,HashMap *hashMap2){
    HashMap *pHashMap = createHashMap(hashMap1->capacity+hashMap2->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        Entry *entry = nextHashMapIterator(pIterator1);
        putHashMap(pHashMap,entry->key,entry->value);
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        Entry *entry = nextHashMapIterator(pIterator2);
        putHashMap(pHashMap,entry->key,entry->value);
    }
    return pHashMap;
}

清除Map

void hashMapClear(HashMap *hashMap){
    for (int i = 0; i < hashMap->nodeLen; i++) {
        // 釋放沖突值內(nèi)存
        Entry *entry = hashMap->list[i];
        if(entry!=NULL){
            Entry *nextEntry = entry->next;
            while (nextEntry != NULL) {
                Entry *next = nextEntry->next;
                free(nextEntry);
                nextEntry = next;
            }
            free(entry);
        }
    }
    // 釋放存儲(chǔ)空間
    free(hashMap->list);
    free(hashMap);
}

到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)手寫Map(全功能)的示例代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言 Map內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: