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

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

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

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

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



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