So a lot of sources say the hashmap remove function is O(1), but I don't see how this could be unless a hashmap were backed by a linkedlist because list removals are O(n). Could someone explain?
问问题
4132 次
2 回答
4
您可以将 Hasmap 视为一个数组。想象一下，您想将地球上所有人类的物体存储在某个地方。您可以为每个人获取一个唯一编号，并使用一个维度为 10*10^20 的数组。如果有人出生，她/他将获得下一个免费号码并添加到末尾。如果有人死了，则使用她/他的号码并将数组条目设置为空。
您可以很容易地看到，添加或删除某人，您只需要恒定的时间。计算数组地址，完成（如果你有随机存取存储器）。
Hashmap 添加了什么？有2个动机。一方面，你不想拥有这么大的阵列。如果您只想存储来自世界各地的 10 个人，则该数组的几乎所有条目都是免费的。另一方面，并非您要存储在某处的所有数据都具有唯一编号。有时有多次相同的数字，有些数字现在确实显示整体，有时您没有任何数字。因此，您定义了一个函数，该函数使用输入中的大数字并将它们减少为较小范围内的数字。这种减少在某种程度上应该是，对于不同的输入，结果数字很可能是唯一的。
示例：假设您要存储从 1 到 100000000 的 10 个数字。您可以使用具有 100000000 个索引的数组。或者您可以使用具有 100 个索引的数组和函数 f(x) = x % 100。如果您有数字 1234，则 f(1234) = 34。将 34 标记为已分配。
现在你可能会问，如果你有数字 2234 会发生什么？那我们就发生碰撞。你需要一些策略来处理这个，有几个。研究一些文献或为此提出具体问题。
如果你想存储一个字符串，你可以想象使用每个字符的长度或 ascii 值的总和。
如您所见，我们可以轻松地存储一些东西，并轻松地再次访问它。我们必须做什么？从函数计算散列（一个好的函数是常数时间），访问数组（常数时间），存储或删除（常数时间）。
在现实世界中，一个好的散列函数并不是那么容易。尝试坚持使用 java 中包含的内容。
如果您想阅读更多详细信息，关于哈希表的维基百科文章是一个很好的起点：http ://en.wikipedia.org/wiki/Hash_table
于 2012-10-29T20:20:39.487 回答
0
我不认为 remove(key) 复杂度是 O(1)。如果我们有一个有很多冲突的大哈希表，那么在最坏的情况下它将是 O(n)。最坏的情况很少见，但我们不能忽视 O(1) 不能保证的事实。
于 2016-02-11T00:15:19.977 回答