哈希表（C语言）

2024-06-12 02:40| 来源: 网络整理| 查看: 265

哈希表

哈希表又称散列表，是一种是“key-value"形式存储的数据结构。即将key映射到表上的一个单元，从而实现快速查找等操作，这个映射操作就叫散列，具体通过散列函数实现相应的映射。根据key的形式，散列的形式多种多样，这里以正整数为例，常用的散列函数为： H a s h ( K e y ) = K e y % T a b l e S i z e Hash(Key) = Key \% TableSize Hash(Key)=Key%TableSize TableSize为表长，一般情况下，我们希望一个元素能唯一对应表上的一个单元，但是这是不可能的，一定会存在不同的Key映射到相同单元的情况，这就称为冲突，因此我们需要想办法解决冲突。首先，保证表长为素数可以一定程度减少冲突，使关键字的分配更均匀。最后，介绍两种常用的冲突解决方法，分离链接法（拉链法）和开放定址法。

分离链接法

分离链接法使用链表结构解决冲突，首先分配一个链表数组，当相应位置出现冲突时，创建一个新的哈希节点接在后面，看起来就像拉链一样。

相关例题：

1.LeetCode 706.设计哈希映射

在这里插入图片描述

代码如下：

#define TSize 1001 typedef struct{ int key; int value; struct HashNode *next; } HashNode; typedef struct { HashNode* HashTable; int TableSize; } MyHashMap; MyHashMap* myHashMapCreate() { MyHashMap* obj = (MyHashMap*)malloc(sizeof(MyHashMap)); obj->HashTable = (HashNode*)calloc(TSize, sizeof(HashNode)); obj->TableSize = TSize; for(int i = 0; i TableSize; i++){ obj->HashTable[i].next = NULL; } return obj; } void myHashMapPut(MyHashMap* obj, int key, int value) { int pos = key % obj->TableSize; HashNode* cur = (&obj->HashTable[pos])->next; //或者obj->HashTable[pos].next while(cur != NULL){ if(cur->key == key){ cur->value = value; return; } cur = cur->next; } //未找到相同的key，添加节点，头插法 HashNode* node = (HashNode*)malloc(sizeof(HashNode)); node->key = key; node->value = value; node->next = (&obj->HashTable[pos])->next; (&obj->HashTable[pos])->next = node; } int myHashMapGet(MyHashMap* obj, int key) { int pos = key % obj->TableSize; HashNode* cur = (&obj->HashTable[pos])->next; while(cur != NULL){ if(cur->key == key){ return cur->value; } cur = cur->next; } return -1; } void myHashMapRemove(MyHashMap* obj, int key) { int pos = key % obj->TableSize; HashNode* cur = (&obj->HashTable[pos])->next; while(cur != NULL){ if(cur->key == key){ cur->key = -1; //懒惰删除 return; } cur = cur->next; } } void myHashMapFree(MyHashMap* obj) { free(obj->HashTable); free(obj); }

2.LeetCode 49.字母异位词分组在这里插入图片描述这题考察了键为字符串的情况，我们使用一个简单的散列函数，即将每个字符的ASCII码的和模上表长即可。代码如下：

void StrSort(char* str, int slen){ //由于全是小写字母，就可以使用桶排序了 int buf[26] = {0}; for(int i = 0; i hashTable = (HashNode*)calloc(TSize, sizeof(HashNode)); for(int i = 0; i hashTable[i].next = NULL; } obj->TableSize = TSize; return obj; } int Insert(HashMap* obj, char* str, int slen){ //返回此字符串应该加入的位置 int Hashval = 0; char* tmp = (char*)calloc(slen + 1, sizeof(char)); strcpy(tmp, str); StrSort(tmp, slen); //如果是字母异位分词，排序后应该相同，哈希函数的值相同 for(int i = 0; i TableSize; HashNode* cur = (&obj->hashTable[pos])->next; while(cur != NULL){ if(strcmp(tmp, cur->key) == 0){ free(tmp); return cur->value; } cur = cur->next; } HashNode* node = (HashNode*)malloc(sizeof(HashNode)); node->key = (char*)calloc(slen + 1, sizeof(char)); strcpy(node->key, tmp); node->value = size++; node->next = (&obj->hashTable[pos])->next; (&obj->hashTable[pos])->next = node; free(tmp); return node->value; } char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){ *returnSize = 0; size = 0; *returnColumnSizes = (int*)calloc(strsSize, sizeof(int)); HashMap* obj = BuildHashMap(strsSize); char*** res = (char***)calloc(strsSize, sizeof(char**)); for(int i = 0; i TableSize = TSize; return obj; } void myHashSetAdd(MyHashSet* obj, int key){ int pos = key % obj->TableSize; for(int i = 0; ; i++){ int nextpos = (key + i * i) % obj->TableSize; if(obj->HashTable[nextpos] == -1){ obj->HashTable[nextpos] = key; break; } else if(obj->HashTable[nextpos] == key){ //如果已经有了就不插入了 break; } } } void myHashSetRemove(MyHashSet* obj, int key){ int pos = key % obj->TableSize; for(int i = 0; ; i++){ int nextpos = (key + i * i) % obj->TableSize; if(obj->HashTable[nextpos] == key){ obj->HashTable[nextpos] = -2; //懒惰删除，用-2标示 break; } else if(obj->HashTable[nextpos] == -1){ //未找到元素 break; } } } bool myHashSetContains(MyHashSet* obj, int key) { int pos = key % obj->TableSize; for(int i = 0; ; i++){ int nextpos = (key + i * i) % obj->TableSize; if(obj->HashTable[nextpos] == key){ return true; } else if(obj->HashTable[nextpos] == -1){ //未找到元素 return false; } } } void myHashSetFree(MyHashSet* obj) { free(obj->HashTable); free(obj); }

2.AcWing 1564.哈希

在这里插入图片描述

代码如下：

#include #include #include bool isPrime(int x){ if(x

【本文地址】

哈希表（C语言）

哈希表（C语言）

今日新闻

推荐新闻