分离链接哈希表删除后能否恢复插入顺序并保持O(n)删除复杂度？

可以做到，核心是用全局双向链表替代数组来维护插入顺序，同时让哈希桶内的节点关联双向链表的对应节点，这样既不增加删除的时间复杂度，又能按插入顺序遍历。

具体实现方案 #

• 除了哈希表的「数组+桶内链表」结构，额外维护一个带头尾指针的全局双向链表，每个插入的元素都会被添加到这个双向链表的尾部，保证插入顺序。
• 哈希桶内的每个节点需要存储三个信息：键、值，以及指向全局双向链表对应节点的引用/指针。

插入操作

1. 计算键的哈希值，找到对应的哈希桶；
2. 把新节点添加到该桶的链表末尾；
3. 同时创建一个双向链表节点，将其添加到全局双向链表的尾部，并用哈希桶节点保存这个双向链表节点的引用。
   整个插入过程时间复杂度为O(1)（哈希计算+链表尾插，双向链表有尾指针时尾插是O(1)）。

删除操作

1. 计算键的哈希值，定位到目标哈希桶；
2. 遍历该桶内的链表，找到要删除的节点（这一步的时间复杂度是O(k)，k为该桶内的元素数，也就是题目中提到的O(n)）；
3. 从桶内链表中移除该节点；
4. 通过哈希桶节点中保存的引用，直接定位到全局双向链表中的对应节点，将其从双向链表中删除（双向链表删除已知节点的时间复杂度是O(1)）。
   整个删除操作的时间复杂度仍由桶内遍历的O(k)决定，没有额外的全局遍历开销，符合题目要求的O(n)复杂度。

示例说明 #

假设插入顺序为keyA、keyB、keyC：

• 哈希计算后，keyA和keyC分到桶0，keyB分到桶1；
• 全局双向链表的顺序为：keyA ↔ keyB ↔ keyC；
• 桶0的链表：keyA节点（含双向链表引用） → keyC节点（含双向链表引用）；
• 桶1的链表：keyB节点（含双向链表引用）。

当删除keyA时：

1. 定位到桶0，遍历找到keyA节点；
2. 从桶0链表中移除keyA节点；
3. 通过引用找到全局双向链表中的keyA节点，将其删除，此时双向链表变为keyB ↔ keyC；
4. 遍历全局双向链表，就能按插入顺序得到剩余元素：keyB、keyC。

为什么不用数组？ #

用数组维护插入顺序的问题在于：删除时需要先遍历数组找到目标元素的索引，这一步是O(m)（m为全局元素总数），会让删除的整体时间复杂度上升到O(m)，不符合要求。而双向链表删除已知节点是O(1)，完全不会增加删除的时间开销。

内容的提问来源于stack exchange，提问作者Kirill Dolghi