在Java中包含()的最快的数据结构？
在Java中包含()的最快的数据结构？
提问于 2010-07-17 01:52:54
在Java中，contains()操作最快的数据结构是什么？
例如，我有一组数字{ 1，7，12，14，20...}
给定另一个任意数字x，生成集合中是否包含x的布尔值的最快方法(平均而言)是什么？包含()的概率大约高出5倍。
是否所有的map结构都提供o(1)操作？HashSet是最快的方法吗？
回答 4
Stack Overflow用户
回答已采纳
发布于 2010-07-17 01:57:44
查看集合(哈希集，枚举集)和哈希(HashMap，linkedhash...，idnetityhash..)基于实现。它们对于contains()有O(1)
This cheatsheet有很大的帮助。
Stack Overflow用户
发布于 2010-07-17 06:15:20
对于密度相对较高的数字的特殊情况，我会使用BitSet，它会更快，而且比哈希集小得多。
Stack Overflow用户
发布于 2010-07-17 15:23:46
唯一比HashSet更快的数据结构可能是来自Trove4J的TIntHashSet。这使用了基元，避免了使用Integer对象的需要。
如果整数的数量很少，您可以创建一个boolean[]，其中存在的每个值都将转换为“真”。这将是O(1)。注意:log不一定是O(1)，更有可能是O( HashSet (log(N)。
对于理想的散列分布，您只会得到O(1)。但是，更有可能的是，您将得到哈希存储桶的冲突，并且某些查找将需要检查多个值。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3267572
复制相关文章
相似问题
腾讯云开发者
