有没有什么数据结构可以避免重复，保持秩序和随机存取

Question

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

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

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

现在，在2个需求之上，我想有一个额外的需求

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

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

Answer 1

Java中的一个简单方法是创建一个实现Set和List接口的包装器类，该类同时包含HashSet和{}。更新操作将需要同时更新两个内部集合，而读取操作将映射到任何一个提供正确语义和最佳性能的内部集合。唯一稍微有点棘手的方法是iterator()，您需要安排remove更新两个集合。在

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

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

我找不到同时实现Set和List接口的通用实现类。我认为原因是当你把接口组合起来时，会出现语义异常。例如，（如@ColinD注释）如果使用列表中已有的元素调用E set(int, E)，则不清楚结果应该是什么。以一种让所有人都满意的方式来处理这件事可能是不可能的，我能理解为什么他们会决定不去柏油池游泳。在

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

• 为适合您的应用程序选择语义
• 编写应用程序，使其完全不使用该方法，或者
• 编写应用程序的代码，以避免被异常情况影响。在

（例如，您可以将其编码为忽略set方法的结果，如果存在重复，则抛出未经检查的异常；如果存在重复，则返回null或某个可分辨对象。）

就记录而言，自定义集合类违反接口约定并不是不可原谅的。事实上，即使是Java设计人员也会这样做——请参见IdentityHashMap。不可原谅的是没有在javadocs中记录违反合同的行为。在

Answer 2

如果可以使用不可变集合，请使用来自Guava的ImmutableSet，它有一个asList（）视图来提供索引访问。在

Answer 3

java.util.Set不提供像get（）和set（）这样的随机访问方法，因此它的大多数/所有实现都没有。您可以创建自己的Set实现来提供这一点，也许可以使用一个ArrayList来保存数据。在