内容简介：如果我们从Java的角度来看,那么我们可以说hashmap查找需要不断的时间.但是内部实施呢？它仍然需要通过特定的桶(匹配哪个密钥的哈希码匹配)来搜索不同的匹配密钥.那么为什么我们说哈希查找需要不断的时间？请解释.在使用的哈希函数的适当假设下,我们可以说哈希表查找取预期的O(1)时间.这意味着平均来说,散列表执行查找的工作量最多是一定的.直观地说,如果你有一个“好的”哈希函数,你会希望这些元素在整个散列表中被均匀地分配,这意味着每个数据桶中元素的数量将接近元素数量除以数字的桶.如果哈希表实现保持这个数字低
如果我们从 Java 的角度来看,那么我们可以说hashmap查找需要不断的时间.但是内部实施呢？它仍然需要通过特定的桶(匹配哪个密钥的哈希码匹配)来搜索不同的匹配密钥.那么为什么我们说哈希查找需要不断的时间？请解释.
在使用的哈希函数的适当假设下,我们可以说哈希表查找取预期的O(1)时间.这意味着平均来说,散列表执行查找的工作量最多是一定的.
直观地说,如果你有一个“好的”哈希函数,你会希望这些元素在整个散列表中被均匀地分配,这意味着每个数据桶中元素的数量将接近元素数量除以数字的桶.如果哈希表实现保持这个数字低(比如说,每当元素与桶之间的比例超过一些常量时,添加更多的桶),那么所做的预期工作量就会被作为一些基准量来选择哪个桶应该被扫描,然后做“不太多”的工作,看看元素在那里,因为期望在那个桶中将只有一个恒定数量的元素.
这并不意味着散列表保证了O(1)行为.事实上,在最坏的情况下,散列方案将退化,所有元素都将在一个桶中结束,从而使查找在最坏的情况下花费时间Θ(n).这就是为什么设计好的哈希函数很重要.
有关更多信息,您可能需要阅读算法教科书,以查看哈希表如何有效地支持查找的正式推导.这通常包含在典型的大学课程中作为算法和数据结构的一部分,并且在线有很多好的资源.
希望这可以帮助！
http://stackoverflow.com/questions/15469795/why-hashmap-lookup-is-o1-i-e-constant-time
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 数据结构和算法(Golang实现)(27)查找算法-二叉查找树
- 数据结构之二分查找
- 数据结构与算法：二分查找
- 数据结构与算法：二分查找
- 【PHP 实现数据结构】二叉查找树
- 【PHP 实现数据结构】遍历二叉查找树
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
