資料結構_哈希表

散清單（Hash table，也叫哈希表），是根據鍵（Key）而直接通路在記憶體存儲位置的資料結構。 也就是說，它通過計算一個關于鍵值的函數，将所需查詢的資料映射到表中一個位置來通路記錄，這加快了查找速度。 這個映射函數稱做散列函數，存放記錄的數組稱做散清單。

hash沖突發生的情況是指存在兩個值的hashCode相同。

連結清單法又稱拉鍊法，作用是把具有相同散列位址的關鍵字(同義詞)值放在同一個單連結清單中，稱為同義詞連結清單。代碼中使用一個清單，儲存所有hashcode相同的值。

//哈希表 的實作

#include <iostream>

using namespace std;

typedef struct node{

    struct node *next;

    int key;

}Node;

typedef struct {

    Node *head;

}HashTable;

void insertHT(HashTable hash[],int &n,int p,int k){

    int index=k%p;

    Node *q=new Node;

    q->next=NULL;

    q->key=k;

    if(hash[index].head==NULL)

        hash[index].head=q;

    else{

        q->next=hash[index].head;

        hash[index].head=q;

    }

    n++;

}

void createHash(HashTable hash[],int &n,int m,int p,int keys[],int n1){

    for(int i=0;i<m;i++){

        hash[i].head==NULL;

    }

    n=0;

    for(int i=0;i<n1;i++)

        insertHT(hash,n,p,keys[i]);

}

bool deleteHash(HashTable hash[],int &n,int m,int p,int key){

    int index=key%p;

    Node* q=NULL,*pre=NULL;

    q=hash[index].head;

    if(q==NULL)

        return false;

    while(q!=NULL){

        if(q->key==key)

        {

            break;

        }

        pre=q;

        q=q->next;

    }

    if(q!=NULL){

        if(pre==NULL){

            Node* tmp=q;

            hash[index].head=tmp->next;

            delete tmp;

            n--;

            return true;

        }else{

            pre->next=q->next;

            delete q;

            n--;

            return true;

        }

    }

    return false;

}

bool searchHash(HashTable hash[],int p,int key){

    Node* q;

    int index=key%p;

    q=hash[index].head;

    while(q!=NULL){

        if(q->key==key)

            break;

        q=q->next;

    }

    if(q!=NULL)

        return true;

    else

        return false;

}

int main(){

    int temp[200];

    HashTable table[100];

    int n=0;

    for(int i=0;i<100;i++)

        temp[i]=i;

    createHash(table,n,100,23,temp,100);

    for(int i=0;i<5;i++){

        cout<<searchHash(table,23,i)<<" ";

    }

    cout<<searchHash(table,23,150)<<" ";

}

本文參考連結及學習資料：

【1】https://github.com/Clayygou/Datawhale-6-programming/blob/master/Task4/%E6%95%A3%E5%88%97%E8%A1%A8%EF%BC%88%E5%93%88%E5%B8%8C%E8%A1%A8%EF%BC%89/1%E3%80%81%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AA%E5%9F%BA%E4%BA%8E%E9%93%BE%E8%A1%A8%E6%B3%95%E8%A7%A3%E5%86%B3%E5%86%B2%E7%AA%81%E9%97%AE%E9%A2%98%E7%9A%84%E6%95%A3%E5%88%97%E8%A1%A8.md

【2】https://github.com/kele1997/talk_is_cheap/blob/master/data_structure/hashtable/hash_table.cpp