怎么用C语言实现Map |
您所在的位置：网站首页 › c语言中有list吗 › 怎么用C语言实现Map |
怎么用C语言实现Map
|
怎么用C语言实现Map
发布时间：2022-08-25 15:45:53
来源：亿速云
阅读：2445
作者：iii
栏目：开发技术
今天小编给大家分享一下怎么用C语言实现Map的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。 为啥需要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(capacitysize=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;ilist[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 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); //获取节点 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 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 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; }复制一个MapHashMap *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; }清除Mapvoid hashMapClear(HashMap *hashMap){ for (int i = 0; i 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”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。 推荐阅读： STL中map怎么用 python中map怎么用免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：[email protected]进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。 c语言 map 上一篇新闻：php数组如何去掉最后一项 下一篇新闻：Mybatis泛型擦除问题如何解决 猜你喜欢 个人服务器搭建需要哪些配置 国外vps租用选择服务商要注意哪些事项 日本vps服务器租用能干什么 免费php主机租用怎么搭建网站 php主机租用服务器环境怎么搭建 购买便宜域名要注意哪些事项 免费cdn加速服务器连接失败怎么解决 php主机空间搭建怎么设置内存 php主机空间租用有哪些特点 游戏论坛主机租用有哪些特点 |
【本文地址】
今日新闻 |
推荐新闻 |