从链表到哈希表：数组索引与链表指针如何协作

从链表到哈希表：数组索引与链表指针如何协作

哈希表不是魔法。它的 O(1) 来自数组寻址，冲突处理靠链表兜底，扩容时则是一场指针大迁徙。

引言

前几篇文章里，我们分别看过链表、二叉树和堆。

链表靠next串起来。二叉树靠left/right分叉。堆把指针藏进数组下标，用2i+1、2i+2完成逻辑跳转。

到了哈希表，指针开始进入更复杂的组合形态：数组负责定位，链表负责解决冲突，指针负责把两者焊接起来。

这也是为什么map.put(key, value)看起来简单，底层却同时包含哈希寻址、链表插入、删除摘链、扩容迁移，甚至红黑树转换。

理解哈希表，就是理解数组索引与链表指针如何协作。

1. 哈希表的骨架：数组 + 链表

最经典的哈希表实现是拉链法。

底层维护一个数组，数组的每个位置叫一个桶。每个桶里存的不是一个值，而是一个链表头指针。

structNode{intkey;intvalue;Node*next;};classHashMap{private:vector<Node*>buckets;intcapacity;floatloadFactor;};

这段结构很关键。

buckets是数组。buckets[index]是某个桶的头指针。桶里的每个节点再通过next连接下