擅长:python、mysql、java
<p>您似乎忽略了哈希表的全部要点,它是快速(O(1))<sup>1</sup>检索,并且如果没有哈希,就无法实现,即将键转换为某种分布良好的整数,用作表的索引。请注意,在检索时仍然需要相等,以便能够处理哈希冲突<sup>2</sup>,但只有在已将元素集缩小到具有特定哈希的元素集时,才能使用相等。你知道吗</p>
<p>只要相等,就可以用并行数组或类似的东西复制类似的功能,但这将使检索O(n)<sup>3</sup>;如果要求严格的弱排序,则可以实现RB树,它允许O(logn)检索。但是O(1)需要散列。你知道吗</p>
<p>查看<a href="http://en.wikipedia.org/wiki/Hash_table" rel="nofollow">Wikipedia</a>以了解有关哈希表的更多信息。你知道吗</p>
<hr/>
<p>注意事项</p>
<ol>
<li>在病态的情况下(所有元素都放在同一个桶中),它可能变成O(n),但这在一个好的哈希函数中是不应该发生的。你知道吗</li>
<li>由于不同的元素可能具有相同的散列,因此在到达与散列对应的bucket之后,必须检查是否实际检索与给定键关联的元素。你知道吗</li>
<li>或者O(logn),如果您保持数组排序,但这会使插入复杂化,由于元素的移动,插入变得平均O(n);但是,如果您有排序,那么您可能需要RB树或堆。你知道吗</li>
</ol>