Java 有序可哈希集合

Question

java数据结构是一个有序集合，提供了HashSet的常量时间contains方法的功能，并且提供了常量时间通过索引查找的功能，很像ArrayList的get方法？ Java API 包含这样的东西吗？我考虑过使用 TreeSet，但根据 Java 文档，这些操作的复杂度为 O(log n)。

Answer 1

Java 标准库没有提供这样的类，但是您可以实现自己的类，而不会有太多麻烦。它或多或少是 LinkedHashSet 的双重:一个维护内部 HashSet 的 List(可能包装 ArrayList) > 用于恒定时间 contains() 处理。

Collections API 的类旨在使其易于实现集合类；在这种情况下，我将考虑实现 AbstractList 的具体子类.

更新:另一方面，如果您的想法是实例自动按顺序维护其元素，和/或它们不允许重复元素，那么您所说的根本不是 List。在这种情况下，您需要考虑实现 AbstractSet 的具体子类添加索引检索方法。您仍然可以包装 HashSet 和 ArrayList，但您需要花费一些精力来保持列表在元素插入时有序。