数据结构 哈希表（链地址法）

头文件

#pragma once #include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> #include<iostream> using namespace std; #define hashfactor 0.75 #define initcapacity 16 typedef struct hashnode{ char* key; int val; struct hashnode* next; }hashnode; typedef struct hashtable { hashnode** buckets; int size; int capacity;// 桶的数量 double factor; }hashtable; // 字符串哈希函数（djb2算法） static unsigned long hashString(const char* str); // 判断是否为质数 static int isPrime(int n); // 获取下一个质数 static int nextPrime(int n); // 创建新节点 static hashnode* createNode(const char* key, int value); // 释放节点 static void freeNode(hashnode* node); // 计算哈希索引 static int getHashIndex(hashtable* table, const char* key); // 重新哈希（扩容） static void rehash(hashtable* table); // 检查是否需要扩容 static void checkResize(hashtable* table); // 1. 创建哈希表 hashtable* createhashtable(); // 2. 销毁哈希表 void destroyhashtable(hashtable* table); // 3. 插入键值对 int hashInsert(hashtable* table, const char* key, int value); // 4. 查找键对应的值 int* hashSearch(hashtable* table, const char* key); // 5. 删除键值对 int hashDelete(hashtable* table, const char* key); // 6. 获取哈希表大小 int getSize(hashtable* table); // 7. 判断哈希表是否为空 int isEmpty(hashtable* table); // 8. 打印哈希表 void printhashtable(hashtable* table); // 9. 清空哈希表 void clearhashtable(hashtable* table); // 10. 获取当前负载因子 double getLoadFactor(hashtable* table);

源文件

#include"哈希.h" // 字符串哈希函数（djb2算法） static unsigned long hashString(const char* str) { unsigned long hash = 5381; int n = 0; while ((n=*str++)) { hash = ((hash << 5) + hash) + n; } return hash; } // 判断是否为质数 static int isPrime(int n) { if (n <= 1)return 0; if (n <= 3)return 1; if (n % 2 == 0 || n % 3 == 0)return 0; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return 0; } return 1; } // 获取下一个质数 static int nextPrime(int n) { while (!isPrime(n)) { n++; } return n; } // 创建新节点 static hashnode* createNode(const char* key, int value) { assert(key != nullptr); hashnode* node = (hashnode*)malloc(sizeof(hashnode)); if (node == nullptr) { cout << "init err" << endl; return nullptr; } node->key = strdup(key); if (node->key==nullptr) { free(node); cout << "init err" << endl; return nullptr; } node->val = value; node->next = nullptr; return node; } // 释放节点 static void freeNode(hashnode* node) { assert(node != nullptr); free(node->key); free(node); } // 计算哈希索引 static int getHashIndex(hashtable* table, const char* key) { assert(table != nullptr && key != nullptr); return hashString(key) % table->capacity; } // 重新哈希（扩容） static void rehash(hashtable* table) { assert(table != nullptr); int newcapacity = nextPrime(table->capacity*2); hashnode** newbuckets = (hashnode**)calloc(newcapacity, sizeof(hashnode*)); if (newbuckets == nullptr) { cout << "expand err" << endl; return ; } for (int i = 0; i < table->capacity; i++) { hashnode* node = table->buckets[i]; while (node) { hashnode* next = node->next; int newIndex = hashString(node->key) % newcapacity; node->next = newbuckets[newIndex]; newbuckets[newIndex] = node; node = next; } } free(table->buckets); table->buckets = newbuckets; table->capacity = newcapacity; } // 检查是否需要扩容 static void checkResize(hashtable* table) { assert(table != nullptr); double a =(double) table->size / table->capacity; if (a >= table->factor)rehash(table); } // 1. 创建哈希表 hashtable* createhashtable() { hashtable* table = (hashtable*)malloc(sizeof(hashtable)); if (table==nullptr) { cout << "init err" << endl; return nullptr; } table->capacity = initcapacity; table->factor = hashfactor; table->size = 0; table->buckets = (hashnode**)calloc(table->capacity, sizeof(hashnode*)); if (table->buckets == nullptr) { free(table); printf("createHashTable err: 桶数组分配失败\n"); return nullptr; } return table; } // 2. 销毁哈希表 void destroyhashtable(hashtable* table) { assert(table != nullptr); clearhashtable(table); if (table->buckets) { free(table->buckets); } free(table); } // 3. 插入键值对 int hashInsert(hashtable* table, const char* key, int value) { assert(key != nullptr && table != nullptr); checkResize(table); int index =getHashIndex(table, key); hashnode*head = table->buckets[index]; hashnode* current = head; while (current) { if (strcmp(current->key, key) == 0) { current->val = value; return 1; } current = current->next; } hashnode* node = createNode(key, value); if (node == nullptr) { cout << "err" << endl; return 0; } node->next = table->buckets[index]; table->buckets[index] = node; table->size++; return 1; } // 4. 查找键对应的值 int* hashSearch(hashtable* table, const char* key) { assert(table != nullptr && key != nullptr); int index = getHashIndex(table, key); hashnode* current = table->buckets[index]; while (current) { if (strcmp(current->key, key) == 0) { return &current->val; } current = current->next; } return nullptr; } // 5. 删除键值对 int hashDelete(hashtable* table, const char* key) { assert(table != nullptr && key != nullptr); int index = getHashIndex(table, key); hashnode* current = table->buckets[index]; hashnode* prev = nullptr; while (current) { if (strcmp(current->key, key) == 0) { if (prev) { prev->next = current->next; } else { table->buckets[index] = current->next; } freeNode(current); table->size--; return 1; } prev = current; current = current->next; } return 0; } // 6. 获取哈希表大小 int getSize(hashtable* table) { assert(table != nullptr); return table->size; } // 7. 判断哈希表是否为空 int isEmpty(hashtable* table) { assert(table != nullptr); return table->size == 0; } // 8. 打印哈希表 void printhashtable(hashtable* table) { assert(table != nullptr); if (isEmpty(table))return; printf("\n========== 哈希表内容 ==========\n"); for (int i = 0; i < table->capacity; i++) { printf("桶[%3d]: ", i); hashnode* current = table->buckets[i]; if (current == nullptr) { printf("(空)"); } else { while (current) { printf("[%s:%d]", current->key, current->val); if (current->next) { printf(" -> "); } current = current->next; } } printf("\n"); } printf("================================\n"); } // 9. 清空哈希表 void clearhashtable(hashtable* table) { assert(table != nullptr); for (int i = 0; i < table->capacity; i++) { hashnode* current = table->buckets[i]; while (current) { hashnode* next = current->next; freeNode(current); current = next; } table->buckets[i] = nullptr; } table->size = 0; } // 10. 获取当前负载因子 double getLoadFactor(hashtable* table) { assert(table != nullptr); return (double)table->size / table->capacity; }