一、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语言实现哈希表，并给出了示例代码，可以帮助读者更好地理解哈希表的原理和应用。哈希表是一个非常重要的数据结构，广泛应用于各种算法和程序设计中。希望读者通过本文的学习，能够对哈希表有更深入的认识，进一步提高自己的程序设计能力。
原创文章，作者：STMQX，如若转载，请注明出处：https://www.506064.com/n/370781.html
微信扫一扫 
支付宝扫一扫 