Java有序哈希集合

什么是java数据结构是一个有序集合，提供HashSet函数的恒定时间方法contains，并提供按索引进行恒定时间查找，就像ArrayList的get方法一样？ Java API是否包含这样的东西？我考虑过使用TreeSet，但根据Java Docs，这些操作是O（log n）。Java有序哈希集合

来源

2016-03-21 Aroto

A ['LinekdHashSet']（https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashSet.html）也许？ – Mureinik

你需要恒定时间插入吗？如果是这样，这是行不通的，因为像这样的数据结构可以让你在O（n）时间进行比较排序。 – user2357112

当您说“已订购”时，是指排序顺序，还是指其他订单，如广告订单？ – user2357112

使用LinkedHashSet。它是Set接口的哈希表和链表实现，具有可预测的迭代顺序。

你会看到最多O（n）的复杂插入或检查的哈希集合项目的存在。但是大多数时候你没有看到碰撞，所以在大多数情况下，它会是O（1）。

来源

2016-03-21 20:29:09 FallAndLearn

LinkedHashSet是否支持索引？ – Aroto

设置界面没有任何直接的方法，如indexOf（）或get（）。您需要解析整个集合才能搜索元素。 indexOf（）和get（）在内部只做同样的事情。 – FallAndLearn

OP通过索引*请求恒定时间元素检索*。虽然'LinkedHashSet'提供了恒定时间检索，但它只能通过键而不是索引。 –

Java标准库不提供这样的类，但你可以没有太多的麻烦实现自己的。这将是或多或少的双重LinkedHashSet：一个List（也许包装ArrayList）维持恒定时处理的内部HashSet。

集合API有为了使自己容易实现集合类课程;在这种情况下，我会考虑实现AbstractList的具体子类。

更新： 在另一方面，如果你的想法是，情况自动保持它们的元素有序，和/或他们不允许重复的元素，那么你所谈论的不是List在所有。在这种情况下，你会想要考虑实现一个AbstractSet的具体子类，它增加了索引检索方法。你仍然可以包装一个HashSet和一个ArrayList，但是你需要花费一些努力来保持元素插入时的列表顺序。

来源

2016-03-21 20:42:34

Java有序哈希集合

回答

相关问题