Java中contains（）的最快数据结构？

Java中对contains（）有最快操作的数据结构是什么？

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

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

所有的地图结构是否提供o（1）操作？ HashSet是最快的方法吗？

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

哈希（哈希集）是最好的一个O（1）