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

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

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

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

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

来源

2010-07-16 codechobo

102

查看set（Hashset，enumset）和hash（HashMap，linkedhash ...，idnetityhash ..）的实现。他们有O（1）for contains（）

This cheatsheet有很大的帮助。

来源

2010-07-16 17:57:43

对于什么是值得的，当散列冲突发生时（通常情况下，如果一次只有很少的情况下它们会发生），散列映射通常不是O（1）查找。最坏的情况是O（n）查找。 – Blindy 2010-07-17 07:27:05

我同意Blindy。基于散列的收集性能受散列函数性能的限制。 – sbidwai 2010-07-17 07:42:33

我最近去的时候，网站已经关闭了。如果发生这种情况，您可以使用此[链接]（http://web.archive.org/web/20120105103844/http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2。 pdf） – EasilyBaffled 2013-04-28 18:17:01

-2

散列（哈希集合）是最好的一个用O（1）

来源

2010-07-16 18:07:10 Satish

答案与Pangea之间有8分钟的时间。你的增加没有额外的价值，为什么张贴它？ – 2010-07-16 18:12:04

@bart真实缓慢的互联网连接 – Will 2010-07-16 18:49:35

@也许会。如果是这样，那么@Satish现在有足够的时间去除他/她多余的答案。然而，他/她选择让它垂涎。也许希望收集一些观点？也许这是开始的意图，谁知道？ – 2010-07-16 18:52:55

对于数字的你的具体情况具有相对高密度的我会使用一个位集合，它会比一个哈希更快，更小组。

来源

2010-07-16 22:15:20 starblue

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

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

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

来源

2010-07-17 07:23:45

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

回答

相关问题