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

Java中对contains()有最快操作的数据结构是什么?

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

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

所有的地图结构是否提供o(1)操作? HashSet是最快的方法吗?

看看集(Hashset,enumset)和散列(HashMap,linkedhash …,idnetityhash ..)为基础的实现。 他们有O(1)for contains()

这个备忘录有很大的帮助。

对于具有相对较高密度的数字的情况,我使用一个BitSet,它比一个散列集更快,更小。

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

如果整数的数量很小,可以创build一个布尔型的[],其中每个存在的值都变成“true”。 这将是O(1)。 注意:HashSet不保证是O(1),更可能是O(log(log(N)))。

你只会得到一个理想的散列分布的O(1)。 但是,更有可能会碰到散列桶,而且有些查找需要检查多个值。

哈希(哈希集)是最好的一个O(1)