一、先给结论（一句话记死）
可扩展哈希是「普通哈希表」的「扩容升级版」，完全解决了普通哈希表「扩容卡顿、效率极低」的致命缺点，其余功能（增删改查）和普通哈希表完全一样，上手零门槛。
二、先回顾：「普通哈希表」核心痛点
普通哈希表（数组+链表+Rehash），是最基础的哈希表实现，日常用没问题，但一扩容就「拉胯」，3个核心痛点新手也能直观感受到：
❌ 痛点1：扩容必「全量搬家」，数据越多越卡
普通哈希表扩容时，会创建一个全新的更大数组，然后把所有旧数据全部重新计算索引、全部搬到新数组。
✅ 大白话举例：
你租了个10平的小房子（哈希表容量10），东西多了要换30平的大房子 → 必须把衣柜、床、冰箱、所有东西全部打包、搬运、重新摆放，过程中完全没法正常生活。
数据量越大（东西越多），搬家耗时越久，程序会直接「卡顿、卡死」。
❌ 痛点2：扩容是「一刀切」，全局整体变大
普通哈希表的容量是全局统一的，扩容时必须「整体翻倍」（比如11→23、23→47），哪怕只有1个桶的数据满了，也要把所有桶一起扩容，属于「小题大做、浪费资源」。
✅ 大白话举例：
小区里只有1栋楼的住户住满了，物业却要求整个小区所有楼栋全部推倒重建、扩大面积，其他空楼栋也跟着折腾，纯纯浪费人力物力。
❌ 痛点3：哈希冲突越积越多，查询变慢
普通哈希表用「链表挂接」解决冲突（一个桶里多个数据），扩容不及时的话，链表会变得越来越长 → 原本O(1)的查询，会慢慢变成O(n)，查数据越来越慢。
三、可扩展哈希的「3大核心改进」
可扩展哈希的所有设计，全部精准解决普通哈希表的3个痛点，核心改进只有3点
✅ 改进1：扩容从「全局搬家」→「局部搬家」（解决「扩容卡顿」）
✅ 核心变化：哪个桶满了，只动哪个桶，其余桶完全不动
普通哈希表是「一动全动」，可扩展哈希是「一动其余全不动」，这是最核心、最关键的改进！
扩容时只迁移「满桶」里的少量数据，其余数据完全不用动，程序全程不卡顿、无延迟。
✅ 改进2：扩容从「全局一刀切」→「局部按需分裂」（解决「资源浪费」）
✅ 核心变化：容量按需增长，不搞「整体翻倍」，哪个桶不够用就「分裂」哪个桶
可扩展哈希没有「全局容量」的概念，而是用「桶」作为最小存储单元，每个桶独立管理容量：
桶没满 → 正常存数据，不做任何操作；
桶存满 → 仅把这个桶「分裂」成2个新桶，仅此而已。
✅ 改进3：冲突从「链表挂接」→「桶分裂化解」（解决「查询变慢」）
✅ 核心变化：用「桶分裂」替代「链表挂接」，永远没有超长链表，查询速度永远是O(1)
普通哈希表：冲突的数据往链表上挂，链表越长查询越慢；
可扩展哈希：没有链表！每个桶里用数组存数据，桶满了就分裂，数据会自动分散到新桶里，永远不会出现「一个桶里堆一堆数据」的情况，查询速度永远保持最快。
四、普通哈希 vs 可扩展哈希
对比维度（新手关心的点） | 「普通哈希表」 | 可扩展哈希（改造版） | 谁更优 |
扩容时是否卡顿 | ✅ 必卡顿（全量迁移所有数据） | ❌ 不卡顿（仅迁移满桶数据） | ✔️ 可扩展哈希 |
扩容是否浪费资源 | ✅ 浪费（全局整体扩容） | ❌ 不浪费（局部按需扩容） | ✔️ 可扩展哈希 |
解决冲突的方式 | ✅ 链表挂接（越长越慢） | ❌ 桶分裂（永远均匀） | ✔️ 可扩展哈希 |
查询速度稳定性 | ✅ 不稳定（链表长则变慢） | ✅ 绝对稳定（永远O(1)） | ✔️ 可扩展哈希 |
实现难度 | ✅ 超简单（新手友好） | ✅ 稍复杂 | ✔️ 普通哈希（上手） |
数据量大时性能 | ✅ 越来越差 | ✅ 始终稳定 | ✔️ 可扩展哈希 |
五、可扩展哈希2个核心概念
不用纠结复杂原理，只需要记住2个最核心的概念，就能彻底理解可扩展哈希，和普通哈希的区别也会更清晰：
✅ 概念1：「桶」—— 可扩展哈希的「最小存储单元」
桶 = 一个「固定大小的小数组」（比如最多存4个键值对）；
所有数据都存在「桶」里，一个桶存满了，就「分裂」成2个桶；
普通哈希表的「桶」是「被动承载数据」，可扩展哈希的「桶」是「主动管理自己」。
✅ 概念2：「目录」—— 可扩展哈希的「导航地图」
目录 = 一张「索引表」，记录「每个哈希值 → 对应哪个桶」；
你要查/存数据时，先查目录 → 找到对应的桶 → 直接操作桶里的数据；
桶分裂时，只需要更新目录里的「一条导航记录」，其余记录完全不变，效率极高。
✅ 选「普通哈希表」，如果：
👉 你是新手，只想快速上手、理解哈希表基础原理；
👉 数据量不大（几百/几千条数据），扩容卡顿完全可以接受；
👉 追求「代码简单、容易调试、出错率低」。
✅ 选「可扩展哈希」，如果：
👉 你需要存储大量数据（几万/几十万条），担心扩容卡顿；
👉 要求程序运行稳定、查询速度快，不能有性能抖动；
👉 想学习「工业级高性能哈希表」的实现思路（面试高频考点）。
七、核心原理极简总结
普通哈希表：扩容全量迁移、冲突挂链表、数据越多越卡；
可扩展哈希：扩容局部分裂、无链表冲突、性能永远稳定；
可扩展哈希的核心优势：解决了普通哈希表「扩容代价高」的致命问题，是更适合大数据量的哈希表实现。
最终总结
✅ 可扩展哈希 对 普通哈希表，本质就是「扩容方式的升级」；
✅ 核心改进只有1个：把「全局全量扩容」改成「局部按需扩容」，其余所有优点（不卡顿、不浪费、速度快）都是这个改进带来的；
✅ 你不用纠结底层复杂逻辑，直接用我改好的可扩展哈希代码，用法和你原来的普通哈希表完全一样，增删改查接口一个没动，上手零成本！
代码
头文件
#ifndef __EXTENDIBLE_HASH_H__ #define __EXTENDIBLE_HASH_H__ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #define INITIAL_GLOBAL_K 2 // 初始全局前缀位数 (目录长度=2^k=4) #define BUCKET_CAPACITY 4 // 每个桶的最大容量（可自定义） #define MAX_KEY_LEN 64 // 键的最大长度 // 1. 键值对结构体（桶内存储的最小单元） typedef struct { char key[MAX_KEY_LEN]; int value; } KVNode; // 2. 哈希桶结构体（可扩展哈希核心：最小存储单元，满了则分裂） typedef struct HashBucket { KVNode* entries; // 桶内的键值对数组 int size; // 桶内已存储元素数量 int local_k; // 桶的局部前缀位数（关键！实现局部分裂） } HashBucket; // 3. 可扩展哈希表主结构体（替代你原有的HashTable） typedef struct ExtendibleHashTable { HashBucket** dir; // 全局目录表（核心！存桶的指针，实现映射） int global_k; // 全局前缀位数，目录长度 = 2^global_k int bucket_cap; // 单个桶的最大容量 int total_size; // 哈希表总元素数量 } ExtendibleHashTable; // 1. 创建可扩展哈希表 ExtendibleHashTable* createHashTable(); // 2. 销毁可扩展哈希表 void destroyHashTable(ExtendibleHashTable* table); // 3. 插入键值对（存在则更新） int hashInsert(ExtendibleHashTable* table, const char* key, int value); // 4. 查找键对应的值（返回NULL表示不存在） int* hashSearch(ExtendibleHashTable* table, const char* key); // 5. 删除键值对 int hashDelete(ExtendibleHashTable* table, const char* key); // 6. 获取哈希表总元素数 int getSize(ExtendibleHashTable* table); // 7. 判断哈希表是否为空 int isEmpty(ExtendibleHashTable* table); // 8. 打印哈希表完整结构（桶+目录+数据） void printHashTable(ExtendibleHashTable* table); // 9. 清空哈希表所有数据 void clearHashTable(ExtendibleHashTable* table); // 10. 获取当前负载因子（总元素/总桶容量） double getLoadFactor(ExtendibleHashTable* table); #endif // __EXTENDIBLE_HASH_H__源文件
#include "可扩展哈希.h" // 1. djb2字符串哈希函数 static unsigned long hashString(const char* str) { unsigned long hash = 5381; int c; while ((c = *str++)) { hash = ((hash << 5) + hash) + c; // hash * 33 + c } return hash; } // 2. 判断是否为质数 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; } // 3. 获取下一个质数 static int nextPrime(int n) { while (!isPrime(n)) { n++; } return n; } /** * 创建新的哈希桶 * @return 初始化完成的桶指针 */ static HashBucket* createBucket() { HashBucket* bucket = (HashBucket*)malloc(sizeof(HashBucket)); if (bucket == NULL) { printf("createBucket err: 内存分配失败\n"); return NULL; } bucket->entries = (KVNode*)malloc(sizeof(KVNode) * BUCKET_CAPACITY); if (bucket->entries == NULL) { free(bucket); printf("createBucket err: 桶数据区分配失败\n"); return NULL; } bucket->size = 0; bucket->local_k = INITIAL_GLOBAL_K; // 初始局部k = 全局k return bucket; } /** * 释放单个哈希桶内存 */ static void freeBucket(HashBucket* bucket) { if (bucket) { free(bucket->entries); free(bucket); } } /** * 计算目录索引（可扩展哈希核心：哈希值高位前缀映射） * @param hash 字符串哈希值 * @param k 前缀位数（全局k/局部k） * @return 目录表的索引位置 */ static int getDirIndex(unsigned long hash, int k) { // 取哈希值的高k位，转为十进制索引（32位无符号数） return (int)(hash >> (32 - k)); } /** * 桶分裂（可扩展哈希核心！替代你的全量Rehash） * @param table 哈希表指针 * @param old_bucket 待分裂的桶 * @param dir_idx 桶在目录中的索引 */ static void splitBucket(ExtendibleHashTable* table, HashBucket* old_bucket, int dir_idx) { printf("触发桶分裂: 全局k=%d → %d | 桶局部k=%d → %d\n", table->global_k, table->global_k + 1, old_bucket->local_k, old_bucket->local_k + 1); // 1. 旧桶局部k+1，创建新桶 int old_local_k = old_bucket->local_k; old_bucket->local_k++; HashBucket* new_bucket = createBucket(); new_bucket->local_k = old_bucket->local_k; // 2. 迁移旧桶数据：重新分配到旧桶/新桶 int idx = 0; while (idx < old_bucket->size) { KVNode* entry = &old_bucket->entries[idx]; unsigned long hash = hashString(entry->key); // 用新的局部k计算索引，判断归属 int new_idx = getDirIndex(hash, old_bucket->local_k); // 掩码：区分新旧桶 (2^(old_local_k)) int mask = 1 << old_local_k; if ((new_idx & mask) != 0) { // 数据归新桶：移过去并删除旧桶中的数据 memcpy(&new_bucket->entries[new_bucket->size], entry, sizeof(KVNode)); new_bucket->size++; // 覆盖旧桶当前位置（前移） old_bucket->entries[idx] = old_bucket->entries[--old_bucket->size]; } else { idx++; // 数据归旧桶，指针后移 } } // 3. 扩展目录表（全局k+1，目录长度翻倍） if (old_bucket->local_k > table->global_k) { int old_dir_len = 1 << table->global_k; table->global_k++; int new_dir_len = 1 << table->global_k; // 重新分配目录内存 table->dir = (HashBucket**)realloc(table->dir, sizeof(HashBucket*) * new_dir_len); if (table->dir == NULL) { printf("splitBucket err: 目录扩容失败\n"); return; } // 目录映射：旧索引复制，新索引指向对应桶 for (int i = old_dir_len; i < new_dir_len; i++) { table->dir[i] = table->dir[i ^ old_dir_len]; } } // 4. 更新目录映射：新索引指向新桶 int new_local_k = old_bucket->local_k; int dir_mask = (1 << new_local_k) - 1; int base_idx = dir_idx & (~dir_mask); for (int i = 0; i < (1 << new_local_k); i++) { int curr_idx = base_idx | i; unsigned long hash = hashString(old_bucket->entries[0].key); if (getDirIndex(hash, new_local_k) == curr_idx % (1 << new_local_k)) { table->dir[curr_idx] = old_bucket; } else { table->dir[curr_idx] = new_bucket; } } printf("桶分裂完成: 旧桶剩余%d个元素 | 新桶新增%d个元素\n", old_bucket->size, new_bucket->size); } /** * 检查桶是否已满，满则触发分裂 */ static void checkSplit(ExtendibleHashTable* table, HashBucket* bucket, int dir_idx) { if (bucket->size >= table->bucket_cap) { splitBucket(table, bucket, dir_idx); } } // 1. 创建可扩展哈希表（替代你的原函数） ExtendibleHashTable* createHashTable() { ExtendibleHashTable* table = (ExtendibleHashTable*)malloc(sizeof(ExtendibleHashTable)); if (table == NULL) { printf("createHashTable err: 内存分配失败\n"); return NULL; } table->global_k = INITIAL_GLOBAL_K; table->bucket_cap = BUCKET_CAPACITY; table->total_size = 0; // 初始目录长度 = 2^global_k int init_dir_len = 1 << table->global_k; table->dir = (HashBucket**)malloc(sizeof(HashBucket*) * init_dir_len); if (table->dir == NULL) { free(table); printf("createHashTable err: 目录分配失败\n"); return NULL; } // 初始化目录：所有索引指向同一个桶 HashBucket* init_bucket = createBucket(); for (int i = 0; i < init_dir_len; i++) { table->dir[i] = init_bucket; } printf("创建可扩展哈希表成功 | 初始全局k=%d | 目录长度=%d | 单桶容量=%d\n", table->global_k, init_dir_len, table->bucket_cap); return table; } // 2. 销毁可扩展哈希表（替代你的原函数） void destroyHashTable(ExtendibleHashTable* table) { if (table == NULL) return; clearHashTable(table); free(table->dir); free(table); printf("可扩展哈希表已销毁\n"); } // 3. 插入键值对（核心，支持更新+自动分裂） int hashInsert(ExtendibleHashTable* table, const char* key, int value) { if (table == NULL || key == NULL || strlen(key) >= MAX_KEY_LEN) return 0; unsigned long hash = hashString(key); int dir_idx = getDirIndex(hash, table->global_k); HashBucket* bucket = table->dir[dir_idx]; // 步骤1：检查键是否存在，存在则更新值 for (int i = 0; i < bucket->size; i++) { if (strcmp(bucket->entries[i].key, key) == 0) { printf("更新键: %s (旧值: %d → 新值: %d)\n", key, bucket->entries[i].value, value); bucket->entries[i].value = value; return 1; } } // 步骤2：键不存在，检查桶容量，满则分裂 checkSplit(table, bucket, dir_idx); // 分裂后桶可能变化，重新获取 dir_idx = getDirIndex(hash, table->global_k); bucket = table->dir[dir_idx]; // 步骤3：插入新键值对 KVNode* new_entry = &bucket->entries[bucket->size]; strncpy(new_entry->key, key, MAX_KEY_LEN - 1); new_entry->key[MAX_KEY_LEN - 1] = '\0'; new_entry->value = value; bucket->size++; table->total_size++; printf("插入键值对: [%s: %d] | 目录索引: %d | 桶内位置: %d\n", key, value, dir_idx, bucket->size - 1); return 1; } // 4. 查找键对应的值（和你原函数用法一致） int* hashSearch(ExtendibleHashTable* table, const char* key) { if (table == NULL || key == NULL) return NULL; unsigned long hash = hashString(key); int dir_idx = getDirIndex(hash, table->global_k); HashBucket* bucket = table->dir[dir_idx]; for (int i = 0; i < bucket->size; i++) { if (strcmp(bucket->entries[i].key, key) == 0) { return &bucket->entries[i].value; } } return NULL; } // 5. 删除键值对（和你原函数用法一致） int hashDelete(ExtendibleHashTable* table, const char* key) { if (table == NULL || key == NULL) return 0; unsigned long hash = hashString(key); int dir_idx = getDirIndex(hash, table->global_k); HashBucket* bucket = table->dir[dir_idx]; for (int i = 0; i < bucket->size; i++) { if (strcmp(bucket->entries[i].key, key) == 0) { // 覆盖删除：最后一个元素前移 bucket->entries[i] = bucket->entries[--bucket->size]; table->total_size--; printf("删除键值对: [%s: %d]\n", key, value); return 1; } } printf("删除失败: 键 %s 不存在\n", key); return 0; } // 6. 获取哈希表大小（和你原函数一致） int getSize(ExtendibleHashTable* table) { return (table == NULL) ? 0 : table->total_size; } // 7. 判断哈希表是否为空（和你原函数一致） int isEmpty(ExtendibleHashTable* table) { return (table == NULL) ? 1 : (table->total_size == 0); } // 8. 打印哈希表（增强版：打印目录+桶+数据） void printHashTable(ExtendibleHashTable* table) { if (table == NULL) { printf("哈希表为空指针\n"); return; } if (isEmpty(table)) { printf("哈希表为空\n"); return; } int dir_len = 1 << table->global_k; printf("\n========== 可扩展哈希表详情 ==========\n"); printf("全局k: %d | 目录长度: %d | 总元素数: %d | 单桶容量: %d | 负载因子: %.2f\n", table->global_k, dir_len, table->total_size, table->bucket_cap, getLoadFactor(table)); printf("\n【全局目录映射表】\n"); for (int i = 0; i < dir_len; i++) { printf("目录[%2d] → 桶地址: %p | 桶局部k: %d | 桶内元素: %d\n", i, table->dir[i], table->dir[i]->local_k, table->dir[i]->size); } printf("\n【所有桶数据详情】\n"); for (int i = 0; i < dir_len; i++) { HashBucket* bucket = table->dir[i]; // 去重打印桶（同一个桶会被多个目录索引指向） static HashBucket* printed_buckets[1024]; static int printed_cnt = 0; int is_printed = 0; for (int j = 0; j < printed_cnt; j++) { if (printed_buckets[j] == bucket) { is_printed = 1; break; } } if (is_printed) continue; printed_buckets[printed_cnt++] = bucket; printf("桶%p (局部k=%d, 元素数=%d): ", bucket, bucket->local_k, bucket->size); for (int j = 0; j < bucket->size; j++) { printf("[%s:%d]", bucket->entries[j].key, bucket->entries[j].value); if (j < bucket->size - 1) printf(" → "); } printf("\n"); } printf("======================================\n"); } // 9. 清空哈希表（和你原函数一致） void clearHashTable(ExtendibleHashTable* table) { if (table == NULL) return; int dir_len = 1 << table->global_k; // 去重释放桶 HashBucket* freed_buckets[1024]; int freed_cnt = 0; for (int i = 0; i < dir_len; i++) { HashBucket* bucket = table->dir[i]; int is_freed = 0; for (int j = 0; j < freed_cnt; j++) { if (freed_buckets[j] == bucket) { is_freed = 1; break; } } if (!is_freed) { freed_buckets[freed_cnt++] = bucket; freeBucket(bucket); } } // 重建初始状态 HashBucket* init_bucket = createBucket(); for (int i = 0; i < dir_len; i++) { table->dir[i] = init_bucket; } table->total_size = 0; table->global_k = INITIAL_GLOBAL_K; printf("可扩展哈希表已清空，恢复初始状态\n"); } // 10. 获取负载因子（和你原函数一致） double getLoadFactor(ExtendibleHashTable* table) { if (table == NULL) return 0.0; int dir_len = 1 << table->global_k; int total_bucket_cap = dir_len * table->bucket_cap; return (total_bucket_cap == 0) ? 0.0 : (double)table->total_size / total_bucket_cap; }
