拉链法关键在于哈希桶数组初始化为null/-1、头插维护O(1)效率、next存节点下标而非地址、遍历时严格按索引跳转；静态三数组结构（e/ne/h）提升缓存友好性与内存安全性。

拉链法不是简单地“把冲突元素塞进链表”，关键在于链表节点如何与哈希桶关联、指针如何初始化、插入时如何维护头尾关系——这些细节直接决定查找效率和内存安全性。

哈希桶数组怎么初始化才不踩坑

桶数组本质是“链表头指针数组”，每个元素必须明确指向一个有效链表头，或显式标记为空。常见错误是直接用 int[] h = new int[N] 初始化，导致默认值 0 被误认为合法链表头索引（实际应为 -1 或 nullptr）。

• Java/C++ 中推荐：用 Integer[] h = new Integer[N] 或 Node* h[N] = {nullptr}，空桶统一为 null/-1
• C 风格静态模拟（如 Redis/算法题常用）：int h[N]; memset(h, -1, sizeof(h))，确保未使用的桶头为 -1
• 切忌用原始整型数组且不做初始化——后续遍历时无法区分“空桶”和“真实存储在索引 0 的节点”

插入时头插还是尾插？为什么几乎都选头插

头插法让新节点成为桶链表的新头部，时间复杂度稳定 O(1)，且无需遍历找尾；尾插需额外维护尾指针或每次遍历，得不偿失。

• 头插核心逻辑：e[idx] = x; ne[idx] = h[k]; h[k] = idx++ —— 新节点的 next 指向原链表头，再把 h[k] 更新为新节点索引
• 注意：h[k] 存的是“当前链表第一个节点在 e[] 中的下标”，不是数据值本身；ne[i] 存的是 e[i] 节点的下一个节点下标
• 若业务要求保持插入顺序（如 LRU），可改用尾插，但必须额外维护 tail[k] 数组，增加空间与逻辑开销

链表节点里的 next 指针到底存什么

next 不是指向内存地址的裸指针，而是“在节点池中的相对位置索引”。这是静态链表（无 malloc/free）的核心设计，避免碎片且利于缓存。

• 典型三数组结构：e[i] 存值，ne[i] 存下一个节点在 e[] 中的下标，h[k] 存该桶第一个节点在 e[] 中的下标
• 例如：h[3] = 5 表示地址 3 的桶，链表头是 e[5]；ne[5] = 2 表示 e[5] 的下一个节点是 e[2]；ne[2] = -1 表示链表结束
• 这种设计下，所有节点内存连续（e[] 和 ne[] 是数组），比动态 new 出来的链表更易预取、更省内存管理开销

查找和删除时如何安全遍历链表

遍历必须严格按 next 索引跳转，不能依赖循环变量 i 自增；删除操作只需修改前驱节点的 ne 值，无需移动数据。

• 查找模板：for (int i = h[k]; i != -1; i = ne[i]) if (e[i] == x) return true;
• 删除关键：找到待删节点的前驱 j，执行 ne[j] = ne[i] 即可“跳过”i；若要删的是头节点（i == h[k]），则直接 h[k] = ne[i]
• 务必检查边界：i == -1 时终止；ne[i] 访问前确保 i 有效（≥ 0 且