内容简介：如果我们从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 实现数据结构】遍历二叉查找树
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
架构即未来：现代企业可扩展的Web架构、流程和组织(原书第2版)
Martin L. Abbott、Michael T. Fisher / 陈斌 / 机械工业出版社 / 2016-4-15 / 99.00
任何一个持续成长的公司最终都需要解决系统、组织和流程的扩展性问题。本书汇聚了作者从eBay、VISA、Salesforce.com到Apple超过30年的丰富经验， 全面阐释了经过验证的信息技术扩展方法，对所需要掌握的产品和服务的平滑扩展做了详尽的论述，并在第1版的基础上更新了扩展的策略、技术和案例。 针对技术和非技术的决策者，马丁•阿伯特和迈克尔•费舍尔详尽地介绍了影响扩展性的各个方面，包......一起来看看 《架构即未来：现代企业可扩展的Web架构、流程和组织(原书第2版)》 这本书的介绍吧!
