C語言實現手寫Map(全功能)的範例程式碼

2022-08-25 18:03:24

為啥需要Map結構

假設，資料很少，十個指頭就能數過來，就不需要資料結構了。隨便存就行了。既然資料多的問題不可避免，資料多了怎麼儲存。最簡單的就是把一個一個的資料排成一排。這就是陣列。陣列這種結構，又稱為列表List。陣列是最簡單和直觀的資料結構。陣列的容量很大，排列緊密，最節省空間，但陣列的缺點是查詢困難。假設你把100個個人資訊放在一個列表裡，當需要用到某個人的時候，就會出現“只在此山中，雲深不知處”的問題。不知道第幾個才是你需要的，所以需要從頭開始一個一個的檢查，直到找到了你需要的那個人。這個查詢花費的時間長度是和人數成正比的。運氣最不好的時候，可能找到最後一個人，才找到了你需要的那個人。你看這個查詢多慢呀。列表中的總量越多，你的查詢時間就可能越長。如果一百萬，一千萬，甚至更多，可能就根本查不出來了。因為時間太久了。所以這裡需要解決這個查詢難慢的問題。

我們分析一下為什麼會出現查詢難的問題，是因為在存資訊的時候，根本就沒有考慮未來有一天我查的時候，怎麼能夠方便一點。因為沒有瞻前顧後，導致查詢時的困難。所以，這次我們儲存的時候，就要想好了，怎麼能夠快速查出來。首先確定一個問題，將來要用什麼資訊去作匹配。這個資訊一定要具備唯一性。比如說查尋人的資訊，身份證id就是一個唯一性的資訊，因為每個人的身份證號碼都不一樣。比方說有100個個人資訊，將來我們要用他們的身份證號去查詢。所以儲存的時候，不應該一股腦的放進一個列表中，這樣不方便查，如果把這100個資訊放入列表的位置和他們的身份證號有一個關係。這樣當要用身份證號查詢時，就能更快的知道存在什麼地方了。

還有一個問題是，時間和空間。我們的理想是查詢時間最快和用最小的空間。但是實踐中發現魚和熊掌不可兼得。不可能使用的空間最小，還能查的又最快。只能浪費一些空間，去獲得更快的查詢體驗，或者使用最少的空間，但是查詢慢。就像100個資訊，如果只給100個空間的話，正好能裝滿，一點空間都不浪費，但是查詢時間就慢了。但是往往是空間比較便宜，而時間比較寶貴。如果說現在願意拿出5倍的空間來儲存資料，如何能夠讓查詢的時間更快一些呢？

現在將100個資訊，儲存在500個空間裡。我們的目標是，在將資料存入500個空間時，不再順序放了，因為這樣找的話，就需要一個一個挨著看。每個資訊都有一個唯一的資訊，如身份證id，如果有一個函數，輸入是身份證號，輸出是儲存位置的索引。那麼，在存入時，我們先用這個函數，算出儲存的位置索引，並存入，當需要取時，只需要將身份號放到這個函數中，就可以算出是在哪兒存的索引，直接去取就可以了。這樣查詢時間就是1次就找到了，只需要花費計劃索引的時間就可以了，這個函數叫雜湊函數Hash。雜湊的過程是一個對映關係的計算。

就拿上面的例子來說，我們知道有100個元素要儲存，並且準備了500個空間。也就意味著，雜湊函數計算出來的值必須要在 0-499 之間。但是輸入是一個18位元的身份證號。18位元數位的所有可能的組合要遠大於500個。就可能出現碰撞的問題。也就是兩個不同的初始值，經過雜湊函數後，算出來的值是一樣的。碰撞是不可避免的，但是好的雜湊函數是能夠將碰撞控制到一個非常小的比例。這也取決與元素的個數和總的空間的比例。顯然，空間越大，碰撞的問題就會越少，但是浪費的空間就越多。這又是一個魚和熊掌的問題。

最後設計出來的Map可以實現無論多少資料都能基本上完成 O(1) 複雜度的查詢效率。恐怖把,這也是每門高階語言必備的資料結構,但是在C語言中沒有,需要我們自己設計

主流Map結構

上圖的資料結構比較簡單就是陣列的每個節點都是連結串列頭,當有hash衝突或者取模相同的時候就會進行連結串列的掛載

上圖的資料結構就比較複雜了,陣列+連結串列+紅黑樹, 分為2個等級, 連結串列長度達到 8 就轉成紅黑樹，而當長度降到 6 就轉換回去,這體現了時間和空間平衡的思想.

為啥是8按照泊松分佈的計算公式計算出了桶中元素個數和概率的對照表，可以看到連結串列中元素個數為8時的概率已經非常小，再多的就更少了，所以原作者在選擇連結串列元素個數時選擇了8，是根據概率統計而選擇的。

陣列+連結串列的Map

結構

typedef struct entry {
    char * key;             // 鍵
    void * value;           // 值
    struct entry * next;    // 衝突連結串列
} Entry;

typedef int boolean;//定義一個布林型別
#define TRUE 1
#define FALSE 0
// 雜湊表結構體
typedef struct hashMap {
    int size;           // 集合元素個數
    int capacity;       // 容量
    int nodeLen;       //節點長度
    Entry **list;         // 儲存區域
    int dilatationCount;  //擴容次數
    int dilatationSum;  //擴容總次數

} HashMap;

// 迭代器結構
typedef struct hashMapIterator {
    Entry *nextEntry;// 迭代器當前指向
    int count;//迭代次數
    HashMap *hashMap;
    int index; //位置
}HashMapIterator;

hash函數

//最好的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值長度取模最後獲取實際位置的下標
static  unsigned int defaultHashCode(HashMap hashMap, char * key){
    return BKDRHash(key)% hashMap.capacity;
}

建立Map集合

HashMap *createHashMap(int capacity) {
    //建立雜湊表
    HashMap *hashMap= (HashMap *)malloc(sizeof(HashMap));
    //建立儲存區域
    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;
}

擴容基數

//擴容基數
static int  expansionBase( HashMap *hashMap){
    int len = hashMap->capacity;
    int dilatationCount= hashMap->dilatationCount;
    hashMap->dilatationSum++;
    //基礎擴容
    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++;
    //頻率擴容
    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;
}

擴容Map集合

//擴容Map集合
static  void dilatationHash(HashMap *hashMap){
    //原來的容量
    int capacity = hashMap->capacity;
    //擴容後的容量
    hashMap->capacity=expansionBase(hashMap);
    //節點長度清空
    hashMap->nodeLen=0;
    //建立新的儲存區域
    Entry **newList=(Entry **)calloc(hashMap->capacity,sizeof(Entry));
    //遍歷舊的儲存區域,將舊的儲存區域的資料拷貝到新的儲存區域
    for(int i=0;i<capacity;i++){
        Entry *entry=hashMap->list[i];
        if(entry!=NULL){
            //獲取新的儲存區域的下標
            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{//那麼就是衝突連結串列新增連結串列節點
                Entry *newEntry = (Entry *)malloc(sizeof(Entry));
                newEntry->key = entry->key;
                newEntry->value = entry->value;
                //將新節點插入到連結串列頭部(這樣的好處是插入快,但是不能保證插入的順序)
                newEntry->next = newList[newIndex];
                newList[newIndex] = newEntry;
            }
            //判斷節點內連表是否為空
            if(entry->next!=NULL){
                //遍歷連結串列,將連結串列節點插入到新的儲存區域
                Entry *nextEntry=entry->next;
                while(nextEntry!=NULL){
                    //獲取新的儲存區域的下標
                    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{//那麼就是衝突連結串列新增連結串列節點
                        Entry *newEntry = (Entry *)malloc(sizeof(Entry));
                        newEntry->key = nextEntry->key;
                        newEntry->value = nextEntry->value;
                        //將新節點插入到連結串列頭部(這樣的好處是插入快,但是不能保證插入的順序)
                        newEntry->next = newList[newIndex];
                        newList[newIndex] = newEntry;
                    }
                    nextEntry=nextEntry->next;
                }
            }
        }
    }
    //釋放舊的儲存區域
    free(hashMap->list);
    //將新的儲存區域賦值給舊的儲存區域
    hashMap->list=newList;
}

給Map集合新增元素

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

    //如果節點是空的那麼直接新增
    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;
    }
    // 當前節點不為空,而且key不一樣,那麼表示hash衝突了,需要新增到連結串列中
    //新增前需要先判斷連結串列中是否存在該鍵
    while (entry != NULL) {
        //如果存在該鍵,那麼更新值
        if (strcmp(entry->key, key) == 0) {
            entry->value = value;
            return;
        }
        entry = entry->next;
    }
    //如果連結串列中不存在,那麼就建立新的連結串列節點
    Entry *newEntry = (Entry *)malloc(sizeof(Entry));
    newEntry->key = key;
    newEntry->value = value;
    //將新節點插入到連結串列頭部(這樣的好處是插入快,但是不能保證插入的順序)
    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:%sn", entry->key, entry->value);
            entry = entry->next;
        }
    }
}

獲取Map集合中的指定元素

void *getHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節點
    Entry *entry = hashMap->list[hashCode];
    //如果節點是空的那麼直接返回
    if(entry==NULL){
        return NULL;
    }
    //判斷是否存在該鍵,並且一樣的話,返回值
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        return entry->value;
    }
    // 當前節點不為空,而且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);
    //獲取節點
    Entry *entry = hashMap->list[hashCode];
    //如果節點是空的那麼直接返回FALSE
    if(entry==NULL){
        return FALSE;
    }
    //判斷是否存在該鍵,並且一樣的話,返回TRUE
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        return TRUE;
    }
    // 當前節點不為空,而且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];//獲取節點
        while (entry != NULL) {
            if (entry->value == value) {//如果找到該值,那麼返回TRUE
                return TRUE;
            }
            entry = entry->next;//否則查詢節點連結串列內部
        }
    }
    return FALSE;
}

刪除Map集合中的指定元素

void removeHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節點
    Entry *entry = hashMap->list[hashCode];
    //如果節點是空的那麼直接返回
    if(entry==NULL){
        return;
    }
    //判斷是否存在該鍵,並且一樣的話,刪除該節點
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        hashMap->list[hashCode] = entry->next;
        free(entry);
        hashMap->size--;
        return;
    }
    // 當前節點不為空,而且key不一樣,那麼表示hash衝突了,需要查詢連結串列
    while (entry != NULL) {
        //如果找到該鍵,那麼刪除該節點
        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);
    //獲取節點
    Entry *entry = hashMap->list[hashCode];
    //如果節點是空的那麼直接返回
    if(entry==NULL){
        return;
    }
    //判斷是否存在該鍵,並且一樣的話,修改該節點的值
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        entry->value = value;
        return;
    }
    // 當前節點不為空,而且key不一樣,那麼表示hash衝突了,需要查詢連結串列
    while (entry != NULL) {
        //如果找到該鍵,那麼修改該節點的值
        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;//迭代次數
    hashMapIterator->index= 0;//迭代位置
    hashMapIterator->nextEntry= NULL;//下次迭代節點

    return hashMapIterator;
}
boolean hasNextHashMapIterator(HashMapIterator *iterator){
    return iterator->count < iterator->hashMap->size ? TRUE : FALSE;
}
Entry *nextHashMapIterator(HashMapIterator *iterator) {
    if (hasNextHashMapIterator(iterator)) {
        //如果節點中存在hash衝突連結串列那麼就迭代連結串列
        if(iterator->nextEntry!=NULL){//如果下次迭代節點不為空,那麼直接返回下次迭代節點
            Entry *entry = iterator->nextEntry;
            iterator->nextEntry = entry->next;
            iterator->count++;
            return entry;
        }

        Entry *pEntry1 = iterator->hashMap->list[iterator->index];
        //找到不是空的節點
        while (pEntry1==NULL){
            pEntry1 = iterator->hashMap->list[++iterator->index];
        }
        //如果沒有hash衝突節點,那麼下次迭代節點在當前節點向後繼續搜尋
        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 ,返回一個自定義的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,返回一個自定義的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;
}

複製一個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;
}

將一個map集合合併到另一個map集合裡

//將一個map集合,合併到另一個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);
    }
}

合併兩個Map集合,返回一個新的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;
}

差集

//差集,返回一個新的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;
}

交集

//交集,返回一個新的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;
}

補集

//補集,返回一個新的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++) {
        // 釋放衝突值記憶體
        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);
        }
    }
    // 釋放儲存空間
    free(hashMap->list);
    free(hashMap);
}

到此這篇關於C語言實現手寫Map(全功能)的範例程式碼的文章就介紹到這了,更多相關C語言 Map內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！