hashmap删除复杂性

Question

所以有很多消息来源说hashmap删除函数是O（1），但我不明白这可能是如何，除非散列表由链表返回，因为列表清除是O（n）。有人可以解释吗？

Answer 1

您可以将Hasmap视为一个数组。想象一下，你想把地球上所有人的物体存储在地球上。您可以为每个人获取唯一的编号，并使用尺寸为10 * 10^20的数组。 如果某人出生，她/他会获得下一个免费号码并被添加到结尾。如果有人死亡，则使用她/他的号码，数组条目设置为空。

你可以很容易地看到，添加一些或删除某人，你只需要恒定的时间。计算阵列地址，完成（如果你有随机存取存储器）。

什么是由Hashmap添加的？有2个动机。一方面，你不想拥有如此庞大的阵列。如果你只想存储来自世界各地的10个人，几乎所有的数组条目都是免费的。另一方面，并​​非所有要存储在某处的数据都有唯一的编号。有时会有多次相同的号码，有些号码现在显示为整体，有时候您没有任何号码。因此，您可以定义一个函数，该函数使用输入中的大数字并将其减小到较小范围内的数字。这种减少应该是一种方式，即最终的数字对于不同的输入来说可能是唯一的。

例如：假设您想要存储10个数字，从1到100000000.您可以使用一个有100000000个索引的数组。或者你可以使用一个有100个索引的数组，并且函数f（x）= x％100.如果你的数字是1234，那么f（1234）= 34。

现在你可以问，如果你的号码是2234，会发生什么？那么我们碰撞了。你需要一些策略来处理这个问题，有几个。研究一些文献或为此提出具体问题。

如果你想存储一个字符串，你可以想象使用每个字符的长度或ascii值的总和。如您所见，我们可以轻松存储某些内容，并轻松地再次访问它。我们必须做什么？计算函数中的散列（一个好函数的恒定时间），访问数组（恒定时间），存储或删除（恒定时间）。

在现实世界中，一个好的散列函数并不那么容易。尝试坚持在Java中包含的。

如果您想了解更多的细节，关于哈希表维基百科的文章是一个很好的起点：http://en.wikipedia.org/wiki/Hash_table

Answer 2

我不认为删除（键）复杂度为O（1）。如果我们有一个有很多碰撞的大散列表，那么在最坏的情况下它就是O（n）。很难得到最坏的情况，但我们不能忽视O（1）不能保证的事实。