Hash Table

雜湊表

1.鄰接串列實作
2.用%來重新定義範圍

定義結構:

typedef struct hash{
    int key;
    int val;
     struct hash *next;
}hash;

hash hashTable[1024];

Hash Funtion=

key=hashFuntion(x);

int HashFuntion(int x){
    return x & 1023;//=X/1024
}

新增

void insert(int key,int val){
    hash *node=malloc(sizeof(hash));
    node->val=val;
    node->key=key;
    node->next=NULL;
    hash *p=&hashTable[HashFuntion(key)];
    while(p->next!=NULL){
        p=p->next;
    }
    p->next=node;
}

查詢

int query(int key){
    hash *p=&hashTable[HashFuntion(key)];
    while(p!=NULL){
        if(p->key==key) return p->val;
        p=p->next;
    }
    return -1;
}

刪除

void delet(int key){
    hash *p=&hashTable[HashFuntion(key)];
    if(p->next->key==key){
        hash *next=p->next->next;
        free(p->next);
        p->next=next;
        return;
    }
    p=p->next;
    while(p->next->next!=NULL&&p->next->key!=key){
        p=p->next;
    }
    hash *next=p->next->next;
    free(p->next);
    p->next=next;
}

更C++版本

#include <unordered_map>

int top=0;
unordered_map<string,int> m;

int hashfunction(string str){ //回傳對應到的特定值
    auto reault=m.find(str);
    if(result!=m.end()){
        return result->second;
    }else{
        m[str]=top++;
        return top-1;
    }
}

int main(){
    int arr[1000]={0};
    
    string target="abc";
    int index=hashfunction(target);
    arr[index]++;
    
    return 0;
}