宝塔服务器面板,一键全能部署及管理,送你10850元礼包,点我领取
一、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语言实现哈希表,并给出了示例代码,可以帮助读者更好地理解哈希表的原理和应用。哈希表是一个非常重要的数据结构,广泛应用于各种算法和程序设计中。希望读者通过本文的学习,能够对哈希表有更深入的认识,进一步提高自己的程序设计能力。
最新评论