【数据结构与算法】哈希表

哈希表（Hash Table）是一种基于键（Key）直接访问数据的高效数据结构，其核心思想是通过哈希函数将键映射到数组的特定位置，从而实现平均时间复杂度为 O(1)O(1) 的插入、查找和删除操作。 结构定义 // 哈希表节点 typedef struct HashNode { int key; int value; struct Hashcode* next; } HashNode; // 哈希表 typedef struct { int size; HashNode** buckets; } HashTable; 初始化 创建HashTable结构体变量，进行初始化赋值，分配桶的内存。 // 初始化哈希表 HashTable *creat_hash_table(int size) { HashTable* table = (HashTable*)malloc(sizeof(HashTable)); table->size = size; table->buckets = (HashNode**)malloc(size * sizeof(HashNode*)); for(int i = 0; i < size; i++) { table->buckets[i] = NULL; } return table; } 哈希函数 // 哈希函数 int hash(int key, int size) { return key % size; } 通过简单取模运算获得哈希值 插入 // 插入 void insert(HashTable *table, int key, int value) { int index = hash(key, table->size); HashNode *newNode = (HashNode *)malloc(sizeof(HashNode)); newNode->key = key; newNode->value = value; newNode->next = NULL; // 插入链表头部，避免遍历链表 if (table->buckets[index] == NULL) { table->buckets[index] = newNode; } else { newNode->next = table->buckets[index]; table->buckets[index] = newNode; } } 头插法无需遍历到尾部。 查找 // 查找 int search(HashTable *table, int key) { int index = hash(key, table->size); HashNode *current = table->buckets[index]; while (current != NULL) { if (current->key == key) { return current->value; } current = current->next; } return -1; } 删除 void deleate(HashTable* table, int key) { int index = hash(key, table->size); HashNode* current = table->buckets[index]; HashNode* prev = NULL; while(current != NULL) { if(current->key == key) { if(prev == NULL) { table->buckets[index] = current->next; } else { prev->next = current->next; } free(current); return; } prev = current; current = current->next; } }