相关疑难解决方法(0)

当我们使用a HashTable来存储数据时,据说搜索需要o(1)时间.我很困惑,任何人都可以解释一下吗？

我对哈希表的时间复杂性感到困惑很多文章表明它们是"摊销的O(1)"而不是真正的命令O(1)这在实际应用中意味着什么.哈希表中的操作的平均时间复杂度是多少,实际实现中不是理论上的,为什么操作不正确O(1)？

为什么Vector(ArrayList for Java people)的经典实现在每次扩展时将其内部数组大小加倍,而不是将其增加三倍或四倍？

好吧,我会承认我没有挖出反射器来看看这里发生了什么,但我希望有人可以告诉我.

Microsoft如何快速地添加和获取,我可以通过在数组中粘贴项目来快速添加,并且我可以通过对数组进行排序和使用二进制搜索来快速获取.但是,如果我每次添加一个项目以快速获取数据时都会进行快速排序,那么添加会大幅减慢速度,如果每次我尝试获取某些内容时都必须对数据进行排序,那么添加项目会大大减慢.

有谁知道字典的内部工作原理？它比数组更需要内存,所以除了聪明的算法之外,显然还有一些东西在幕后进行.

我正在努力理解魔法并从中学习!

在线检查java和google搜索哈希表代码示例,似乎通过加倍来完成表的大小调整.
但是大多数教科书都说桌子的最佳尺寸是素数.
所以我的问题是:
加倍的方法是因为:

1. 它易于实现,或
2. 找到素数太低效了(但我认为找到下一个素n+=2数并使用模数测试素数是O(loglogN)这很便宜)
3. 或者这是我的误解,只有某些散列表变体只需要主表大小？

更新:
教科书中使用素数的方式是某些属性工作所必需的(例如,二次探测需要一个素数表来证明,例如,如果一个表不是完整的项目X将被插入).
发布为重复的链接一般要求增加任何数字,例如25%或下一个素数,并且答案接受说明我们加倍以保持调整大小操作"罕见",因此我们可以保证摊销时间.
这并没有回答这样一个问题:使用一个表格大小是素数并使用素数来调整大小甚至大于两倍.因此,我们的想法是保持主要大小的属性考虑调整大小开销