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
    next;
                    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<
    <<":"<<*(table.get(key))<
     


      
三、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语言实现哈希表，并给出了示例代码，可以帮助读者更好地理解哈希表的原理和应用。哈希表是一个非常重要的数据结构，广泛应用于各种算法和程序设计中。希望读者通过本文的学习，能够对哈希表有更深入的认识，进一步提高自己的程序设计能力。