Java中contains()的最快数据结构？

Question

Java中哪些数据结构对contains()的运行速度最快？

例如,我有一组数字{1,7,12,14,20 ...}

给定另一个任意数x,生成布尔值的最快方式(平均)是否包含在集合中？!contains()的概率大约高出5倍.

所有地图结构都提供o(1)操作吗？HashSet是最快的方式吗？

Answer 1

查看set(Hashset,enumset)和hash(HashMap,linkedhash ...,idnetityhash ..)的实现.他们有O(1)for contains()

这张备忘单非常有用.

Answer 2

对于具有相对较高密度的数字的特定情况,我使用BitSet,它将比哈希集更快且更小.

Answer 3

唯一比 HashSet 更快的数据结构可能是来自 Trove4J 的 TIntHashSet。这使用原语避免了使用整​​数对象的需要。

如果整数的数量很少，您可以创建一个 boolean[]，其中每个存在的值都变成“true”。这将是 O(1)。注意：HashSet 不保证是 O(1)，更可能是 O(log(log(N)))。

对于理想的散列分布，您只会得到 O(1)。但是，您更有可能会遇到散列存储桶的冲突，并且某些查找将需要检查多个值。