algorithm - 如何创建复杂度为 O(1) 的集合

Question

我想创建一个数据结构或集合，在添加、删除和计算 no 时复杂度为 O(1)。的元素。我应该如何开始？

我想到了一个解决方案:我将使用一个哈希表，对于插入的每个键/值对，我将只有一个哈希码，即:我的哈希码算法每次都会生成一个唯一的哈希值，因此存储值的索引将是唯一的(即没有冲突)。

这会给我 O(1) 复杂度吗？

Answer 1

是的，这会起作用，但正如您提到的，您的哈希函数需要 100% 唯一。任何重复都会导致您不得不使用某种冲突解决方案。我会推荐线性链接。

编辑 Hashmap.size() 允许 O(1) 访问

编辑 2: 对 Larry 造成的困惑的回应 =P

是的，散列是 O(k)，其中 k 是 key 长度。每个人都可以同意这一点。但是，如果您没有完美的散列，您根本无法获得 O(1) 时间。你的主张是你不需要唯一性来实现 O(1) 删除特定元素。我向你保证那是错误的。

考虑一个最坏的情况:每个元素散列到相同的东西。你最终得到一个链表，众所周知，它没有 O(1) 删除。我希望，正如您提到的，没有人愚蠢到像这样制作哈希。

要点是，哈希的唯一性是 O(1) 运行时间的先决条件。

即便如此，从技术上讲，它也不是 O(1) 大 O 效率。只有使用摊销分析，您才能在最坏的情况下实现恒定的时间效率。正如维基百科关于摊销分析的文章所述

The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

这指的是在某些负载因子下调整哈希表的大小(改变数据结构的状态)可以确保更小的冲突机会等。

我希望这一切都清楚了。