typedef struct entry {
    char * key;             // 鍵
    void * value;           // 值
    struct entry * next;    // 沖突鏈表
} Entry;

typedef int boolean;//定義一個(gè)布爾類(lèi)型
#define TRUE 1
#define FALSE 0
// 哈希表結(jié)構(gòu)體
typedef struct hashMap {
    int size;           // 集合元素個(gè)數(shù)
    int capacity;       // 容量
    int nodeLen;       //節(jié)點(diǎn)長(zhǎng)度
    Entry **list;         // 存儲(chǔ)區(qū)域
    int dilatationCount;  //擴(kuò)容次數(shù)
    int dilatationSum;  //擴(kuò)容總次數(shù)

} HashMap;

// 迭代器結(jié)構(gòu)
typedef struct hashMapIterator {
    Entry *nextEntry;// 迭代器當(dāng)前指向
    int count;//迭代次數(shù)
    HashMap *hashMap;
    int index; //位置
}HashMapIterator;

//最好的char類(lèi)型的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值長(zhǎng)度取模最后獲取實(shí)際位置的下標(biāo)
static  unsigned int defaultHashCode(HashMap hashMap, char * key){
    return BKDRHash(key)% hashMap.capacity;
}

HashMap *createHashMap(int capacity) {
    //創(chuàng)建哈希表
    HashMap *hashMap= (HashMap *)malloc(sizeof(HashMap));
    //創(chuàng)建存儲(chǔ)區(qū)域
    if(capacity<10){
        capacity=10;
    }
    hashMap->size=0;
    hashMap->dilatationCount=0;
    hashMap->dilatationSum=0;
    hashMap->nodeLen=0;
    hashMap->capacity=capacity;
    hashMap->list = (Entry **)calloc(capacity,sizeof(Entry));
    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>=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;
}

//擴(kuò)容Map集合
static  void dilatationHash(HashMap *hashMap){
    //原來(lái)的容量
    int capacity = hashMap->capacity;
    //擴(kuò)容后的容量
    hashMap->capacity=expansionBase(hashMap);
    //節(jié)點(diǎn)長(zhǎng)度清空
    hashMap->nodeLen=0;
    //創(chuàng)建新的存儲(chǔ)區(qū)域
    Entry **newList=(Entry **)calloc(hashMap->capacity,sizeof(Entry));
    //遍歷舊的存儲(chǔ)區(qū)域,將舊的存儲(chǔ)區(qū)域的數(shù)據(jù)拷貝到新的存儲(chǔ)區(qū)域
    for(int i=0;i<capacity;i++){
        Entry *entry=hashMap->list[i];
        if(entry!=NULL){
            //獲取新的存儲(chǔ)區(qū)域的下標(biāo)
            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{//那么就是沖突鏈表添加鏈表節(jié)點(diǎn)
                Entry *newEntry = (Entry *)malloc(sizeof(Entry));
                newEntry->key = entry->key;
                newEntry->value = entry->value;
                //將新節(jié)點(diǎn)插入到鏈表頭部(這樣的好處是插入快,但是不能保證插入的順序)
                newEntry->next = newList[newIndex];
                newList[newIndex] = newEntry;
            }
            //判斷節(jié)點(diǎn)內(nèi)鏈表是否為空
            if(entry->next!=NULL){
                //遍歷鏈表,將鏈表節(jié)點(diǎn)插入到新的存儲(chǔ)區(qū)域
                Entry *nextEntry=entry->next;
                while(nextEntry!=NULL){
                    //獲取新的存儲(chǔ)區(qū)域的下標(biāo)
                    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{//那么就是沖突鏈表添加鏈表節(jié)點(diǎn)
                        Entry *newEntry = (Entry *)malloc(sizeof(Entry));
                        newEntry->key = nextEntry->key;
                        newEntry->value = nextEntry->value;
                        //將新節(jié)點(diǎn)插入到鏈表頭部(這樣的好處是插入快,但是不能保證插入的順序)
                        newEntry->next = newList[newIndex];
                        newList[newIndex] = newEntry;
                    }
                    nextEntry=nextEntry->next;
                }
            }
        }
    }
    //釋放舊的存儲(chǔ)區(qū)域
    free(hashMap->list);
    //將新的存儲(chǔ)區(qū)域賦值給舊的存儲(chǔ)區(qū)域
    hashMap->list=newList;
}

void putHashMap(HashMap *hashMap, char *key, void *value) {
    //判斷是否需要擴(kuò)容
    if(hashMap->nodeLen==hashMap->capacity){
        dilatationHash(hashMap);
    }
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];

    //如果節(jié)點(diǎn)是空的那么直接添加
    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;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要添加到鏈表中
    //添加前需要先判斷鏈表中是否存在該鍵
    while (entry != NULL) {
        //如果存在該鍵,那么更新值
        if (strcmp(entry->key, key) == 0) {
            entry->value = value;
            return;
        }
        entry = entry->next;
    }
    //如果鏈表中不存在,那么就創(chuàng)建新的鏈表節(jié)點(diǎn)
    Entry *newEntry = (Entry *)malloc(sizeof(Entry));
    newEntry->key = key;
    newEntry->value = value;
    //將新節(jié)點(diǎn)插入到鏈表頭部(這樣的好處是插入快,但是不能保證插入的順序)
    newEntry->next = hashMap->list[hashCode];
    hashMap->list[hashCode] = newEntry;
    hashMap->size++;

}

void printHashMap(HashMap *hashMap) {
    for (int i = 0; i < hashMap->capacity; i++) {
        Entry *entry = hashMap->list[i];
        while (entry != NULL) {
            printf("%s:%s\n", entry->key, entry->value);
            entry = entry->next;
        }
    }
}

void *getHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];
    //如果節(jié)點(diǎn)是空的那么直接返回
    if(entry==NULL){
        return NULL;
    }
    //判斷是否存在該鍵,并且一樣的話,返回值
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        return entry->value;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要查詢(xún)鏈表
    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);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];
    //如果節(jié)點(diǎn)是空的那么直接返回FALSE
    if(entry==NULL){
        return FALSE;
    }
    //判斷是否存在該鍵,并且一樣的話,返回TRUE
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        return TRUE;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要查詢(xún)鏈表
    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 < hashMap->capacity; i++) {
        Entry *entry = hashMap->list[i];//獲取節(jié)點(diǎn)
        while (entry != NULL) {
            if (entry->value == value) {//如果找到該值,那么返回TRUE
                return TRUE;
            }
            entry = entry->next;//否則查詢(xún)節(jié)點(diǎn)鏈表內(nèi)部
        }
    }
    return FALSE;
}

void removeHashMap(HashMap *hashMap, char *key) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];
    //如果節(jié)點(diǎn)是空的那么直接返回
    if(entry==NULL){
        return;
    }
    //判斷是否存在該鍵,并且一樣的話,刪除該節(jié)點(diǎn)
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        hashMap->list[hashCode] = entry->next;
        free(entry);
        hashMap->size--;
        return;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要查詢(xún)鏈表
    while (entry != NULL) {
        //如果找到該鍵,那么刪除該節(jié)點(diǎn)
        if (strcmp(entry->key, key) == 0) {
            Entry *next = entry->next;
            entry->next = next->next;
            free(next);
            hashMap->size--;
            return;
        }
        entry = entry->next;
    }
}

void updateHashMap(HashMap *hashMap, char *key, void *value) {
    //獲取hash值
    unsigned int hashCode = defaultHashCode(*hashMap, key);
    //獲取節(jié)點(diǎn)
    Entry *entry = hashMap->list[hashCode];
    //如果節(jié)點(diǎn)是空的那么直接返回
    if(entry==NULL){
        return;
    }
    //判斷是否存在該鍵,并且一樣的話,修改該節(jié)點(diǎn)的值
    if(entry->key !=NULL && strcmp(entry->key,key)==0){
        entry->value = value;
        return;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空,而且key不一樣,那么表示hash沖突了,需要查詢(xún)鏈表
    while (entry != NULL) {
        //如果找到該鍵,那么修改該節(jié)點(diǎn)的值
        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;//迭代次數(shù)
    hashMapIterator->index= 0;//迭代位置
    hashMapIterator->nextEntry= NULL;//下次迭代節(jié)點(diǎn)

    return hashMapIterator;
}
boolean hasNextHashMapIterator(HashMapIterator *iterator){
    return iterator->count < iterator->hashMap->size ? TRUE : FALSE;
}
Entry *nextHashMapIterator(HashMapIterator *iterator) {
    if (hasNextHashMapIterator(iterator)) {
        //如果節(jié)點(diǎn)中存在hash沖突鏈表那么就迭代鏈表
        if(iterator->nextEntry!=NULL){//如果下次迭代節(jié)點(diǎn)不為空,那么直接返回下次迭代節(jié)點(diǎn)
            Entry *entry = iterator->nextEntry;
            iterator->nextEntry = entry->next;
            iterator->count++;
            return entry;
        }

        Entry *pEntry1 = iterator->hashMap->list[iterator->index];
        //找到不是空的節(jié)點(diǎn)
        while (pEntry1==NULL){
            pEntry1 = iterator->hashMap->list[++iterator->index];
        }
        //如果沒(méi)有hash沖突節(jié)點(diǎn),那么下次迭代節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)向后繼續(xù)搜索
        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 ,返回一個(gè)自定義的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,返回一個(gè)自定義的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;
}

HashMap *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;
}

//將一個(gè)map集合,合并到另一個(gè)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);
    }
}

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

//差集,返回一個(gè)新的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;
}

//交集,返回一個(gè)新的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;
}

//補(bǔ)集,返回一個(gè)新的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;
}

void hashMapClear(HashMap *hashMap){
    for (int i = 0; i < hashMap->nodeLen; i++) {
        // 釋放沖突值內(nè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);
        }
    }
    // 釋放存儲(chǔ)空間
    free(hashMap->list);
    free(hashMap);
}