如何用C语言实现手写Map(c语言,map,开发技术)

本文小编为大家详细介绍“如何用C语言实现手写Map”，内容详细，步骤清晰，细节处理妥当，希望这篇“如何用C语言实现手写Map”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

要求

需要准备数组集合(List) 数据结构

需要准备单向链表(Linked) 数据结构

需要准备红黑树(Rbtree)数据结构

需要准备红黑树和链表适配策略

hashmap使用红黑树的原因是： 当某个节点值过多的时候那么链表就会非常长,这样搜索的时候查询速度就是O(N) 线性查询了,为了避免这个问题我们使用了红黑树,当链表长度大于8的时候我们转换为红黑树,当红黑树的长度小于6的时候转换为链表,这样既可以利用链表对内存的使用率而且还可以使用红黑树的高效检索，是一种很有效率的数据结构。那么为啥不使用AVL树呢? 因为AVL树是一种高度平衡的二叉树，所以查找的非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多代价。每次插入、删除都要做调整，复杂、耗时。所以，使用红黑树是最好的策略。

结构

红黑树和链表转换策略

#ifndefSTUDY_LINKEDKVANDRBTREE_H#defineSTUDY_LINKEDKVANDRBTREE_H#include"charkvlinked.h"#include"rbtree.h"typedefintboolean;//定义一个布尔类型#defineTRUE1#defineFALSE0enumLINKEDKV_RBTREE_TYPE{LINKEDKV=0,RBTREE=1};typedefstructlinkedKvAndRbTree{CharKvLinked*linked;//链表RBTree*rbTree;//红黑树intlen;//长度enumLINKEDKV_RBTREE_TYPEtype;//类型}LinkedKvAndRbTree;#defineisLinked(linkedKvAndRbTree)((linkedKvAndRbTree!=NULL)&&(linkedKvAndRbTree->type==LINKEDKV))?TRUE:FALSE#defineisRbtree(linkedKvAndRbTree)((linkedKvAndRbTree!=NULL)&&(linkedKvAndRbTree->type==RBTREE))?TRUE:FALSELinkedKvAndRbTree*createLinkedKvAndRbTree();voidlinked_to_rbtree(LinkedKvAndRbTree*linkedKvAndRbTree);voidrbtree_to_linked(LinkedKvAndRbTree*linkedKvAndRbTree);voidinsertOrUpdateLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree,char*key,char*value);void*searchLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree,char*key);voiddeleteLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree,char*key);CharKvLinked*getAllLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree);booleanisExistLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree,char*key);voiddestroyLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree);//迭代器结构typedefstructlinkedKvAndRbTreeIterator{CharKvLinkedNode*next;//迭代器当前指向intcount;//迭代次数CharKvLinked*linked;//链表intindex;//位置}LinkedKvAndRbTreeIterator;LinkedKvAndRbTreeIterator*createLinkedKvAndRbTreeIterator(LinkedKvAndRbTree*linkedKvAndRbTree);booleanhasNextLinkedKvAndRbTreeIterator(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;//默认是链表,满足条件则转换为红黑树或者降级为链表returnlinkedKvAndRbTree;}voidlinked_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;}}//红黑树转换为链表(不保证唯一性(可重复),自行判断)voidrbtree_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是唯一的,如果冲突那么就修改valuevoidinsertOrUpdateLinkedKvAndRbTree(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));}}elseif(isRbtree(linkedKvAndRbTree)){if(linkedKvAndRbTree->rbTree==NULL){linkedKvAndRbTree->rbTree=createRBTree();}insertOrUpdateRBTreeKey(linkedKvAndRbTree->rbTree,createRbTreeNode(key,value));}else{return;}linkedKvAndRbTree->len++;}//查询,返回节点的valuevoid*searchLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree,char*key){if(linkedKvAndRbTree==NULL){returnNULL;}if(isLinked(linkedKvAndRbTree)){CharKvLinkedNode*pNode=searchCharKvLinked(linkedKvAndRbTree->linked,key);returnpNode!=NULL?pNode->value:NULL;}elseif(isRbtree(linkedKvAndRbTree)){RBNode*pNode=searchRbTree(linkedKvAndRbTree->rbTree,key);returnpNode!=NULL?pNode->value:NULL;}returnNULL;}//判断是否存在booleanisExistLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree,char*key){if(linkedKvAndRbTree==NULL){returnFALSE;}if(isLinked(linkedKvAndRbTree)){returnisExistCharKvLinked(linkedKvAndRbTree->linked,key);}elseif(isRbtree(linkedKvAndRbTree)){returnisExistRbTree(linkedKvAndRbTree->rbTree,key);}returnFALSE;}//删除voiddeleteLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree,char*key){if(linkedKvAndRbTree==NULL){return;}if(isLinked(linkedKvAndRbTree)){delCharKvLinkedNode(linkedKvAndRbTree->linked,key);}elseif(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和valueCharKvLinked*getAllLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree){if(linkedKvAndRbTree==NULL){returnNULL;}if(isLinked(linkedKvAndRbTree)){returncopyCharKvLinked(linkedKvAndRbTree->linked);}elseif(isRbtree(linkedKvAndRbTree)){returngetAllKeyAndValueRbTree(linkedKvAndRbTree->rbTree);}else{returnNULL;}}//销毁voiddestroyLinkedKvAndRbTree(LinkedKvAndRbTree*linkedKvAndRbTree){if(linkedKvAndRbTree==NULL){return;}if(isLinked(linkedKvAndRbTree)){destroyCharKvLinked(linkedKvAndRbTree->linked);}elseif(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;//下次迭代节点returnlinkedKvAndRbTreeIterator;}booleanhasNextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator*linkedKvAndRbTreeIterator){booleanpd=linkedKvAndRbTreeIterator->count<linkedKvAndRbTreeIterator->linked->len?TRUE:FALSE;if(!pd){free(linkedKvAndRbTreeIterator->linked);free(linkedKvAndRbTreeIterator);}returnpd;}CharKvLinkedNode*nextLinkedKvAndRbTreeIterator(LinkedKvAndRbTreeIterator*linkedKvAndRbTreeIterator){if(!hasNextLinkedKvAndRbTreeIterator(linkedKvAndRbTreeIterator)){returnNULL;}CharKvLinkedNode*pNode=linkedKvAndRbTreeIterator->next;linkedKvAndRbTreeIterator->next=pNode->next;//切换到下一个节点linkedKvAndRbTreeIterator->count++;returnpNode;}

hash

#ifndefSTUDY_CHARHASH_H#defineSTUDY_CHARHASH_H#include"charlist.h"#include"../structure/linkedKvAndRbTree.h"typedefintboolean;//定义一个布尔类型#defineTRUE1#defineFALSE0//哈希表结构体typedefstructhashMap{intsize;//集合元素个数intcapacity;//容量intnodeLen;//节点长度LinkedKvAndRbTree**list;//存储区域intdilatationCount;//扩容次数intdilatationSum;//扩容总次数}HashMap;HashMap*createHashMap(intcapacity);voidputHashMap(HashMap*hashMap,char*key,void*value);voidprintHashMap(HashMap*hashMap);void*getHashMap(HashMap*hashMap,char*key);booleancontainsKey(HashMap*hashMap,char*key);booleancontainsValue(HashMap*hashMap,void*value);voidremoveHashMap(HashMap*hashMap,char*key);voidupdateHashMap(HashMap*hashMap,char*key,void*value);CharList*getKeys(HashMap*hashMap);CharList*getValues(HashMap*hashMap);HashMap*copyHashMap(HashMap*hashMap);voidmergeHashMap(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);voidhashMapClear(HashMap*hashMap);//迭代器结构typedefstructhashMapIterator{LinkedKvAndRbTreeIterator*linkedKvAndRbTreeIterator;//迭代器CharKvLinkedNode*next;//下次的值intcount;//迭代次数HashMap*hashMap;intindex;//位置}HashMapIterator;//创建哈希结构迭代器HashMapIterator*createHashMapIterator(HashMap*hashMap);//迭代器是否有下一个booleanhasNextHashMapIterator(HashMapIterator*iterator);//迭代到下一次CharKvLinkedNode*nextHashMapIterator(HashMapIterator*iterator);#endif//STUDY_CHARHASH_H

#include"charHash.h"#include<stdio.h>#include<string.h>#include<stdlib.h>//最好的char类型的hash算法,冲突较少,效率较高staticunsignedintBKDRHash(char*str){unsignedintseed=131;//31131131313131131313etc..unsignedinthash=0;while(*str){hash=hash*seed+(*str++);}return(hash&0x7FFFFFFF);}//hash值长度取模最后获取实际位置的下标staticunsignedintdefaultHashCode(HashMaphashMap,char*key){returnBKDRHash(key)%hashMap.capacity;}//创建Map集合HashMap*createHashMap(intcapacity){//创建哈希表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));returnhashMap;}//扩容基数staticintexpansionBase(HashMap*hashMap){intlen=hashMap->capacity;intdilatationCount=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;}returnlen;}//扩容Map集合staticvoiddilatationHash(HashMap*hashMap){//原来的容量intcapacity=hashMap->capacity;//扩容后的容量hashMap->capacity=expansionBase(hashMap);//节点长度清空hashMap->nodeLen=0;//创建新的存储区域LinkedKvAndRbTree**newList=(LinkedKvAndRbTree**)calloc(hashMap->capacity,sizeof(LinkedKvAndRbTree));for(inti=0;i<capacity;++i){//获取旧的存储区域的每个节点LinkedKvAndRbTree*node=hashMap->list[i];//如果节点不为空,将旧的节点所有数据放入新的存储区域if(node!=NULL){//拿到旧节点的所有key和valueCharKvLinked*pCharKvLinked=getAllLinkedKvAndRbTree(node);//遍历每个key和value,将每个key和value放入新的存储区域CharKvLinkedIterator*pIterator=createCharKvLinkedIterator(pCharKvLinked);while(hasNextCharKvLinkedIterator(pIterator)){CharKvLinkedNode*pNode=nextCharKvLinkedIterator(pIterator);//获取新的存储区域的下标unsignedintindex=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集合添加元素voidputHashMap(HashMap*hashMap,char*key,void*value){//判断是否需要扩容if(hashMap->nodeLen==hashMap->capacity){dilatationHash(hashMap);}//获取hash值unsignedinthashCode=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集合voidprintHashMap(HashMap*hashMap){for(inti=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值unsignedinthashCode=defaultHashCode(*hashMap,key);//获取节点LinkedKvAndRbTree*linkedKvAndRbTree=hashMap->list[hashCode];//如果节点是空的那么直接返回if(linkedKvAndRbTree==NULL){returnNULL;}//获取节点中的值returnsearchLinkedKvAndRbTree(linkedKvAndRbTree,key);}//判断键是否存在booleancontainsKey(HashMap*hashMap,char*key){//获取hash值unsignedinthashCode=defaultHashCode(*hashMap,key);//获取节点LinkedKvAndRbTree*linkedKvAndRbTree=hashMap->list[hashCode];//如果节点是空的那么直接返回FALSEif(linkedKvAndRbTree==NULL){returnFALSE;}returnisExistLinkedKvAndRbTree(linkedKvAndRbTree,key);}//删除Map集合中的元素voidremoveHashMap(HashMap*hashMap,char*key){//获取hash值unsignedinthashCode=defaultHashCode(*hashMap,key);//获取节点LinkedKvAndRbTree*linkedKvAndRbTree=hashMap->list[hashCode];//如果节点是空的那么直接返回if(linkedKvAndRbTree==NULL){return;}//判断是否存在该键,并且一样的话,删除该节点if(isExistLinkedKvAndRbTree(linkedKvAndRbTree,key)){deleteLinkedKvAndRbTree(linkedKvAndRbTree,key);hashMap->size--;return;}}//修改Map集合中的元素voidupdateHashMap(HashMap*hashMap,char*key,void*value){//获取hash值unsignedinthashCode=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;returnpVoid;}booleanhasNextHashMapIterator(HashMapIterator*iterator){booleanpd=iterator->count<iterator->hashMap->size?TRUE:FALSE;if(!pd){free(iterator);}returnpd;}CharKvLinkedNode*nextHashMapIterator(HashMapIterator*iterator){if(!hasNextHashMapIterator(iterator)){returnNULL;}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++;returnentry;}//获取所有的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);}returnpCharlist;}//获取所有的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);}returnpCharlist;}//复制一个HashMapHashMap*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);}returnpHashMap;}//将一个map集合,合并到另一个map集合里hashMap2合并到hashMap1voidmergeHashMap(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);}returnpHashMap;}//差集,返回一个新的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);}}returnpHashMap;}//交集,返回一个新的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);}}returnpHashMap;}//补集,返回一个新的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);}}returnpHashMap;}//并集,返回一个新的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);}returnpHashMap;}voidhashMapClear(HashMap*hashMap){for(inti=0;i<hashMap->nodeLen;i++){//释放冲突值内存LinkedKvAndRbTree*pTree=hashMap->list[i];if(pTree!=NULL){destroyLinkedKvAndRbTree(pTree);}}//释放存储空间free(hashMap->list);free(hashMap);}

使用

intmain(){HashMap*pMap=createHashMap(10);for(inti=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”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注亿速云行业资讯频道。