data-structures - 具有删除 o(1) 和随机访问 o(1) 的数据结构

Question

我正在为我的项目寻找具有删除 o(1) 和随机访问 o(1) 的数据结构。有人可以帮忙吗？

标签： data-structures

Answer 1

如果您坚持这些复杂性，并且您不必在删除键后立即释放表中的内存，那么您可以使用动态完美散列。

这有点复杂：https ://en.wikipedia.org/wiki/Dynamic_perfect_hashing

要获得 O(1) 删除，您必须将删除引起的任何重新散列推迟到下一次插入。