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