当前位置：首页 > news >正文

Hash哈希表以及代码

news 2026/3/26 19:56:56

哈希表（Hash Table），也叫散列表，是一种用于存储键值对（key-value pairs）的高效数据结构。它通过一个哈希函数（Hash Function）将任意的键（如字符串、数字等）映射到一个固定范围的索引（通常是一个数组下标），进而实现数据的快速插入、查找、删除和修改。

哈希表在平均情况下，这些操作的时间复杂度可以达到：

插入：O(1)

查找：O(1)

删除：O(1)

修改：O(1)

但在极端情况下（例如大量哈希冲突且未有效处理），性能可能退化至O(n)。

哈希表的核心在于：

哈希函数：将任意 key 映射为数组的一个索引，决定该键值对应该存放在哪个“桶（bucket）”中。
冲突解决：由于不同的 key 可能映射到同一个索引（即哈希冲突），因此需要有机制来处理多个键值对共享同一个桶的情况。

这里使用的是链地址法解决哈希冲突。本代码只使用了简单的线性链表。

链地址法：在每个数组位置（桶）上维护一个链表（或树结构）。当发生冲突时，将新元素添加到对应索引的链表中。如果冲突链表过长，这个时候可以将这个链表转换为红黑树、最小堆。由原来链表时间复杂度O(n) 转换为红黑树时间复杂度O(log n) ；

本文采用一种简单的字符累加取模法作为哈希函数：

static int _hash(char *key, int size) { if (!key) return -1; int sum = 0; int i = 0; while (key[i] != 0) { sum += key[i]; // 累加每个字符的 ASCII 值 i++; } return sum % size; // 取模得到桶的索引 }

对于存储节点的定义如下：

typedef struct hashnode_s{ char *key; char *value; struct hashnode_s *next; } hashnode_t;

一对键值对以及 next节点.

分别实现了初始化函数，申请节点函数，销毁函数，增删改函数。

核心 API：

init_hashtable初始化

_create_node创建节点

_hash哈希函数

hashtable_insert插入

get_hashtable查找

hashtable_delete删除

hashtable_modify修改

count_hashtable查询节点数量

dest_hashtable销毁

测试 main() 函数：涵盖初始化 → 插入 → 查询 → 统计 → 删除 → 修改的完整流程

完整代码：

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <pthread.h> #define MAX_KEY_LEN 128 #define MAX_VALUE_LEN 512 #define MAX_TABLE_SIZE 1024 typedef struct hashnode_s{ char *key; char *value; struct hashnode_s *next; } hashnode_t; typedef struct hashtable_s{ hashnode_t **nodes; int node_count; } hashtable_t; hashtable_t Hash; // 哈希函数 static int _hash(char *key, int size) { if(!key) return -1; int sum = 0; int i = 0; while(key[i]!=0){ sum += key[i]; i++; } return sum % size; } hashnode_t *_create_node(char *key, char *value){ hashnode_t *node = (hashnode_t *)malloc(sizeof(hashnode_t)); if(!node) return NULL; node->key = (char *)malloc(strlen(key) + 1); if (!node->key){ free(node); return NULL; } strcpy(node->key, key); node->value = (char *)malloc(strlen(value) + 1); if(!node->value){ free(node->key); free(node); return NULL; } strcpy(node->value, value); node->next = NULL; return node; } int init_hashtable(hashtable_t *hash){ if(!hash) return -1; hash->nodes = (hashnode_t **)malloc(sizeof(hashnode_t *) * MAX_TABLE_SIZE); hash->node_count = 0; return 0; } int dest_hashtable(hashtable_t *hash){ if(!hash) return -1; int i = 0; for (i = 0; i < hash->node_count; i++){ hashnode_t *node = hash->nodes[i]; while(node != NULL){ hashnode_t *tmp = node; node = node->next; hash->nodes[i] = node;//为什么？没有这行代码也可以吧 if (tmp->key) free(tmp->key); if(tmp->value) free(tmp->value); free(tmp); } } free(hash->nodes); return 0; } int hashtable_insert(hashtable_t *hash, char *key, char *value) { if(!hash || !key || !value) return -1; int idx = _hash(key, MAX_TABLE_SIZE); hashnode_t *node = hash->nodes[idx]; while(node != NULL){ if(strcmp(node->key,key) == 0) return 1; // 已经存在这个key node = node->next; } hashnode_t *new_node = _create_node(key, value); // 头插法 new_node->next = hash->nodes[idx]; hash->nodes[idx] = new_node; hash->node_count++; return 0; } char *get_hashtable(hashtable_t *hash, char *key){ if(!hash || !key ) return NULL; int idx = _hash(key, MAX_TABLE_SIZE); hashnode_t *node = hash->nodes[idx]; while(node != NULL){ if(strcmp(node->key,key) == 0) return node->value; node = node->next; } return NULL;// 没找到key } int count_hashtable(hashtable_t *hash){ return hash->node_count; } int hashtable_delete(hashtable_t *hash, char *key) { if(!hash || !key ) return -1; hashnode_t *node_del_per = NULL; hashnode_t *node_del = NULL; int idx = _hash(key, MAX_TABLE_SIZE); hashnode_t *node = hash->nodes[idx]; if (node == NULL) { return -1; // 没有找到任何节点 } if(strcmp(node->key,key) == 0){// 排查第一个元素 node_del = node; hash->nodes[idx] = node_del->next; node_del->next = NULL; if (node_del->key) free(node_del->key); if(node_del->value) free(node_del->value); free(node_del); hash->node_count--; return 0; } while (node->next != NULL)// 排查其他元素 { if(strcmp(node->next->key,key) == 0){ node_del_per = node; node_del = node->next; node_del_per->next = node_del->next; node_del->next = NULL; if (node_del->key) free(node_del->key); if(node_del->value) free(node_del->value); free(node_del); hash->node_count--; return 0; } node = node->next; } return 1;// 没找到 } int hashtable_modify(hashtable_t *hash, char *key, char *value) { if(!hash || !key || !value) return -1; int idx = _hash(key, MAX_TABLE_SIZE); hashnode_t *node = hash->nodes[idx]; while(node != NULL){ if(strcmp(node->key,key) == 0) break; node = node->next; } if(node == NULL)//没找到key { return 1; } if(node->value) free(node->value); node->value = (char *)malloc(strlen(value) + 1); if(!node->value){ free(node->key); free(node); return -1; } strcpy(node->value, value); return 0; } // 测试部分ai写的 int main(void) { int i = -100; // ---------------------------------------- // 1. Initialize hashtable // ---------------------------------------- printf("1. Initialize hashtable\n"); i = init_hashtable(&Hash); if (i == 0) printf(" Hash table initialized successfully\n"); else printf(" Hash table initialization failed, return value: %d\n", i); printf("\n"); // ---------------------------------------- // 2. Insert key-value pairs // ---------------------------------------- printf("2. Insert key-value pairs\n"); i = hashtable_insert(&Hash, "King", "111"); if (i == 0) printf(" Inserted King=111: success\n"); else if (i == 1) printf(" Inserted King=111: failed, key already exists\n"); else printf(" Inserted King=111: failed, error code: %d\n", i); i = hashtable_insert(&Hash, "Aing", "222"); if (i == 0) printf(" Inserted Aing=222: success\n"); else if (i == 1) printf(" Inserted Aing=222: failed, key already exists\n"); else printf(" Inserted Aing=222: failed, error code: %d\n", i); i = hashtable_insert(&Hash, "Bing", "333"); if (i == 0) printf(" Inserted Bing=333: success\n"); else if (i == 1) printf(" Inserted Bing=333: failed, key already exists\n"); else printf(" Inserted Bing=333: failed, error code: %d\n", i); printf("\n"); // ---------------------------------------- // 3. Get key values // ---------------------------------------- printf("3. Get key values\n"); char *str = get_hashtable(&Hash, "King"); if (str) printf(" Get King: success, value = %s\n", str); else printf(" Get King: failed, key not found\n"); str = get_hashtable(&Hash, "Aing"); if (str) printf(" Get Aing: success, value = %s\n", str); else printf(" Get Aing: failed, key not found\n"); str = get_hashtable(&Hash, "Cing"); if (str) printf(" Get Cing: success, value = %s\n", str); else printf(" Get Cing: failed, key not found\n"); printf("\n"); // ---------------------------------------- // 4. Count entries // ---------------------------------------- printf("4. Count entries\n"); int count = count_hashtable(&Hash); printf(" Total entries in hash table: %d\n", count); printf("\n"); // ---------------------------------------- // 5. Delete a key // ---------------------------------------- printf("5. Delete a key\n"); i = hashtable_delete(&Hash, "King"); if (i == 0) { printf(" Delete King: success\n"); } else { printf(" Delete King: failed, key not found\n"); } count = count_hashtable(&Hash); printf(" Total entries after deletion: %d\n", count); printf("\n"); str = get_hashtable(&Hash, "King"); if (str) printf(" Verify deletion: King still exists, value = %s\n", str); else printf(" Verify deletion: King no longer exists\n"); printf("\n"); // ---------------------------------------- // 6. Modify a key // ---------------------------------------- printf("6. Modify a key\n"); i = hashtable_modify(&Hash, "Aing", "999"); if (i == 0) printf(" Modify Aing=999: success\n"); else printf(" Modify Aing=999: failed, key not found\n"); str = get_hashtable(&Hash, "Aing"); if (str) printf(" Get modified Aing: value = %s\n", str); else printf(" Get modified Aing: failed, key not found\n"); printf("\n"); count = count_hashtable(&Hash); printf(" Total entries after modification: %d\n", count); printf("\n"); // ---------------------------------------- // 7. End // ---------------------------------------- // Free memory dest_hashtable(&Hash); return 0; }

查看全文

http://www.jsqmd.com/news/453515/