哈希表实现原理（通俗版）

哈希表实现的 4 个核心步骤对着图看1. 最底层桶数组Bucket Array这是哈希表的根本质上就是一个普通的 C 语言数组。图里的桶0、桶1...桶7就是这个数组的 8 个元素。为什么用数组因为数组可以按下标 “直达”比如你要访问下标为 2 的元素直接arr[2]不用遍历一步到位。这就是 O (1) 的基础2. 第一步哈希函数把 key 映射到桶你拿到一个 key比如数字2、7、10首先要算它该放哪个桶里。哈希函数干的就是这件事// 最简单的哈希函数uthash 内部用的更复杂但原理一样 int hash(int key, int bucket_count) { return key % bucket_count; // 取模把大数字映射到 0~7 的小范围 }比如key2→2 % 8 2→ 去桶 2key7→7 % 8 7→ 去桶 7key10→10 % 8 2→ 也去桶 2你看不管你的 key 多大算完之后永远是数组的下标直接就能定位到桶不用挨个找。3. 冲突了怎么办拉链法uthash 用的就是这个你发现了吗key2和key10算出来都要去桶 2这就叫哈希冲突。这时候不能把原来的key2覆盖掉怎么办把它们串成一个短链表先到的key2挂在桶 2 下面后到的key10挂在key2的后面变成一串这就是你之前写的uthash代码里那个UT_hash_handle hh;字段的作用它就是用来存链表指针的帮你把冲突的节点串起来。4. 查找的全过程为什么是 O (1)现在你要找key10整个过程是这样的算哈希10 % 8 2→ 我知道了它肯定在桶 2 里直接跳桶不用遍历所有 8 个桶直接跳到数组下标 2 的位置一步到位。短链表查找桶 2 下面有个很短的链表挨个比一下 key第一个是2不对第二个是10找到了你看整个过程不管你总共有 10 个、1000 个、100 万个数据你都只看了桶 2 下面的 2 个元素剩下的 999998 个元素你连看都没看这就是为什么哈希表查找是 O (1)它根本不遍历全部数据只看你要找的那个桶里的一点点数据。那 uthash 帮你做了什么几行简单代码HASH_ADD_INT(hashTable, key, node); HASH_FIND_INT(hashTable, key, node);uthash 内部已经把上面所有事都帮你做了自动维护桶数组自动算哈希值自动处理冲突、串链表自动扩容当数据太多桶不够用了自动把桶的大小翻倍重新哈希所有元素保证每个桶里的链表永远很短你不用管这些细节直接用就行。一句话总结哈希表的本质用一个数组当 “快递柜”用哈希函数直接告诉你快递在哪个柜子就算柜子里有好几个快递也很少找起来超快。