Java 中 contains() 最快的数据结构？
Java 中 contains() 操作速度最快的数据结构是什么？
例如，我有一组数字 { 1, 7, 12, 14, 20... }
给定另一个任意数字 x，（平均而言）生成 x 是否包含在该集合中的布尔值的最快方法是什么？ !contains() 的概率大约高出 5 倍。
所有的map结构都提供o(1)操作吗？ HashSet 是最快的方法吗？
What's the data structure in Java that has the fastest operation for contains() ?
e.g. i have a set of numbers { 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.
Do all the map structures provide o(1) operation? Is HashSet the fastest way to go?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
查看基于集合（Hashset，enumset）和散列（HashMap，linkedhash ...，idnetityhash ..）的实现。他们的 contains() 时间复杂度为 O(1)
这份备忘单 有很大帮助。
look at set (Hashset, enumset) and hash (HashMap,linkedhash...,idnetityhash..) based implementations. they have O(1) for contains()
This cheatsheet is of great help.
对于密度相对较高的数字的特定情况，我会使用 BitSet，它比哈希集更快且小得多。
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.
唯一比 HashSet 更快的数据结构可能是来自 Trove4J 的 TIntHashSet。这使用原语，避免使用整数对象。
如果整数的数量很少，您可以创建一个 boolean[]，其中每个存在的值都将转换为“true”。这将是 O(1)。注意：HashSet 不保证是 O(1)，更可能是 O(log(log(N)))。
对于理想的哈希分布，您只能得到 O(1)。然而，您更有可能会遇到散列存储桶的冲突，并且某些查找需要检查多个值。
The only data structure faster than HashSet is likely to be TIntHashSet from Trove4J. This uses primitives avoiding the need to use Integer Objects.
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))).
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)
hashing(hash set) is the best one with O(1)