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的布尔值的最快方法(平均)是什么?包含()的概率大约高5倍。
Do all the map structures provide o(1) operation? Is HashSet the fastest way to go?
所有的地图结构都提供o(1)操作吗?HashSet是最快的方法吗?
4 个解决方案
#1
108
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.)基于实现。它们含有O(1)表示contains()
This cheatsheet is of great help.
这张作弊单很有帮助。
#2
7
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.
对于密度较高的数字，我会使用位集，它会比哈希集更快更小。
#3
3
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)。然而，更有可能的是，您将会遇到散列桶的冲突，而一些查找将需要检查多个值。
#4
-2
hashing(hash set) is the best one with O(1)
哈希(哈希集)是O(1)的最佳哈希集
#1
108
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.)基于实现。它们含有O(1)表示contains()
This cheatsheet is of great help.
这张作弊单很有帮助。
#2
7
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.
对于密度较高的数字，我会使用位集，它会比哈希集更快更小。
#3
3
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)。然而，更有可能的是，您将会遇到散列桶的冲突，而一些查找将需要检查多个值。
#4
-2
hashing(hash set) is the best one with O(1)
哈希(哈希集)是O(1)的最佳哈希集