HashMap - 簡書

我們通常使用的dict刮萌、map基本都是hashmap,表現(xiàn)形式就是key-value鍵值對的形式，如下圖：

我們可以使用鏈表或者數(shù)組的方式實現(xiàn)這個功能，但是他們各自有各自的的優(yōu)缺點
數(shù)組：尋址容易，但是增加刪除太麻煩婿禽，每次都要整體移動很多數(shù)據(jù)
鏈表：增減刪除簡單，只需要改變next指針的指向大猛，但是尋址麻煩

所以hashmap采用的是數(shù)組+鏈表的方式：

HashMap.png

實現(xiàn)原理：

通過開辟一定數(shù)量的數(shù)組空間bucket扭倾，數(shù)組里的指針指向一個鏈表，當(dāng)輸入key時挽绩，通過計算hashCode,然后對數(shù)組空間數(shù)量取模膛壹，來獲取數(shù)組bucket的index:即index = key.hash % capacity; 其中capacity就是數(shù)組的數(shù)量（如上圖的數(shù)量是10）。為什么bucket里的指針指向的是一個鏈表呢?是因為兩個key的hash值在取模之后有可能是一樣的琼牧。這種情況就將bucketIndex一樣的key恢筝，放在同一個鏈表上。

talk is cheap ,show me the code

struct Node{
    char * key; 
    void * value;
    struct Node * next; //指向下一個Node地址或者null
};

struct HashMap{
    //容量 (是容量巨坊，指的是bucketArr數(shù)組的的數(shù)量撬槽，不是key-value的數(shù)量)
    int capacity;
    //bucket array
    struct Node ** bucketArr;
    //添加key-value
    void(*add)(struct Node ** bucketArr,int capacity, char * key,void * value);
    //移除key-value
    void(*remove)(struct Node ** bucketArr,int capacity,char * key);
    //根據(jù)key獲取value的值
    void *(*get)(struct Node ** bucketArr,int capacity,char * key);
};

//根據(jù)key,通過hash，然后計算出index
int getBucketIndex(char * key,int capacity){
    unsigned long hashCode = [NSString stringWithFormat:@"%s",key].hash;
    return hashCode%capacity;
}

//添加bucket的index指向的鏈表中
void addKeyValue(struct Node ** bucketArr,int capacity, char * key,void * value){
    if(!key)return;
    int index = getBucketIndex(key, capacity);
    struct Node * head = bucketArr[index];
   //循環(huán)遍歷Node
    while (head!=NULL) {
        //如果鏈表中的Node存在相同key,直接替換value
        if(!strcmp(head->key, key)){
            head->next = value;
            return;
        }
        head = head->next;
    }
 
    //生成新node
    struct Node * newNode = malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;
    //鏈表為空時
    if(head==NULL){
        bucketArr[index] = newNode;
    }else{
        //鏈表不為空時趾撵，將新的node的next指向原來的head,然后再將指向新node 地址的指針保存到bucket中侄柔。
        newNode->next = bucketArr[index];;
        bucketArr[index] = newNode;
    }
    
    //擴容(根據(jù)實際情況自定義，當(dāng)keyvalue數(shù)量過多占调，增加capaity)
    //TODO 暫時就不實現(xiàn)了
}

//移除bucket的index指向的鏈表中的特定key
void removeKey(struct Node ** bucketArr,int capacity,char * key){
    if(!key)return;
    int index = getBucketIndex(key, capacity);
    struct Node * head = bucketArr[index];
    struct Node * pre = NULL;
    struct Node * removeNode = NULL;
    //查找bucketIndex指向的鏈表中是否有對應(yīng)的key
     while (head!=NULL) {
         if(!strcmp(head->key, key)){
             removeNode = head;
             break;
         }
         //往后查找
         pre = head;
         head = head->next;
     }
    
    //說明鏈表中沒有對應(yīng)的要刪除的Node
    if(removeNode==NULL){
        return;
    }
    
    //說明不是鏈表頭結(jié)點
    if(pre!=NULL){
        pre->next = head->next;
    }
    //鏈表頭結(jié)點
    else{
        bucketArr[index] = head->next;
    }
}

//根據(jù)key獲取value的值
void * getKeyValue(struct Node ** bucketArr,int capacity,char * key){
    if(!key) return NULL;
    int index = getBucketIndex(key, capacity);
    struct Node * head = bucketArr[index];
    while (head!=NULL) {
        if(!strcmp(head->key, key)){
            return head->value;
            break;
        }
        head = head->next;
    }
    return NULL;
}


int main(int argc,char *argv[]){
    struct HashMap * hashMap = malloc(sizeof(struct HashMap));
    hashMap->capacity = 10;
    struct Node * nodeArr[10] = {0};
    hashMap->bucketArr = nodeArr;
    hashMap->add = addKeyValue;
    hashMap->remove = removeKey;
    hashMap->get = getKeyValue;
    //驗證
    char * key1 = "姓名1";
    char * key2 = "姓名2";
    char * key3 = "姓名3";
    hashMap->add(hashMap->bucketArr, hashMap->capacity, key1, @"王二牛");
    hashMap->add(hashMap->bucketArr, hashMap->capacity, key2, @"王大牛");
    hashMap->add(hashMap->bucketArr, hashMap->capacity, key3, @"王老牛");
    
    char * keys[3] = {key1,key2,key3};
    for(int i=0;i<3;i++){
        NSString * value = (__bridge NSString *)hashMap->get(hashMap->bucketArr,hashMap->capacity,keys[i]);
        NSLog(@"%s:%@",keys[i],value);
    }
/*
2020-09-14 08:32:07.696646+0800 Test[11948:327436] 姓名1:王二牛
2020-09-14 08:32:07.698029+0800 Test[11948:327436] 姓名2:王大牛
2020-09-14 08:32:07.698129+0800 Test[11948:327436] 姓名3:王老牛
能驗證get set功能
*/    

    hashMap->remove(hashMap->bucketArr, hashMap->capacity, key1);
    for(int i=0;i<3;i++){
        NSString * value = (__bridge NSString *)hashMap->get(hashMap->bucketArr,hashMap->capacity,keys[i]);
        NSLog(@"%s:%@",keys[i],value);
    }
    
/*
2020-09-14 08:32:07.698210+0800 Test[11948:327436] 姓名1:(null)
2020-09-14 08:32:07.698289+0800 Test[11948:327436] 姓名2:王大牛
2020-09-14 08:32:07.698364+0800 Test[11948:327436] 姓名3:王老牛
能驗證remove set功能
*/

//TODO: free object 釋放堆上創(chuàng)建的對象

    return 1;
}

這里說一下小插曲暂题，add方法中的struct Node * newNode = malloc(sizeof(struct Node))新生成一個對象這個地方，我調(diào)用兩次add方法究珊，每次返回的Node的地址都是一樣薪者，導(dǎo)致后面add的key-value會將前面的值覆蓋掉。應(yīng)該是方法棧執(zhí)行完后剿涮，棧對象被回收言津，導(dǎo)致每次調(diào)用alloc返回的都是同一個地址。后來改用malloc在堆上開辟空間取试，這樣悬槽，就得手動調(diào)用free來釋放對象。

總結(jié)：

HashMap是通過數(shù)組+鏈表的方式實現(xiàn)快速的增加瞬浓、刪除初婆、獲取等方法
增加：通過key的hash值對bucket數(shù)量取模，來獲取index,進而獲取單向鏈表，判斷當(dāng)鏈表中沒有Node的key與新增的key相同磅叛，如果有則直接替換value屑咳。如果沒有，則創(chuàng)建一個新的Node,新Node的next指向原來鏈表的Head弊琴，并將bucket的index指向新的Node的地址乔宿。
刪除：通過key的hash值對bucket數(shù)量取模，來獲取index,進而獲取單向鏈表访雪。然后遍歷鏈表，遍歷Node沒有相同key掂林，則直接退出臣缀，如果有Node的key相等，若是頭結(jié)點則直接直接將bucketIndex指向head->next泻帮，若不是頭結(jié)點精置，則將pre->next指向head->next來實現(xiàn)刪除node結(jié)點。
獲取：找到bucketIndex指向的鏈表锣杂，然后遍歷鏈表脂倦，根據(jù)key找到對應(yīng)的Node,然后返回value值。找不到返回null元莫。
通過上面的實現(xiàn)赖阻，我們自然而然的也就理解了為什么hashmap是無序的了。