如何用C語言實現手寫Map

本文小編為大家詳細介紹“如何用C語言實現手寫Map”，內容詳細，步驟清晰，細節處理妥當，希望這篇“如何用C語言實現手寫Map”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

要求

需要準備數組集合(List) 數據結構

需要準備單向鏈表(Linked) 數據結構

需要準備紅黑樹(Rbtree)數據結構

需要準備紅黑樹和鏈表適配策略

hashmap使用紅黑樹的原因是： 當某個節點值過多的時候那么鏈表就會非常長,這樣搜索的時候查詢速度就是O(N) 線性查詢了,為了避免這個問題我們使用了紅黑樹,當鏈表長度大于8的時候我們轉換為紅黑樹,當紅黑樹的長度小于6的時候轉換為鏈表,這樣既可以利用鏈表對內存的使用率而且還可以使用紅黑樹的高效檢索，是一種很有效率的數據結構。那么為啥不使用AVL樹呢? 因為AVL樹是一種高度平衡的二叉樹，所以查找的非常高，但是，有利就有弊，AVL樹為了維持這種高度的平衡，就要付出更多代價。每次插入、刪除都要做調整，復雜、耗時。所以，使用紅黑樹是最好的策略。

結構

紅黑樹和鏈表轉換策略

#ifndef STUDY_LINKEDKVANDRBTREE_H
#define STUDY_LINKEDKVANDRBTREE_H
#include "charkvlinked.h"
#include "rbtree.h"
typedef int boolean;//定義一個布爾類型
#define TRUE 1
#define FALSE 0
enum LINKEDKV_RBTREE_TYPE{LINKEDKV=0,RBTREE=1};
typedef  struct  linkedKvAndRbTree{
    CharKvLinked *linked; // 鏈表
    RBTree *rbTree; // 紅黑樹
    int len;// 長度
    enum LINKEDKV_RBTREE_TYPE type; // 類型
} LinkedKvAndRbTree;
#define  isLinked(linkedKvAndRbTree) ((linkedKvAndRbTree != NULL) && (linkedKvAndRbTree->type == LINKEDKV)) ? TRUE : FALSE
#define  isRbtree(linkedKvAndRbTree) ((linkedKvAndRbTree != NULL) && (linkedKvAndRbTree->type == RBTREE)) ? TRUE : FALSE
LinkedKvAndRbTree *createLinkedKvAndRbTree();
void linked_to_rbtree(LinkedKvAndRbTree *linkedKvAndRbTree);
void rbtree_to_linked(LinkedKvAndRbTree *linkedKvAndRbTree);
void insertOrUpdateLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key,char *value);
void *searchLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key);
void deleteLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key);
CharKvLinked * getAllLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree);
boolean isExistLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key);
void destroyLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree);
// 迭代器結構
typedef struct linkedKvAndRbTreeIterator {
    CharKvLinkedNode *next;// 迭代器當前指向
    int count;//迭代次數
    CharKvLinked *linked;//鏈表
    int index; //位置
}LinkedKvAndRbTreeIterator;

LinkedKvAndRbTreeIterator *createLinkedKvAndRbTreeIterator(LinkedKvAndRbTree *linkedKvAndRbTree);
boolean hasNextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator);
CharKvLinkedNode *nextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator);
#endif //STUDY_LINKEDKVANDRBTREE_H

#include <stdio.h>
#include "linkedKvAndRbTree.h"
#include <stdlib.h>
//創建
LinkedKvAndRbTree *createLinkedKvAndRbTree() {
    LinkedKvAndRbTree *linkedKvAndRbTree= malloc(sizeof(LinkedKvAndRbTree));
    linkedKvAndRbTree->linked=NULL;
    linkedKvAndRbTree->rbTree=NULL;
    linkedKvAndRbTree->len=0;
    linkedKvAndRbTree->type=LINKEDKV;//默認是鏈表,滿足條件則轉換為紅黑樹或者降級為鏈表
    return linkedKvAndRbTree;
}

void linked_to_rbtree(LinkedKvAndRbTree *linkedKvAndRbTree){
    //鏈表轉換為紅黑樹(不保證唯一性(可重復),自行判斷)
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isLinked(linkedKvAndRbTree)){
        linkedKvAndRbTree->type = RBTREE;
        linkedKvAndRbTree->rbTree = createRBTree();
        CharKvLinkedNode *node = linkedKvAndRbTree->linked->head;
        while(node != NULL){
            insertRBTreeKeyRepetition(linkedKvAndRbTree->rbTree,createRbTreeNode(node->key,node->value));
            node = node->next;
        }
        linkedKvAndRbTree->len = linkedKvAndRbTree->rbTree->size;
        //清除鏈表
        destroyCharKvLinked(linkedKvAndRbTree->linked);
        linkedKvAndRbTree->linked=NULL;
    }
}
//紅黑樹轉換為鏈表(不保證唯一性(可重復),自行判斷)
void rbtree_to_linked(LinkedKvAndRbTree *linkedKvAndRbTree){
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isRbtree(linkedKvAndRbTree)){
        linkedKvAndRbTree->type = LINKEDKV;
        linkedKvAndRbTree->linked = createCharKvLinked();
        RBNode *node = linkedKvAndRbTree->rbTree->root;
        while(node != NULL){
            insertCharKvLinkedHeadNode(linkedKvAndRbTree->linked,createCharKvLinkedNode(node->key,node->value));
            node = node->right;
        }
        linkedKvAndRbTree->len = linkedKvAndRbTree->linked->len;
        //清除紅黑樹
        destroyRbTree(linkedKvAndRbTree->rbTree);
        linkedKvAndRbTree->rbTree=NULL;
    }
}

//插入時候key是唯一的,如果沖突那么就修改value
void insertOrUpdateLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key,char *value){
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isLinked(linkedKvAndRbTree)){
        if(linkedKvAndRbTree->linked==NULL){
            linkedKvAndRbTree->linked= createCharKvLinked();
        }
        //長度大于8的時候轉換為紅黑樹
        if(linkedKvAndRbTree->linked->len >=8){
            linked_to_rbtree(linkedKvAndRbTree);
            insertOrUpdateRBTreeKey(linkedKvAndRbTree->rbTree,createRbTreeNode(key,value));
        }else{
            insertOrUpdateCharKvLinkedHeadNode(linkedKvAndRbTree->linked,createCharKvLinkedNode(key,value));
        }
    }else if(isRbtree(linkedKvAndRbTree)){
        if(linkedKvAndRbTree->rbTree==NULL){
            linkedKvAndRbTree->rbTree=createRBTree();
        }
        insertOrUpdateRBTreeKey(linkedKvAndRbTree->rbTree,createRbTreeNode(key,value));
    }else{
        return;
    }

    linkedKvAndRbTree->len++;
}
//查詢,返回節點的value
void *searchLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key){
    if(linkedKvAndRbTree == NULL){
        return NULL;
    }
    if(isLinked(linkedKvAndRbTree)){
        CharKvLinkedNode *pNode = searchCharKvLinked(linkedKvAndRbTree->linked, key);
        return pNode!=NULL?pNode->value:NULL;
    }else if(isRbtree(linkedKvAndRbTree)){
        RBNode *pNode = searchRbTree(linkedKvAndRbTree->rbTree, key);
        return pNode!=NULL?pNode->value:NULL;
    }
    return NULL;
}

//判斷是否存在
boolean isExistLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key){
    if(linkedKvAndRbTree == NULL){
        return FALSE;
    }
    if(isLinked(linkedKvAndRbTree)){
        return isExistCharKvLinked(linkedKvAndRbTree->linked,key);
    }else if(isRbtree(linkedKvAndRbTree)){
        return isExistRbTree(linkedKvAndRbTree->rbTree,key);
    }
    return FALSE;
}

//刪除
void deleteLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree,char *key){
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isLinked(linkedKvAndRbTree)){
        delCharKvLinkedNode(linkedKvAndRbTree->linked,key);
    }else if(isRbtree(linkedKvAndRbTree)){
        //長度小于6的時候轉換為鏈表
        if(linkedKvAndRbTree->rbTree->size <=6){
            rbtree_to_linked(linkedKvAndRbTree);
            delCharKvLinkedNode(linkedKvAndRbTree->linked,key);
        } else{
            removeRbTree(linkedKvAndRbTree->rbTree,key);
        }
    } else{
        return;
    }
    linkedKvAndRbTree->len--;
}

//獲取所有的key和value
CharKvLinked * getAllLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree){
    if(linkedKvAndRbTree == NULL){
        return NULL;
    }
    if(isLinked(linkedKvAndRbTree)){
       return copyCharKvLinked(linkedKvAndRbTree->linked);
    }else if(isRbtree(linkedKvAndRbTree)){
        return getAllKeyAndValueRbTree(linkedKvAndRbTree->rbTree);
    }else{
        return NULL;
    }
}
//銷毀
void destroyLinkedKvAndRbTree(LinkedKvAndRbTree *linkedKvAndRbTree){
    if(linkedKvAndRbTree == NULL){
        return;
    }
    if(isLinked(linkedKvAndRbTree)){
        destroyCharKvLinked(linkedKvAndRbTree->linked);
    }else if(isRbtree(linkedKvAndRbTree)){
        destroyRbTree(linkedKvAndRbTree->rbTree);
    }
    free(linkedKvAndRbTree);
}



LinkedKvAndRbTreeIterator *createLinkedKvAndRbTreeIterator(LinkedKvAndRbTree *linkedKvAndRbTree) {
    LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator = malloc(sizeof(LinkedKvAndRbTreeIterator));;
    linkedKvAndRbTreeIterator->count = 0;//迭代次數
    linkedKvAndRbTreeIterator->linked = getAllLinkedKvAndRbTree(linkedKvAndRbTree);
    linkedKvAndRbTreeIterator->next = linkedKvAndRbTreeIterator->linked->head;//下次迭代節點
    return linkedKvAndRbTreeIterator;
}
boolean hasNextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator) {
   boolean pd=linkedKvAndRbTreeIterator->count < linkedKvAndRbTreeIterator->linked->len ? TRUE : FALSE;
   if(!pd){
       free(linkedKvAndRbTreeIterator->linked);
       free(linkedKvAndRbTreeIterator);
   }
  return pd;
}

CharKvLinkedNode *nextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator) {
    if(!hasNextLinkedKvAndRbTreeIterator(linkedKvAndRbTreeIterator)){
        return NULL;
    }
    CharKvLinkedNode *pNode = linkedKvAndRbTreeIterator->next;
    linkedKvAndRbTreeIterator->next =pNode->next;//切換到下一個節點
    linkedKvAndRbTreeIterator->count++;
    return pNode;
}

hash

#ifndef STUDY_CHARHASH_H
#define STUDY_CHARHASH_H
#include "charlist.h"

#include "../structure/linkedKvAndRbTree.h"

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

} HashMap;
HashMap *createHashMap(int capacity);
void putHashMap(HashMap *hashMap, char *key, void *value);
void printHashMap(HashMap *hashMap);
void *getHashMap(HashMap *hashMap, char *key);
boolean containsKey(HashMap *hashMap, char *key);
boolean containsValue(HashMap *hashMap, void *value);
void removeHashMap(HashMap *hashMap, char *key);
void updateHashMap(HashMap *hashMap, char *key, void *value);
CharList *getKeys(HashMap *hashMap);
CharList *getValues(HashMap *hashMap);
HashMap *copyHashMap(HashMap *hashMap);
void mergeHashMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *mergeHashMapNewMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *differenceHashMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *intersectionHashMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *complementHashMap(HashMap *hashMap1,HashMap *hashMap2);
HashMap *unionHashMap(HashMap *hashMap1,HashMap *hashMap2);
void hashMapClear(HashMap *hashMap);



// 迭代器結構
typedef struct hashMapIterator {
    LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator;// 迭代器
    CharKvLinkedNode *next;// 下次的值
    int count;//迭代次數
    HashMap *hashMap;
    int index; //位置
}HashMapIterator;
// 創建哈希結構迭代器
HashMapIterator *createHashMapIterator(HashMap *hashMap);
// 迭代器是否有下一個
boolean hasNextHashMapIterator(HashMapIterator *iterator);
// 迭代到下一次
CharKvLinkedNode *nextHashMapIterator(HashMapIterator *iterator);

#endif //STUDY_CHARHASH_H

#include "charHash.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//最好的char類型的hash算法,沖突較少,效率較高
static unsigned int BKDRHash(char *str) {
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    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 = (LinkedKvAndRbTree **) calloc(capacity, sizeof(LinkedKvAndRbTree));
    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 >= 3) {
        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集合
static void dilatationHash(HashMap *hashMap) {
    //原來的容量
    int capacity = hashMap->capacity;
    //擴容后的容量
    hashMap->capacity = expansionBase(hashMap);
    //節點長度清空
    hashMap->nodeLen = 0;
    //創建新的存儲區域
    LinkedKvAndRbTree **newList = (LinkedKvAndRbTree **) calloc(hashMap->capacity, sizeof(LinkedKvAndRbTree));

    for (int i = 0; i < capacity; ++i) {
        //獲取舊的存儲區域的每個節點
        LinkedKvAndRbTree *node = hashMap->list[i];
        //如果節點不為空,將舊的節點所有數據放入新的存儲區域
        if (node != NULL) {
            //拿到舊節點的所有key和value
            CharKvLinked *pCharKvLinked = getAllLinkedKvAndRbTree(node);
            //遍歷每個key和value,將每個key和value放入新的存儲區域
            CharKvLinkedIterator *pIterator = createCharKvLinkedIterator(pCharKvLinked);
            while (hasNextCharKvLinkedIterator(pIterator)) {
                CharKvLinkedNode *pNode = nextCharKvLinkedIterator(pIterator);
                //獲取新的存儲區域的下標
                unsigned int index = defaultHashCode(*hashMap, pNode->key);
                //將舊的節點放入新的存儲區域
                LinkedKvAndRbTree *linkedKvAndRbTree = newList[index];
                if (linkedKvAndRbTree == NULL) {
                    //如果新存儲區域的節點為空,創建新的節點
                    LinkedKvAndRbTree *newLinkedKvAndRbTree = createLinkedKvAndRbTree();
                    insertOrUpdateLinkedKvAndRbTree(newLinkedKvAndRbTree, pNode->key, pNode->value);
                    newList[index] = newLinkedKvAndRbTree;
                    hashMap->nodeLen++; //節點長度加1
                } else {
                    //如果新存儲區域的節點不為空,將舊的節點放入新的存儲區域
                    insertOrUpdateLinkedKvAndRbTree(linkedKvAndRbTree, pNode->key, pNode->value);
                }

            }
        }
    }

    //釋放舊的存儲區域
    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);
    //獲取節點
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果節點是空的那么直接添加
    if (linkedKvAndRbTree == NULL) {
        //如果新存儲區域的節點為空,創建新的節點
        LinkedKvAndRbTree *newLinkedKvAndRbTree = createLinkedKvAndRbTree();
        insertOrUpdateLinkedKvAndRbTree(newLinkedKvAndRbTree, key, value);
        hashMap->list[hashCode] = newLinkedKvAndRbTree;
        hashMap->size++;
        hashMap->nodeLen++;
        return;
    }
    //如果節點不為空,那么就插入或者修改
    insertOrUpdateLinkedKvAndRbTree(linkedKvAndRbTree, key, value);
    hashMap->size++;
}

//打印Map集合
void printHashMap(HashMap *hashMap) {
    for (int i = 0; i < hashMap->capacity; i++) {
        LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[i];
        if (linkedKvAndRbTree != NULL) {
            CharKvLinked *pLinked = getAllLinkedKvAndRbTree(linkedKvAndRbTree);
            printCharKvLinked(pLinked);
        }
    }
}


//獲取Map集合中的元素
void *getHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節點
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果節點是空的那么直接返回
    if (linkedKvAndRbTree == NULL) {
        return NULL;
    }
    //獲取節點中的值
    return searchLinkedKvAndRbTree(linkedKvAndRbTree, key);
}

//判斷鍵是否存在
boolean containsKey(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節點
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果節點是空的那么直接返回FALSE
    if (linkedKvAndRbTree == NULL) {
        return FALSE;
    }
    return isExistLinkedKvAndRbTree(linkedKvAndRbTree, key);
}

//刪除Map集合中的元素
void removeHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節點
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果節點是空的那么直接返回
    if (linkedKvAndRbTree == NULL) {
        return;
    }
    //判斷是否存在該鍵,并且一樣的話,刪除該節點
    if (isExistLinkedKvAndRbTree(linkedKvAndRbTree, key)) {
        deleteLinkedKvAndRbTree(linkedKvAndRbTree, key);
        hashMap->size--;
        return;
    }
}


//修改Map集合中的元素
void updateHashMap(HashMap *hashMap, char *key, void *value) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節點
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果節點是空的那么直接返回
    if (linkedKvAndRbTree == NULL) {
        return;
    }
    //判斷是否存在該鍵,然后進行修改
    if (isExistLinkedKvAndRbTree(linkedKvAndRbTree, key)) {
        insertOrUpdateLinkedKvAndRbTree(linkedKvAndRbTree, key, value);
    }
}

HashMapIterator *createHashMapIterator(HashMap *hashMap) {
    HashMapIterator *pVoid = malloc(sizeof(HashMapIterator));
    pVoid->hashMap = hashMap;
    pVoid->index = 0;
    pVoid->count = 0;
    LinkedKvAndRbTree *pTree = hashMap->list[pVoid->index];
    //找到不是空的節點
    while (pTree == NULL) {
        pTree = hashMap->list[++pVoid->index];
    }
    //創建迭代器
    pVoid->linkedKvAndRbTreeIterator = createLinkedKvAndRbTreeIterator(pTree);
    //獲取迭代器中的第一個節點
    pVoid->next = nextLinkedKvAndRbTreeIterator(pVoid->linkedKvAndRbTreeIterator);;
    ++pVoid->index;
    return pVoid;
}

boolean hasNextHashMapIterator(HashMapIterator *iterator) {
    boolean pd = iterator->count < iterator->hashMap->size ? TRUE : FALSE;
    if (!pd) {
        free(iterator);
    }
    return pd;
}

CharKvLinkedNode *nextHashMapIterator(HashMapIterator *iterator) {
    if (!hasNextHashMapIterator(iterator)) {
        return NULL;
    }
    CharKvLinkedNode *entry = iterator->next;
    //獲取下一個節點
    CharKvLinkedNode *nextNode = nextLinkedKvAndRbTreeIterator(iterator->linkedKvAndRbTreeIterator);
    if (nextNode != NULL) {
        iterator->next = nextNode;
    } else {
        //如果是最后一個節點了,那么就不在找下個節點了
        if (iterator->count + 1 < iterator->hashMap->size) {
            //獲取下一個節點
            LinkedKvAndRbTree *pTree = iterator->hashMap->list[iterator->index];
            while (pTree == NULL) {
                pTree = iterator->hashMap->list[++iterator->index];
            }
            iterator->linkedKvAndRbTreeIterator = createLinkedKvAndRbTreeIterator(pTree);
            iterator->next = nextLinkedKvAndRbTreeIterator(iterator->linkedKvAndRbTreeIterator);;
            ++iterator->index;
        }
    }
    iterator->count++;
    return entry;
}


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

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

//復制一個HashMap
HashMap *copyHashMap(HashMap *hashMap) {
    HashMap *pHashMap = createHashMap(hashMap->capacity);
    HashMapIterator *pIterator = createHashMapIterator(hashMap);
    while (hasNextHashMapIterator(pIterator)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    return pHashMap;
}

//將一個map集合,合并到另一個map集合里   hashMap2合并到hashMap1
void mergeHashMap(HashMap *hashMap1, HashMap *hashMap2) {
    HashMapIterator *pIterator = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator)) {
        CharKvLinkedNode *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)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator1);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        CharKvLinkedNode *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)) {
        CharKvLinkedNode *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)) {
        CharKvLinkedNode *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)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator1);
        if (!containsKey(hashMap2, entry->key)) {
            putHashMap(pHashMap, entry->key, entry->value);
        }
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator2);
        if (!containsKey(hashMap1, entry->key)) {
            putHashMap(pHashMap, entry->key, entry->value);
        }
    }
    return pHashMap;
}

//并集,返回一個新的Map集合 (如果有相同的key,則取hashMap2的值)
HashMap *unionHashMap(HashMap *hashMap1, HashMap *hashMap2) {
    HashMap *pHashMap = createHashMap(hashMap1->capacity + hashMap2->capacity);
    HashMapIterator *pIterator1 = createHashMapIterator(hashMap1);
    while (hasNextHashMapIterator(pIterator1)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator1);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    HashMapIterator *pIterator2 = createHashMapIterator(hashMap2);
    while (hasNextHashMapIterator(pIterator2)) {
        CharKvLinkedNode *entry = nextHashMapIterator(pIterator2);
        putHashMap(pHashMap, entry->key, entry->value);
    }
    return pHashMap;
}

void hashMapClear(HashMap *hashMap) {
    for (int i = 0; i < hashMap->nodeLen; i++) {
        // 釋放沖突值內存
        LinkedKvAndRbTree *pTree = hashMap->list[i];
        if (pTree != NULL) {
            destroyLinkedKvAndRbTree(pTree);
        }
    }
    // 釋放存儲空間
    free(hashMap->list);
    free(hashMap);
}

使用

int main() {

    HashMap *pMap = createHashMap(10);
    for (int i = 0; i < 100; i++) {  //插入從0~1億數據大約60~90秒
        char *str = (char *) malloc(sizeof(char) * 10);
        sprintf(str, "%d", i);
        putHashMap(pMap, str, str);
    }

//打印
    printHashMap(pMap);

    //迭代器
//    HashMapIterator *pIterator = createHashMapIterator(pMap);
//    while (hasNextHashMapIterator(pIterator)) {
//        CharKvLinkedNode *entry = nextHashMapIterator(pIterator);
//        printf("%s %s\n", entry->key, entry->value);
//    }

//    void *pVoid = getHashMap(pMap, "999999");   // O(1) 查詢速度  
//    printf("=====%s\n",pVoid);

//    CharList *pCharlist = getValues(pMap);
//    printCharList(pCharlist);

    hashMapClear(pMap);


}

讀到這里，這篇“如何用C語言實現手寫Map”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。