散列表和阵列列表的时间复杂度

为什么haskey的时间复杂度是O（1）。为了找到一个密钥，它必须遍历列表中的所有元素，所以它为什么是O（1）
contains数组列表的方法的时间复杂度散列表和阵列列表的时间复杂度

2014-09-13 user3856587

为什么不尝试谷歌搜索！ – 2014-09-13 19:52:50

没有得到满意的答案 – user3856587 2014-09-13 19:53:36

看看这个答案：http://stackoverflow.com/questions/4100677/is-there-a-comprehensive-big-o-listing-of-java-data-structures/25338144#25338144 – nem035 2014-09-13 19:55:47

散列表不是列表。它是一种专门针对常见情况下的O（1）查找而设计的数据结构（最坏情况的查找实际上是O（n））。它通过散列的概念实现了这一点，该散列是从密钥内容派生的数字，用于直接计算数组中密钥的索引。

ArrayList只是一个下面的数组，因此contains就是您所期望的线性搜索结构。

来源

2014-09-13 19:56:50

散列表和阵列列表的时间复杂度

回答

相关问题