有没有可以避免重复、保持顺序并支持随机访问的数据结构？
之前，我在寻找一种数据结构，具有以下特点：
- 避免重复
- 遍历的顺序和插入的顺序相同
在Java中，我使用LinkedHashSet，在Python中，我使用OrderedDict
现在，在满足这两个要求的基础上，我还想增加一个新要求：
- 能够通过索引随机访问，也就是说我可以通过
data[123]来访问数据
有没有合适的数据结构可以使用？还是我需要退回去使用List？List可以满足第二和第三个要求，但不能满足第一个要求。在插入时，我可能需要手动（而且比较慢地）检查，以避免重复数据？
5 个回答
java.util.Set 是一种集合类型，它不提供像 get() 和 set() 这样的随机访问方法。因此，大多数（或所有）实现这种集合的方式也没有这些方法。如果你想要的话，可以自己实现一个 Set，这样就可以提供这些功能，可能可以用一个 ArrayList 来存储数据。
如果你可以使用一个不可变的集合，那就用Guava库里的ImmutableSet吧。它有一个asList()的方法，可以让你通过索引来访问集合里的元素。
在Java中，一个简单的方法是创建一个包装类，这个类同时实现了Set和List这两个接口，并且内部包含一个HashSet和一个ArrayList。在更新操作时，需要同时更新这两个内部集合，而在读取操作时，则根据哪个内部集合能提供正确的语义和最佳性能来选择使用。唯一稍微复杂一点的方法是iterator()，在这里你需要确保remove操作能够同时更新这两个集合。
这种方法能让你在读取操作时获得“兼得”的性能，但更新操作的速度会相对慢一些。特别是，在给定位置插入和删除操作的时间复杂度是O(N)。
我想提一下，LinkedHashSet并不是一个直接的解决方案，因为它不提供get(int)方法。你可以通过LinkedHashSet的迭代器来实现这个方法，但这样会变成O(N)的操作，可能不是你想要的。
后续补充
我没有找到一个通用的实现类，能够同时实现Set和List这两个接口。我认为原因在于，当你将这两个接口结合在一起时，会出现一些语义上的问题。例如（正如@ColinD所提到的），如果你用一个已经在列表中的元素调用E set(int, E)，结果应该是什么就不太明确了。以一种让所有人都满意的方式来处理这个问题可能是不可能的，我能理解为什么他们可能决定不去碰这个麻烦。
不过，如果你是为自己的应用程序内部创建一个Set + List类，我并不认为这是个大问题。你可以选择：
- 选择一个适合你应用程序的语义，
- 让你的应用程序完全不使用这个方法，或者
- 让你的应用程序避免受到这个问题的影响。
（例如，你可以让它忽略set方法的结果，或者如果有重复元素就抛出一个未检查的异常，或者在有重复时返回null或某个特殊对象。）
值得一提的是，自定义集合类违反接口约定并不是不可原谅的。实际上，连Java的设计者也会这样做——比如IdentityHashMap。真正不可原谅的是没有在javadocs中记录这些约定的违反。