如何用C語言實現(xiàn)手寫Map

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

要求

需要準(zhǔn)備數(shù)組集合(List) 數(shù)據(jù)結(jié)構(gòu)

需要準(zhǔn)備單向鏈表(Linked) 數(shù)據(jù)結(jié)構(gòu)

需要準(zhǔn)備紅黑樹(Rbtree)數(shù)據(jù)結(jié)構(gòu)

需要準(zhǔn)備紅黑樹和鏈表適配策略

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

結(jié)構(gòu)

紅黑樹和鏈表轉(zhuǎn)換策略

#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);
// 迭代器結(jié)構(gòu)
typedef struct linkedKvAndRbTreeIterator {
    CharKvLinkedNode *next;// 迭代器當(dāng)前指向
    int count;//迭代次數(shù)
    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>
//創(chuàng)建
LinkedKvAndRbTree *createLinkedKvAndRbTree() {
    LinkedKvAndRbTree *linkedKvAndRbTree= malloc(sizeof(LinkedKvAndRbTree));
    linkedKvAndRbTree->linked=NULL;
    linkedKvAndRbTree->rbTree=NULL;
    linkedKvAndRbTree->len=0;
    linkedKvAndRbTree->type=LINKEDKV;//默認(rèn)是鏈表,滿足條件則轉(zhuǎn)換為紅黑樹或者降級為鏈表
    return linkedKvAndRbTree;
}

void linked_to_rbtree(LinkedKvAndRbTree *linkedKvAndRbTree){
    //鏈表轉(zhuǎn)換為紅黑樹(不保證唯一性(可重復(fù)),自行判斷)
    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;
    }
}
//紅黑樹轉(zhuǎn)換為鏈表(不保證唯一性(可重復(fù)),自行判斷)
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的時候轉(zhuǎn)換為紅黑樹
        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++;
}
//查詢,返回節(jié)點的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的時候轉(zhuǎn)換為鏈表
        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;//迭代次數(shù)
    linkedKvAndRbTreeIterator->linked = getAllLinkedKvAndRbTree(linkedKvAndRbTree);
    linkedKvAndRbTreeIterator->next = linkedKvAndRbTreeIterator->linked->head;//下次迭代節(jié)點
    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;//切換到下一個節(jié)點
    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
// 哈希表結(jié)構(gòu)體
typedef struct hashMap {
    int size;           // 集合元素個數(shù)
    int capacity;       // 容量
    int nodeLen;       //節(jié)點長度
    LinkedKvAndRbTree **list;         // 存儲區(qū)域
    int dilatationCount;  //擴(kuò)容次數(shù)
    int dilatationSum;  //擴(kuò)容總次數(shù)

} 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);



// 迭代器結(jié)構(gòu)
typedef struct hashMapIterator {
    LinkedKvAndRbTreeIterator *linkedKvAndRbTreeIterator;// 迭代器
    CharKvLinkedNode *next;// 下次的值
    int count;//迭代次數(shù)
    HashMap *hashMap;
    int index; //位置
}HashMapIterator;
// 創(chuàng)建哈希結(jié)構(gòu)迭代器
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值長度取模最后獲取實際位置的下標(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)建存儲區(qū)域
    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;
}

//擴(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 >= 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;
}

//擴(kuò)容Map集合
static void dilatationHash(HashMap *hashMap) {
    //原來的容量
    int capacity = hashMap->capacity;
    //擴(kuò)容后的容量
    hashMap->capacity = expansionBase(hashMap);
    //節(jié)點長度清空
    hashMap->nodeLen = 0;
    //創(chuàng)建新的存儲區(qū)域
    LinkedKvAndRbTree **newList = (LinkedKvAndRbTree **) calloc(hashMap->capacity, sizeof(LinkedKvAndRbTree));

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

            }
        }
    }

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

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

//刪除Map集合中的元素
void removeHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果節(jié)點是空的那么直接返回
    if (linkedKvAndRbTree == NULL) {
        return;
    }
    //判斷是否存在該鍵,并且一樣的話,刪除該節(jié)點
    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);
    //獲取節(jié)點
    LinkedKvAndRbTree *linkedKvAndRbTree = hashMap->list[hashCode];
    //如果節(jié)點是空的那么直接返回
    if (linkedKvAndRbTree == NULL) {
        return;
    }
    //判斷是否存在該鍵,然后進(jìn)行修改
    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];
    //找到不是空的節(jié)點
    while (pTree == NULL) {
        pTree = hashMap->list[++pVoid->index];
    }
    //創(chuàng)建迭代器
    pVoid->linkedKvAndRbTreeIterator = createLinkedKvAndRbTreeIterator(pTree);
    //獲取迭代器中的第一個節(jié)點
    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;
    //獲取下一個節(jié)點
    CharKvLinkedNode *nextNode = nextLinkedKvAndRbTreeIterator(iterator->linkedKvAndRbTreeIterator);
    if (nextNode != NULL) {
        iterator->next = nextNode;
    } else {
        //如果是最后一個節(jié)點了,那么就不在找下個節(jié)點了
        if (iterator->count + 1 < iterator->hashMap->size) {
            //獲取下一個節(jié)點
            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;
}

//復(fù)制一個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;
}

//補(bǔ)集,返回一個新的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++) {
        // 釋放沖突值內(nè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億數(shù)據(jù)大約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語言實現(xiàn)手寫Map”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。