哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:
答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.
B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).
除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.
我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.
维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？
编辑:总结我学到的东西:
这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.
在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.
因此，我正在观看其中一部有关他们如何进行采访的Google视频（https://www.youtube.com/watch?v=XKu_SEDAykw），我发现他们的解决方案很奇怪。由于Google的工作人员很多，所以我现在想知道我是否做错了什么，或者他们做错了。让我总结一下任务和解决方案，以防您不想看它：
任务是为以下问题提供有效的算法：
给定一个整数数组A和一个单独的整数a，找到两个索引i，j，使得A [i] + A [j] = a。
他们从对数组进行排序开始，并产生一个不错的线性时间算法。但是然后，面试官问如果不对数组进行排序会发生什么情况。他们提出了以下线性时间算法（他们说先对数组排序然后使用线性时间算法太慢，尽管它会以nlogn的时间运行）：
他们从头到尾遍历数组，并使用哈希集存储他们已经看到的数字。然后，他们只需要检查数组的每个索引的哈希集（即我是否已经看到需要获取和的数字），并且由于这显然可以在恒定时间内进行，因此整个算法都在线性时间内运行（本质上是哈希集的数量* Array.length）。
现在我的批评是：我认为这种解决方案存在一个巨大的缺陷，本质上在于可能发生碰撞。由于它们假定nlogn较慢，因此我们可以假设哈希集具有比logn少的许多不同条目。现在，在有大量输入的情况下，将n个数字散列到最多log个很多集合中时，发生冲突的可能性趋于1。因此，他们以非常适度的速度增加进行交易（他们假设该数组的速度为100亿，但是对数（以2为底）仍然小于30。但是，将此速度与哈希集算法匹配将意味着超过3亿）数字将被散列到同一位置），几乎可以确定是错误的算法。
我或者对哈希有误解，或者这是解决该问题的糟糕方法。同样，安全的nlogn算法不会比他们给出的算法慢很多，除非数组变得太大以至于哈希算法肯定会发生冲突。
如果一个恒定时间算法为小型数组投入一枚硬币并始终对大型数组说“是”，那么它们的哈希集解决方案平均具有相同的成功率，我不会感到惊讶。
如果我对散列有所误解，请指出，因为我很难相信他们会在一流的计算机工程公司犯这样的错误。