C++哈希表詳解

一、C 哈希表模板

template 
class HashTable{
    private:
        struct Node{
            Key key;
            Value val;
            Node* next;
            Node(Key key,Value val,Node* next){
                this->key=key;
                this->val=val;
                this->next=next;
            }
        };
        int M;
        int size;
        Node** table;
        int hash(Key key){
            return (std::hash()(key) & 0x7fffffff) % M;
        }
        
    public:
        HashTable(int M){
            this->M=M;
            this->size=0;
            table=new Node*[M];
            for(int i=0;i<M;i++){
                table[i]=NULL;
            }
        }
        ~HashTable(){
            for(int i=0;inext;
                    delete temp;
                }
            }
            delete[] table;
        }
        int getSize(){
            return size;
        }
        void add(Key key,Value val){
            int index=hash(key);
            Node* cur=table[index];
            while(cur){
                if(cur->key==key){
                    cur->val=val;
                    return;
                }
                cur=cur->next;
            }
            Node* newNode=new Node(key,val,table[index]);
            table[index]=newNode;
            size++;
        }
        bool contains(Key key){
            int index=hash(key);
            Node* cur=table[index];
            while(cur){
                if(cur->key==key)
                    return true;
                cur=cur->next;
            }
            return false;
        }
        Value* get(Key key){
            int index=hash(key);
            Node* cur=table[index];
            while(cur){
                if(cur->key==key)
                    return &(cur->val);
                cur=cur->next;
            }
            return NULL;
        }
        void set(Key key,Value val){
            int index=hash(key);
            Node* cur=table[index];
            while(cur){
                if(cur->key==key){
                    cur->val=val;
                    return;
                }
                cur=cur->next;
            }
            throw std::invalid_argument("Key not exist");
        }
        Value remove(Key key){
            int index=hash(key);
            Node* cur=table[index];
            Node* prev=NULL;
            while(cur){
                if(cur->key==key){
                    if(!prev)
                        table[index]=cur->next;
                    else
                        prev->next=cur->next;
                    Value res=cur->val;
                    delete cur;
                    size--;
                    return res;
                }
                prev=cur;
                cur=cur->next;
            }
            throw std::invalid_argument("Key not exist");
        }
};

該哈希表支持泛型，其中 key 和 value 類型可以自行指定。哈希表使用鏈表解決哈希衝突問題，因為鏈表解決衝突的時間複雜度低，實現簡單。哈希表中的元素個數如果超出數組大小的一半，就調整數組大小，使數組大小成為原來大小的兩倍。如果元素個數小於數組大小的四分之一，就將數組大小減小到原來的一半，以防止浪費空間。在哈希表中最重要的是哈希函數，它決定了元素的分布情況，哈希函數的設計要盡量高效，盡量不會出現過多的衝突。

二、C 哈希表 遍歷

可以使用哈希表中的 getKeySet 和 getValueSet 函數，獲取哈希表中所有 key 和 value 的集合，然後遍歷一個個輸出。

int main(){
    HashTable table(10);
    table.add("a",1);
    table.add("b",2);
    table.add("c",3);

    std::unordered_set keySet;
    table.getKeySet(keySet);

    for(std::string key : keySet){
        std::cout<<key<<":"<<*(table.get(key))<<std::endl;
    }
    return 0;
}

三、C 哈希表接口

C++ 的哈希表接口跟 Java 的哈希表接口不一樣，在 C++ 中沒有實現 Map 接口。C++ 的 unordered_map 可以作為 Map，提供了 Map 的基本接口，不過其底層實現使用了哈希表。除了 Map 接口外，C++ 標準庫里還定義了 unordered_set 和 unordered_multiset、 unordered_multimap 等不同類型的哈希表。

四、C 哈希表頭文件

使用哈希表需要包含 C++ 標準庫中的unordered_map 頭文件，如下：

#include <unordered_map>
using namespace std;

五、哈希表在c中怎麼用

C 語言中沒有哈希表的數據類型，但是可以用鏈表實現一個哈希表來解決鍵值對的存儲和查找。C 語言的哈希表中的關鍵就是哈希函數，對於同一個鍵值，必須總是得出相同的哈希地址，否則無法找到該值。

六、哈希表C語言示例代碼

#include <stdio.h>
#include <string.h>

#define HASH_TABLE_SIZE 1024
  
struct hashtable_t {
    char* key;
    char* val;
  
    struct hashtable_t* next;
};

unsigned int hashtable_hash(struct hashtable_t* const hashtable, char* const key) {
    unsigned long int hashval = 0;
    unsigned int i = 0;
  
    while (hashval < ULONG_MAX && i < strlen(key)) {
        hashval = hashval << 8;
        hashval += key[i];
        i++;
    }
  
    return hashval % HASH_TABLE_SIZE;
}
  
  
struct hashtable_t* hashtable_newpair(char* key, char* value) {
    struct hashtable_t* newpair;
  
    if ((newpair = malloc(sizeof(struct hashtable_t)))==NULL) {
        return NULL;
    }
  
    if ((newpair->key = strdup(key))==NULL) {
        return NULL;
    }
  
    if ((newpair->val = strdup(value))==NULL) {
        return NULL;
    }
  
    newpair->next = NULL;
  
    return newpair;
}
  
  
void hashtable_set(struct hashtable_t* const hashtable, char* const key, char* const value) {
    int bin = 0;
    struct hashtable_t* newpair = NULL;
    struct hashtable_t* next = NULL;
    struct hashtable_t* last = NULL;
  
    bin = hashtable_hash(hashtable, key);
    next = hashtable->table[bin];
  
    while (next!=NULL && next->key!=NULL && strcmp(key, next->key) > 0) {
        last = next;
        next = next->next;
    }
  
    if (next!=NULL && next->key!=NULL && strcmp(key, next->key)==0) {
        free(next->val);
        next->val = strdup(value);
    } else {
        newpair = hashtable_newpair(key, value);
  
        if (next==hashtable->table[bin]) {
            newpair->next = next;
            hashtable->table[bin] = newpair;
        } else if (next==NULL) {
            last->next = newpair;
        } else {
            newpair->next = next;
            last->next = newpair;
        }
    }
}
  
  
char* hashtable_get(struct hashtable_t* const hashtable, char* const key) {
    int bin = 0;
    struct hashtable_t* pair;
  
    bin = hashtable_hash(hashtable, key);
  
    pair = hashtable->table[bin];
  
    while (pair!=NULL && pair->key!=NULL && strcmp(key, pair->key) > 0) {
        pair = pair->next;
    }
  
    if (pair==NULL || pair->key==NULL || strcmp(key, pair->key)!=0) {
        return NULL;
    } else {
        return pair->val;
    }
}
  
int main(int argc, char **argv) {
    struct hashtable_t* hashtable = NULL;
    char* str = NULL;
  
    hashtable = calloc(1, sizeof(struct hashtable_t*));
    hashtable->table = calloc(HASH_TABLE_SIZE, sizeof(struct hashtable_t*));
  
    hashtable_set(hashtable, "key1", "inky");
    hashtable_set(hashtable, "key2", "pinky");
    hashtable_set(hashtable, "key3", "blinky");
    hashtable_set(hashtable, "key4", "floyd");
  
    printf("%s\n", hashtable_get(hashtable, "key1"));
    printf("%s\n", hashtable_get(hashtable, "key2"));
    printf("%s\n", hashtable_get(hashtable, "key3"));
    printf("%s\n", hashtable_get(hashtable, "key4"));

    return 0;
}

本文詳細介紹了哈希表在C++中的應用，包括C++哈希表模板、C++哈希表遍歷、C++哈希表頭文件、C++哈希表接口等方面的內容。同時，本文還介紹了如何用C語言實現哈希表，並給出了示例代碼，可以幫助讀者更好地理解哈希表的原理和應用。哈希表是一個非常重要的數據結構，廣泛應用於各種算法和程序設計中。希望讀者通過本文的學習，能夠對哈希表有更深入的認識，進一步提高自己的程序設計能力。