java数据结构是一个有序集合,提供了HashSet的常量时间contains
方法的功能,并且提供了常量时间通过索引查找的功能,很像ArrayList的get
方法? Java API 包含这样的东西吗?我考虑过使用 TreeSet,但根据 Java 文档,这些操作的复杂度为 O(log n)。
最佳答案
Java 标准库没有提供这样的类,但是您可以实现自己的类,而不会有太多麻烦。它或多或少是 LinkedHashSet
的双重:一个维护内部 HashSet
的 List
(可能包装 ArrayList
) > 用于恒定时间 contains()
处理。
Collections API 的类旨在使其易于实现
集合类;在这种情况下,我将考虑实现 AbstractList
的具体子类.
更新:
另一方面,如果您的想法是实例自动按顺序维护其元素,和/或它们不允许重复元素,那么您所说的根本不是 List
。在这种情况下,您需要考虑实现 AbstractSet
的具体子类添加索引检索方法。您仍然可以包装 HashSet
和 ArrayList
,但您需要花费一些精力来保持列表在元素插入时有序。
关于Java 有序可哈希集合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36140884/