c语言实现哈希表的核心在于设计高效的哈希函数与解决冲突的方法。1. 哈希函数应尽量均匀分布键值，减少冲突，常用方法包括除法哈希、乘法哈希、全域哈希和字符串哈希（如djb2）。2. 冲突解决主要有链地址法和开放寻址法：链地址法通过链表存储冲突元素，实现简单但需额外空间；开放寻址法通过探测空位插入，节省空间但实现复杂，包括线性探测、二次探测和双重哈希。3. 哈希表大小通常选质数以减少冲突，结合负载因子（建议0.7左右）判断扩容时机。4. 扩容时创建更大哈希表并重新哈希所有键，提升性能但代价较高。综上，实现需综合考虑键类型、性能需求与内存限制。
哈希表本质上是一种键值对存储的数据结构，C语言实现哈希表，核心在于哈希函数的设计和冲突的解决。选择合适的哈希函数能直接影响哈希表的性能，而解决冲突则保证了即使不同的键映射到相同的位置，也能正确存储和检索数据。
哈希表是一种通过哈希函数将键（Key）映射到表中一个位置来访问记录的数据结构，查找速度快。
C语言实现哈希表主要包括以下几个步骤：
立即学习“C语言免费学习笔记（深入）”；
定义哈希表结构： 包括存储数据的数组（或链表数组），以及哈希表的大小。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义键值对结构
typedef struct {
char* key;
void* value;
} KeyValuePair;
// 定义哈希表节点结构 (用于链地址法解决冲突)
typedef struct HashNode {
KeyValuePair pair;
struct HashNode* next;
} HashNode;
// 定义哈希表结构
typedef struct {
int capacity; // 哈希表容量
HashNode** table; // 指向HashNode指针的指针，相当于HashNode* 数组
} HashTable;
实现哈希函数： 哈希函数将键转换为数组的索引。一个好的哈希函数应该尽量减少冲突。
// 一个简单的哈希函数示例 (DJB2算法)
unsigned long hash(char *str) {
unsigned long hash = 5381;
int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
// 根据哈希值获取索引
int getIndex(HashTable* ht, char* key) {
unsigned long hashValue = hash(key);
return hashValue % ht->capacity;
}
实现哈希表操作： 包括创建、插入、查找和删除。
// 创建哈希表
HashTable* createHashTable(int capacity) {
HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
if (ht == NULL) {
perror("Failed to allocate memory for hash table");
exit(EXIT_FAILURE);
}
ht->capacity = capacity;
ht->table = (HashNode**)calloc(capacity, sizeof(HashNode*));
if (ht->table == NULL) {
perror("Failed to allocate memory for hash table buckets");
free(ht);
exit(EXIT_FAILURE);
}
return ht;
}
// 插入键值对
void insert(HashTable* ht, char* key, void* value) {
int index = getIndex(ht, key);
// 创建新的键值对和节点
KeyValuePair newPair;
newPair.key = strdup(key); // 复制key，避免外部修改影响哈希表
newPair.value = value;
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
if (newNode == NULL) {
perror("Failed to allocate memory for new node");
exit(EXIT_FAILURE);
}
newNode->pair = newPair;
newNode->next = NULL;
// 链地址法解决冲突
if (ht->table[index] == NULL) {
ht->table[index] = newNode;
} else {
newNode->next = ht->table[index];
ht->table[index] = newNode;
}
}
// 查找键对应的值
void* search(HashTable* ht, char* key) {
int index = getIndex(ht, key);
HashNode* current = ht->table[index];
while (current != NULL) {
if (strcmp(current->pair.key, key) == 0) {
return current->pair.value;
}
current = current->next;
}
return NULL; // 未找到
}
// 删除键值对 (简化版，不释放value指向的内存)
void delete(HashTable* ht, char* key) {
int index = getIndex(ht, key);
HashNode* current = ht->table[index];
HashNode* prev = NULL;
while (current != NULL) {
if (strcmp(current->pair.key, key) == 0) {
if (prev == NULL) {
// 删除的是链表头节点
ht->table[index] = current->next;
} else {
prev->next = current->next;
}
free(current->pair.key); // 释放复制的key
free(current);
return;
}
prev = current;
current = current->next;
}
}
// 释放哈希表内存
void freeHashTable(HashTable* ht) {
if (ht == NULL) return;
for (int i = 0; i < ht->capacity; i++) {
HashNode* current = ht->table[i];
while (current != NULL) {
HashNode* temp = current;
current = current->next;
free(temp->pair.key); // 释放复制的key
free(temp);
}
}
free(ht->table);
free(ht);
}
处理冲突： 常见的冲突解决方法包括链地址法和开放寻址法。上面的代码示例使用了链地址法。
// (链地址法已经在上面的 insert 函数中实现) // 开放寻址法示例 (线性探测) - 不推荐，容易导致聚集 // 插入时，如果位置被占用，则探测下一个位置，直到找到空位 // 查找时，如果位置的键不匹配，则继续探测，直到找到匹配的键或空位
哈希函数的目标是将任意大小的键转换为固定大小的哈希值，理想情况下，它应该均匀地分布键，以减少冲突。常见的哈希函数设计方法包括：
h(k) = k mod m，其中 k 是键，m 是哈希表的大小。选择 m 时，通常避免选择2的幂，因为如果 m 是2的幂，哈希值将仅仅依赖于 k 的最低几位。选择质数作为 m 通常是一个好选择。h(k) = floor(m * (k * A mod 1))，其中 A 是一个常数，0 < A < 1。Knuth 建议使用 A ≈ (sqrt(5) - 1) / 2 = 0.6180339887...。选择哈希函数时，需要考虑键的类型和分布。例如，如果键是整数，除法哈希或乘法哈希可能是一个不错的选择。如果键是字符串，DJB2 或 FNV-1a 可能更合适。
哈希冲突是指不同的键被哈希函数映射到哈希表的同一个位置。解决冲突对于哈希表的性能至关重要。常见的冲突解决方法包括：
链地址法（Separate Chaining）：
开放寻址法（Open Addressing）：
h(k, i) = (h'(k) + i) mod m。容易导致聚集（clustering），即连续的位置被占用，降低查找效率。h(k, i) = (h'(k) + c1*i + c2*i^2) mod m。可以减少聚集，但如果哈希表几乎满了，仍然可能找不到空位。h(k, i) = (h1(k) + i*h2(k)) mod m。是解决聚集的有效方法。再哈希法（Rehashing）：
选择冲突解决方法时，需要权衡空间和时间效率。链地址法通常更容易实现，并且在负载因子较高时也能保持较好的性能。开放寻址法可以节省空间，但在负载因子接近 1 时性能会下降。双重哈希是开放寻址法中一种有效的解决方案，可以减少聚集。
哈希表的大小直接影响其性能。如果哈希表太小，会导致大量的冲突，降低查找效率。如果哈希表太大，会浪费内存。一个好的哈希表大小应该能够平衡空间和时间效率。
选择合适的哈希表大小：
哈希表的扩容：
当哈希表中的键的数量超过了哈希表大小乘以负载因子时，就需要进行扩容。扩容的过程包括：
扩容是一个耗时的操作，因为它需要重新哈希所有键。为了减少扩容的频率，可以选择一个较大的初始哈希表大小，并设置一个合适的负载因子。
// 扩容哈希表
void resizeHashTable(HashTable* ht) {
int oldCapacity = ht->capacity;
HashNode** oldTable = ht->table;
// 新容量选择一个质数 (这里简化处理，直接翻倍)
int newCapacity = oldCapacity * 2;
ht->capacity = newCapacity;
ht->table = (HashNode**)calloc(newCapacity, sizeof(HashNode*));
if (ht->table == NULL) {
perror("Failed to allocate memory for resized hash table");
exit(EXIT_FAILURE);
}
// 重新哈希所有键
for (int i = 0; i < oldCapacity; i++) {
HashNode* current = oldTable[i];
while (current != NULL) {
HashNode* next = current->next;
int newIndex = getIndex(ht, current->pair.key); // 使用新的容量计算索引
// 插入到新的哈希表 (链地址法)
current->next = ht->table[newIndex];
ht->table[newIndex] = current;
current = next;
}
}
// 释放旧哈希表的内存
free(oldTable);
}
// 在插入时检查是否需要扩容
void insert(HashTable* ht, char* key, void* value) {
// ... (之前的插入代码) ...
// 检查是否需要扩容 (例如，当键的数量超过容量的75%时)
int currentSize = 0;
for(int i = 0; i < ht->capacity; i++){
HashNode* node = ht->table[i];
while(node != NULL){
currentSize++;
node = node->next;
}
}
if ((float)currentSize / ht->capacity > 0.75) {
resizeHashTable(ht);
}
}
总而言之，C语言实现哈希表需要仔细考虑哈希函数的设计、冲突的解决、哈希表大小的选择和扩容策略。选择合适的方案取决于具体的应用场景和性能需求。
以上就是C语言中如何实现哈希表 C语言哈希函数设计与冲突解决方法的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
178
收藏
