本文详细介绍了哈希表的数据结构，包括键值对的定义、如何通过哈希函数确定数组下标、以及如何使用链地址法解决哈希冲突。还涵盖了插入、查找和删除操作，以及哈希表的完整生命周期管理。
摘要由CSDN通过智能技术生成
哈希表实现了“键key——值value”这一映射关系的存储。每个值对应唯一的键，一个键可以对应多个值。
在哈希表在插入、删除、查找一个元素都只需要O（1）的时间复杂度，所以哈希表常常用来优化时间效率，在基础数据结构中，数组满足O（1）时间复杂度，所以哈希表可以考虑使用‘数组’实现。
由于每个值唯一对应一个键，需要通过键来查找特定的值，因此一个值和它唯一对应的键是同时存储的，称为‘键值对’。下图定义了一个键值对结构体：
//定义哈希表的节点结构（叫节点是因为键值对用链表存储在数组中） typedef struct HashNode { char* key; int value; struct HashNode* next; // 指向下一个节点的指针，用来解决哈希冲突 } HashNode;
所以在数组中存储‘键值对’时，使用‘键’来确定键值对在数组中的下标。
下图为数组实现的哈希表结构：
// 哈希表结构 typedef struct { HashNode* array[TABLE_SIZE]; // 哈希表的桶数组 } HashTable;
将键转换成数组下标的过程：将键转换成整数（即哈希值），哈希值对数组长度求余，得到的余数为数组的下标。
键如果是英文或中文字符，则通过ASCII或Unicode转换成整数（即哈希值）。
// 哈希函数，这里简单地将键转换为整数然后取余 int hash(char* key) { int hashValue = 0; int len = strlen(key); for (int i = 0; i < len; i++) { hashValue = (hashValue << 5) + key[i]; } return hashValue % TABLE_SIZE; }
因此这样的转换方式会出现多个键具有相同的哈希值，即出现多个键值对需要存储到数组的同一个位置，很显然这会引起冲突，叫做哈希冲突。
// 创建哈希表 HashTable* createHashTable() { HashTable* hashtable = (HashTable*)malloc(sizeof(HashTable)); for (int i = 0; i < TABLE_SIZE; i++) { hashtable->array[i] = NULL; } return hashtable; }
为了解决哈希冲突，可以把存入数组中同一位置的多个键值对用链表存储，也就是说，数组中每个位置存储的是链表。
// 插入键值对到哈希表，采用链地址法解决冲突 void insert(HashTable* hashtable, char* key, int value) { int index = hash(key);//哈希值 HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));//为新键值对创建新节点 newNode->key = strdup(key); newNode->value = value; newNode->next = NULL;//初始化结点指针 if (hashtable->array[index] == NULL) {//哈希表上所要插入的位置为空（无链表） hashtable->array[index] = newNode; } else { //不为空，出现冲突 HashNode* current = hashtable->array[index];//声明当前节点指针 while (current->next != NULL) {//遍历到该位置链表的最后一个节点 current = current->next;//找到了最后一个节点，并将当前节点设置为最后一个节点 } current->next = newNode;//将最后一个节点的next指针从NULL设置为newnode新节点 } } 查找： // 根据键查找对应的值 int get(HashTable* hashtable, char* key) { int index = hash(key); HashNode* current = hashtable->array[index]; while (current != NULL) { if (strcmp(current->key, key) == 0) { return current->value; } current = current->next; } return -1; // 表示未找到 } 删除： // 从哈希表中删除指定键的键值对 void removeKey(HashTable* hashtable, char* key) { int index = hash(key); HashNode* current = hashtable->array[index]; HashNode* prev = NULL; // 查找要删除的节点并记录其前驱节点 while (current != NULL && strcmp(current->key, key) != 0) { prev = current; current = current->next; } // 如果找到了要删除的节点 if (current != NULL) { // 如果要删除的节点是链表的第一个节点 if (prev == NULL) { hashtable->array[index] = current->next; } else { prev->next = current->next; } // 释放要删除的节点的内存 free(current->key); free(current); } } 完全销毁哈希表（销毁哈希表中所有占用内存的子成员）： // 销毁哈希表 void destroyHashTable(HashTable* hashtable) { for (int i = 0; i < TABLE_SIZE; i++) { HashNode* current = hashtable->array[i]; while (current != NULL) { HashNode* temp = current; current = current->next; free(temp->key);//释放节点的空间 free(temp);//释放节点的指针成员空间 } } free(hashtable);//释放哈希表的空间 }
