Java 中 contains() 最快的数据结构？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3267572/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fastest data structure for contains() in Java?
提问by codechobo
What's the data structure in Java that has the fastest operation for contains() ?
Java 中对 contains() 操作最快的数据结构是什么？
e.g. i have a set of numbers { 1, 7, 12, 14, 20... }
例如我有一组数字 { 1, 7, 12, 14, 20 ... }
Given another arbitrary number x, what's the fastest way (on average) to generate the boolean value of whether x is contained in the set or not? The probability for !contains() is about 5x higher.
给定另一个任意数字 x，生成 x 是否包含在集合中的布尔值的最快方法（平均而言）是什么？!contains() 的概率大约高出 5 倍。
Do all the map structures provide o(1) operation? Is HashSet the fastest way to go?
所有的映射结构都提供 o(1) 操作吗？HashSet 是最快的方法吗？
采纳答案by Aravind Yarram
look at set (Hashset, enumset) and hash (HashMap,linkedhash...,idnetityhash..) based implementations. they have O(1) for contains()
查看基于 set (Hashset, enumset) 和 hash (HashMap,linkedhash...,idnetityhash...) 的实现。对于 contains() 他们有 O(1)
This cheatsheetis of great help.
回答by Satish
hashing(hash set) is the best one with O(1)
hashing(hash set) 是 O(1) 中最好的
回答by starblue
For your particular case of numbers with a relatively high density I'd use a BitSet, it will be faster and much smaller than a hash set.
对于具有相对较高密度的数字的特殊情况，我会使用 BitSet，它会比哈希集更快且小得多。
回答by Peter Lawrey
The only data structure faster than HashSet is likely to be TIntHashSet from Trove4J. This uses primitives avoiding the need to use Integer Objects.
唯一比 HashSet 更快的数据结构可能是来自 Trove4J 的 TIntHashSet。这使用原语避免了使用整数对象的需要。
If the number of integers is small, you can create a boolean[] where each value present is turned into a "true". This will be O(1). Note: HashSet is not guarenteed to be O(1) and is more likely to be O(log(log(N))).
如果整数的数量很少，您可以创建一个 boolean[]，其中每个存在的值都变成“true”。这将是 O(1)。注意：HashSet 不保证是 O(1)，更可能是 O(log(log(N)))。
You will only get O(1) for an ideal hash distribution. However, it is more likely you will get collisions of hashed buckets and some lookups will need to check more than one value.
对于理想的散列分布，您只会得到 O(1)。但是，您更有可能会遇到散列存储桶的冲突，并且某些查找将需要检查多个值。
