C语言-手写Map(数组+链表+红黑树)(全功能)

news/2024/5/4 22:10:27/文章来源:https://blog.csdn.net/weixin_45203607/article/details/126649951

要求

  1. 需要准备数组集合(List) 数据结构
  2. 需要准备单向链表(Linked) 数据结构
  3. 需要准备红黑树(Rbtree)数据结构
  4. 需要准备红黑树和链表适配策略(文章内部提供,可以自行参考)

建议先去阅读我博客这篇文章C语言-手写Map(数组+链表)(全功能) 有助于理解

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

结构

在这里插入图片描述

红黑树和链表转换策略

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和valueCharKvLinked *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];//如果节点是空的那么直接返回FALSEif (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);}

在这里插入图片描述

点赞 -收藏-关注-便于以后复习和收到最新内容
有其他问题在评论区讨论-或者私信我-收到会在第一时间回复
在本博客学习的技术不得以任何方式直接或者间接的从事违反中华人民共和国法律,内容仅供学习、交流与参考
免责声明：本文部分素材来源于网络，版权归原创者所有，如存在文章/图片/音视频等使用不当的情况，请随时私信联系我、以迅速采取适当措施，避免给双方造成不必要的经济损失。
感谢,配合,希望我的努力对你有帮助^_^

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_4416.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Java实现的一个编译器源代码（Win11）

Java实现的一个编译器源代码（Win11）

本文的源代码摘自编译器龙书《Compilers : principles, techniques, and tools》第二版的附录A“一个完整的前端”&#xff08;A Complete Front End&#xff09;。 上述书中的编译器是在Unix系统中&#xff0c;主体代码与书中相同&#xff0c;只是对字符串处理不同&#xff1…
阅读更多...
C++ Qt / VS2019 +opencv + onnxruntime 部署语义分割模型【经验】

C++ Qt / VS2019 +opencv + onnxruntime 部署语义分割模型【经验】

本机环境&#xff1a; OS:WIN11 CUDA: 11.1 CUDNN:8.0.5 显卡&#xff1a;RTX3080 16G opencv:3.3.0 onnxruntime:1.8.1 目前C 调用onnxruntime的示例主要为图像分类网络&#xff0c;与语义分割网络在后处理部分有很大不同。 pytorch模型转为onnx格式 1.1 安装onnx, 参考官网…
阅读更多...
Tcp通信

Tcp通信

一发一收 Client package tcpDemo;import java.io.OutputStream; import java.io.PrintStream; import java.net.Socket; import java.util.Scanner;public class Client {public static void main(String[] args) throws Exception {//1.创建Socke通信管道请求服务端的连接//p…
阅读更多...
TCP连接管理机制(超级重要)

TCP连接管理机制(超级重要)

以下是这篇文章讲解的思维导图,整理完,我也脑瓜子嗡嗡的,怎么这么多,那是因为太重要了,防止面试官把你问死,那就必须去了解,加油啊~~~ 参考 : 小林coding 书籍 : TCP/IP 卷一 网站 : 计算机网络-41-60 | 阿秀的学习笔记 知乎文章 : 看到有人说&#xff0c;只看到过TCP状态位…
阅读更多...
【单片机原理及应用】第一篇——单片机概述

【单片机原理及应用】第一篇——单片机概述

个人主页 点击这里 专栏学习 点击这里 目录 内容概要 1.1单片机简介 1.2单片机的发展历史 1.3单片机的特点 1.4单片机的应用 1&#xff0e;工业检测与控制 2&#xff0e;仪器仪表 3&#xff0e;消费类电子产品 4&#xff0e;通讯 5&#xff0e;武器装备 6.各种终…
阅读更多...
python从入门到实践：数据类型、文件处理

python从入门到实践：数据类型、文件处理

目录 一、数据类型 1.数字 整型与浮点型 其他数字类型 2.字符串 3.字节串 4.列表 5.元祖 6.集合 7.字典 8.可变类型与不可变类型 数字类型 字符串 列表 元祖 字典 9.数据类型总结 二、文件处理 1.文件的引入 2.文件的基本操作流程 2.1基本流程 2.2资源回…
阅读更多...
【Java 基础】7、学习 Java 中的方法（方法的定义、可变参数、参数的传递问题、方法重载、方法签名）通过官方教程

【Java 基础】7、学习 Java 中的方法（方法的定义、可变参数、参数的传递问题、方法重载、方法签名）通过官方教程

&#x1f4b0; 写了一段时间的 Java 程序&#xff0c;SpringBoot &#x1f343;项目也做了好几个&#xff0c;但感觉自己对 Java 的了解还是特别少&#xff0c;所以决定从零&#x1f37c;开始重新学习&#xff0c;下面是学习的笔记。【学习素材&#xff1a;韩顺平老师】 &#…
阅读更多...
docker 安装 elasticsearch

docker 安装 elasticsearch

一、安装docker Docker 的安装_傲傲娇的博客-CSDN博客 二、配置es挂载文件和目录 mkdir -p /opt/elasticsearch/{config,data,plugins} chmod 777 /opt/elasticsearch/data 在config目录下创建elasticsearch.yml配置文件 cluster.name: elasticsearch-cluster # 节点名称 n…
阅读更多...
【MC教程】iPad启动Java版mc（无需越狱）(保姆级?) Jitterbug启动iOS我的世界Java版启动器 PojavLauncher

【MC教程】iPad启动Java版mc（无需越狱）(保姆级?) Jitterbug启动iOS我的世界Java版启动器 PojavLauncher

【MC教程】iPad启动Java版mc&#xff08;无需越狱&#xff09;(保姆级?) Jitterbug启动iOS我的世界Java版启动器 PojavLauncher 文章目录【MC教程】iPad启动Java版mc&#xff08;无需越狱&#xff09;(保姆级?) Jitterbug启动iOS我的世界Java版启动器 PojavLauncher前言iSign…
阅读更多...
springmvc实现文件上传书本管理CRUD

springmvc实现文件上传书本管理CRUD

今天小编给大家分享文件上传&#xff0c;和对书本管理进行新增、修改、删除、查询。 效果展示 首页 新增 修改 一、书本管理CRUD 1.开发前必做的配置 1.1 导入pom.xml文件依赖 实现CRUDspringmvc的jar包 <dependency><groupId>org.springframework</groupId…
阅读更多...
3.实现redis哨兵，模拟master故障场景

3.实现redis哨兵，模拟master故障场景

3.实现redis哨兵，模拟master故障场景 实验拓扑图 3.1 哨兵的准备实现主从复制架构 哨兵的前提是已经实现了一个redis的主从复制的运行环境，从而实现一个一主两从基于哨兵的高可用redis架构。 注意: master 的配置文件中的masterauth 和slave的都必须相同 所有主从节点的redis…
阅读更多...
小波神经网络的基本原理,小波神经网络功能分析

小波神经网络的基本原理,小波神经网络功能分析

小波神经网络的优势是什么&#xff1f;谢谢 小波神经网络相比于前向的神经网络,它有明显的优点:首先小波神经网络的基元和整个结构是依据小波分析理论确定的,可以避免BP神经网络等结构设计上的盲目性;其次小波神经网络有更强的学习能力,精度更高。 总的而言&#xff0c;对同样…
阅读更多...
数据结构初步（一）- 时间与空间复杂度

数据结构初步（一）- 时间与空间复杂度

目录前言1. 数据结构与算法1.1 数据结构是啥1.2 算法是啥2. 算法效率2.1 如何衡量一个算法的效率2.2 算法的复杂度3. 时间复杂度3.1 概念3.2 大O的渐进表示法3.3 例子分析计算Func2的时间复杂度计算Func3的时间复杂度计算Func4的时间复杂度计算strchr的时间复杂度计算冒泡排序的…
阅读更多...
端口号被占用解决办法（超详细）

端口号被占用解决办法（超详细）

文章目录问题描述java.net.BindException: Address already in use: JVM_BindWeb server failed to start. Port 8899 was already in use.解决方案问题描述 java.net.BindException: Address already in use: JVM_Bind Web server failed to start. Port 8899 was already in…
阅读更多...
极几何，本质矩阵，基础矩阵，单应矩阵

极几何，本质矩阵，基础矩阵，单应矩阵

什么是三角化&#xff1f; 三角化就是下图的红字部分&#xff1a; 什么是极几何&#xff1f; 极几何描述了同一场景或者物体在两个视点图像间的对应关系。 下图中的O1和O2分别是两个相机的光心&#xff0c;即摄像机坐标系的原点。由下图可知给定了一个三维空间下的P点&…
阅读更多...
07-Linux基本权限

07-Linux基本权限

1. 权限基本概述 1.1 什么是权限&#xff1f; 权限: 操作系统对用户能够执行的功能所设立的限制, 主要用于约束用户能对系统所做的操作, 以及内容访问的范围, 或者说, 权限是指某个特定的用户具有特定的系统资源使用权力.1.2 为什么要有权限&#xff1f; 因为系统中不可能只…
阅读更多...
最详解消息队列以及RabbbitMQ之HelloWorld

最详解消息队列以及RabbbitMQ之HelloWorld

1、消息队列 1、MQ的相关概念 1、什么是MQ MQ(message queue)&#xff0c;从字面意思上看&#xff0c;本质是个队列&#xff0c;FIFO 先入先出&#xff0c;只不过队列中存放的内容是message 而已&#xff0c;还是一种跨进程的通信机制&#xff0c;用于上下游传递消息。 在互联…
阅读更多...
webpack中的插件

webpack中的插件

1.webpack插件的作用通过安装和配置第三方插件，可以拓展webpack的能力，从而让webpack用起来更方便。最常用的webpack插件如下有两个：webpack-dev-server 类似于node.js阶段用到的nodemon工具 每当修改了源代码，webpack会自动进行项目的打包和构建html-webpack-pluginwebpac…
阅读更多...
（分布式缓存）Redis哨兵

（分布式缓存）Redis哨兵

对应的教程视频&#xff1a; 高级篇Day3-03-Redis哨兵_哔哩哔哩_bilibili 目录&#xff1a; 哨兵的作用和原理搭建哨兵集群RedisTemplate的哨兵模式 一、哨兵的作用和原理 二、搭建哨兵集群 1.集群结构 这里我们搭建一个三节点形成的Sentinel集群&#xff0c;来监管之前的Re…
阅读更多...
C++版本的OpenCV 5.x编译生成opencv-python==5.x(GPU版本)接口并进行调用

C++版本的OpenCV 5.x编译生成opencv-python==5.x(GPU版本)接口并进行调用

实现文章连接&#xff1a;强力推荐】基于Nvidia-Docker-Linux(Ubuntu18.04)平台&#xff1a;新版OpenCV5.x(C)联合CUDA11.1(GPU)完美配置视觉算法开发环境 目录1、关于有粉丝私信问我怎么调用的问题2、opencv5.x&#xff08;GPU&#xff09;测试成功opencv-python5.x测试代码Op…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业