在Java中，哪种数据结构具有最快的contains()操作?
比如我有一个数字集合{1、7、12、14、20...}
给定另一个任意数字x，最快的方法（平均而言）生成x是否包含在集合中的布尔值是什么？!contains()的概率约为5倍。
所有映射结构都提供O(1)操作吗？HashSet是最快的方式吗？
4个回答
136
看看基于set（Hashset，enumset）和hash（HashMap，linkedhash ...，idnetityhash ...）的实现。它们对contains()方法具有O(1)复杂度。
这份速查表非常有帮助。
- Aravind Yarram
4
8就此而言，当哈希冲突发生时（尤其是同时发生的情况很少），一般情况下哈希映射在查找方面并不是O(1)。最坏情况下，查找复杂度为O(n)。请注意，哈希冲突经常发生。 - Blindy
我同意Blindy的观点。基于哈希的集合的性能受到哈希函数性能的限制。 - sbidwai
最近我去的时候，网站已经崩了。如果你也遇到这种情况，可以使用这个链接：http://web.archive.org/web/20120105103844/http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf - EasilyBaffled
由于 robots.txt 文件的限制，无法爬取或显示该页面（请更正链接）。 - iluvatar_GR
9
对于数字密度相对较高的情况，我建议使用BitSet，它比哈希集合更快且更小。
- starblue
5
HashSet之外唯一更快的数据结构可能是Trove4J中的TIntHashSet。它使用原始类型避免使用整数对象。
如果整数数量很小，可以创建一个boolean[]，其中每个存在的值都变为"true"。这将是O(1)。注意：HashSet不能保证是O(1)，更有可能是O(log(log(N)))。
只有在理想的哈希分布下才能获得O(1)。然而，你更有可能会遇到哈希桶的冲突，有些查找需要检查多个值。
如果整数数量很小，可以创建一个boolean[]，其中每个存在的值都变为"true"。这将是O(1)。注意：HashSet不能保证是O(1)，更有可能是O(log(log(N)))。
只有在理想的哈希分布下才能获得O(1)。然而，你更有可能会遇到哈希桶的冲突，有些查找需要检查多个值。
- Peter Lawrey
-2
哈希（哈希集）是最好的，具有O（1）
- Satish
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接