擅长:python、mysql、java
<p>对于第一个问题-为什么查找的平均时间复杂度是O(1)?-一般来说,只有当你有一个好的哈希函数时,这个语句才是正确的。一个理想的散列函数是一个在其元素上产生良好扩散的函数。特别是,哈希函数的选择通常使得任意两个元素碰撞的概率很低。在这个假设下,可以正式证明要检查的元素的预期数量是O(1)。如果你在网上搜索“通用散列函数族”,你可能会找到这个结果的一些很好的证明。在</p>
<p>至于使用占位符-有几种不同的方法来实现哈希表。您所使用的方法称为“封闭寻址”或“带链接的散列”,在这种方法中,几乎没有理由使用占位符。然而,也存在其他哈希策略。一种常见的方法称为“开放寻址”(其中最著名的是线性探测散列),在这些设置中,占位符元素是必要的,以避免错误的否定查找。在网上搜索这方面的更多细节可能会给你一个很好的解释。在</p>
<p>至于这与HashMap有何区别,HashMap只是一种可能的映射抽象实现,由哈希表支持。Java的HashMap确实支持null,而其他方法则不支持</p>