java - 有没有一种数据结构可以避免重复、保持顺序和随机访问

Question

之前，当我寻找具有以下特征的数据结构时。

• 避免重复
• 迭代顺序与插入顺序相同

在 Java 中，我使用 LinkHashSet ，在Python中，我使用OrderedDict

现在，除了 2 个要求之外，我还想有一个附加要求

• 能够通过索引进行随机访问，意味着我可以通过data[123]进行访问

有没有可用的数据结构？或者我需要回退到使用List？ List 能够完全满足第二个和第三个要求，但不能满足第一个要求。我可能需要在插入过程中执行手动(和缓慢检查)以避免重复？

Answer 1

Java 中的一种简单方法是创建一个包装类，该类实现 Set 和 List 接口(interface)，并且包含 HashSet > 和ArrayList。更新操作需要更新两个内部集合，而读取操作将映射到能够提供正确语义和最佳性能的内部集合。唯一有点棘手的方法是 iterator()，您需要安排 remove 更新两个集合。

这种方法将为您提供“两全其美”的读取操作性能，但更新速度必然会较慢。特别是，在给定位置插入和删除将是 O(N) 操作。

(我注意到 LinkedHashSet 不是一个直接的解决方案，因为它不提供 get(int) 方法。您可以通过 LinkedHashSet 迭代器实现此方法，从而使其成为 O(N) 操作。可能不是您想要的。)

跟进

我无法找到同时实现 Set 和 List 接口(interface)的通用实现类。我认为原因是接口(interface)组合时存在语义异常。例如，(如 @ColinD 注释)如果您使用列表中已有的元素调用 E set(int, E) ，则不清楚结果应该是什么。以一种让每个人都满意的方式处理这个问题可能是不可能的，我可以理解为什么他们可能决定不在柏油坑里游泳。

但是，如果您要创建一个 Set + List 类供应用程序内部使用，我认为这不是一个主要问题。你要么

• 选择适合您的应用程序的语义，
• 对您的应用程序进行编码，使其根本不使用该方法，或者
• 对您的应用程序进行编码以避免受到异常影响。

(例如，您可以将其编码为忽略 set 方法的结果，如果存在重复，则抛出未经检查的异常，或者返回 null 或某些区分对象是否有重复。)

郑重声明，自定义集合类违反接口(interface)约定并不是不可原谅的。事实上，甚至 Java 设计者也这样做 - 请参阅 IdentityHashMap。不可原谅的是没有在 javadoc 中记录违反契约(Contract)的行为。