一般的哈希表保证 O(1) 的插入、删除和查找，但是没有特定的遍历顺序。

Python 里的哈希表（dict）保证遍历顺序等于插入顺序，其他复杂度不变。实现方法是把元素按插入顺序放在一个链表（或者数组）里，而哈希表指向这个链表的节点。

我现在的需求是，提供一个函数 move_key_to_index(k, i)，使得遍历时这个key在第i个位置。

这个需求最佳能达到什么时间复杂度？

我能想到的是把键按需要的遍历顺序排在一个平衡二叉树里。这样插入/删除都是O(log n)复杂度。有没有复杂度更低的方式？



- 来自 水木社区APP v3.5.5
--
FROM 183.179.53.*

当然有。你可以写一个hash表，里面key是i，v是指向链表的指针。每次这个moveto i，就update这个hash表，然后顺序遍历时自己存一个当前遍历到的index，如果hash表里有i，则返回hash表指向的v，否则接着遍历。当然需要调过已遍历的key啥啥的，细节你自己扣吧。

【 在 fanci 的大作中提到: 】
:
: 一般的哈希表保证 O(1) 的插入、删除和查找，但是没有特定的遍历顺序。
:
: Python 里的哈希表（dict）保证遍历顺序等于插入顺序，其他复杂度不变。实现方法是把元素按插入顺序放在一个链表（或者数组）里，而哈希表指向这个链表的节点。
:
--
FROM 141.193.88.*