就技术而言,根据我在这里阅读的帖子,哈希表在最坏情况下确实需要O(n)时间来查找。但我不理解内部机制如何保证平均情况下是O(1)时间。
我的理解是,对于给定的n个元素,理想情况是有n个桶,这样可以得到O(1)的空间复杂度。这就是我卡住的地方。假设我想要查找字典中是否存在某个键,这肯定需要O(n)的时间。那么当我想要通过使用其键的哈希值来搜索哈希表中的元素时,为什么会产生差异呢?简单来说,使用原始键值进行搜索需要O(n)时间,但是使用哈希值则需要O(1)时间。为什么?
我难道不仍然需要一个一个地查找哈希值才能看到哪一个匹配吗?为什么哈希让我立即知道要检索哪个元素或是否存在这样的元素?
index = hashFunction(key) % number_of_buckets
(这是概念性的,实际上在现实世界中计算索引会更加复杂) - fps