是否有任何数据结构可以避免重复、保持顺序和随机访问

Java中的一个简单方法是创建一个实现两个包的包类。 Set 和 List 接口,其中包含 HashSet 和 ArrayList . 更新操作将需要同时更新两个内部集合,并且读取操作将被映射到任何一个提供正确语义和最佳性能的内部集合。唯一有点棘手的方法是 iterator() 你需要安排的地方 remove 更新两个集合。

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

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

跟进

我找不到实现 集合 和 表 接口。我认为原因是当您组合接口时,存在语义异常。例如,(如@colind notes)如果您调用 E set(int, E) 对于已经在列表中的元素,不清楚结果应该是什么。以一种让每个人都满意的方式来处理这件事可能是不可能的,我可以理解为什么他们可能决定不去油布坑游泳。

但是,如果您正在创建一个 集合 + 表 类以供应用程序的内部使用。你也不是

• 为适合您的应用程序选择一个语义,
• 将应用程序编码为根本不使用该方法,或者
• 编写应用程序代码以避免被异常情况咬伤。

(例如,您可以将其编码为忽略 set 方法,如果存在重复项,则引发未选中的异常,或者返回 null 或者有重复的可分辨对象。)

对于记录,自定义集合类不可原谅违反接口约定。事实上,即使是Java设计者也会这么做——见IdentityHashMap。不可原谅的是没有在javadocs中记录违反合同的行为。

如果可以使用不可变集合,请使用guava中的不可变集合,该集合具有aslist()视图以提供索引访问。

java.util.Set 不提供像get()和set()这样的随机访问方法,所以它的大多数/所有实现也不提供。您可以创建自己的 Set 这就提供了这个,可能有一个数组列表来保存数据。

LinkedHashset类提供了ToArray方法,该方法应该适合您的需要。

您不会找到这样做的基本数据结构;您要寻找的目标排除了所有这些目标。您可能会发现一个更为深奥的方法可以做到这一点,但最简单的方法是使用复合数据结构,并行维护两个数据结构。

就是这样 collections.OrderedDict 实际上是在引擎盖下。不过,这并不是你想要的:因为它不是为支持索引而设计的,所以它使用引擎盖下的链接列表来保存顺序。链表不能做索引——除非是慢的线性扫描,这通常是你想要避免的,因为如果在一个循环中使用链表,它会对你打开O(n^2)。

这是一个简单的实现。它维护两个数据结构:一个列表,保留项目设置时的顺序;一个dict,用于按键快速查找。二者都保存值,二者都保存对方的键:dict在列表中保存索引,list在dict中保存键。这使得从对方引用每个数据结构很容易,因此它可以有效地处理赋值和迭代。

注意,这并不是实现每个操作,只是基本操作:dict样式的赋值 a['x'] = 1 ,dict样式查找 a['x'] ,列表样式分配 a.set_value_by_index(0, 1) 和列表样式查找 a.get_value_by_index(0) .

还要注意:对于dict样式和list样式的操作,这并不是使用相同的语法。这很混乱,很邪恶,迟早会把你咬得很厉害。这个不转 a[0] 到列表样式的查找中;如果这是您想要的,则显式并使用 get_value_by_index . 不要 魔术 并尝试根据参数类型进行猜测。

最后,它提供了简单的dict样式迭代,像dict一样生成键。执行一些事情,比如 iteritems 和 itervalues 或者python3视图是明显的扩展。

class IndexableUniqueList(object):
    """
    >>> a = IndexableUniqueList()
    >>> a['x'] = 1
    >>> a['x']
    1
    >>> a['y'] = 2
    >>> a['y']
    2
    >>> a.get_key_by_index(0)
    'x'
    >>> a.get_value_by_index(0)
    1
    >>> a.get_key_by_index(1)
    'y'
    >>> a.get_value_by_index(1)
    2
    >>> a['x'] = 3
    >>> a.get_key_by_index(0)
    'x'
    >>> a.get_value_by_index(0)
    3
    >>> a.set_value_by_index(0, 4)
    >>> a['x']
    4
    >>> [val for val in a]
    ['x', 'y']
    """
    def __init__(self):
        self.items_by_index = []
        self.items_by_key = {}

    def __getitem__(self, key):
        return self.items_by_key[key][1]

    def __setitem__(self, key, value):
        if key in self.items_by_key:
            idx, old_value = self.items_by_key[key]
            self.items_by_key[key] = (idx, value)
            self.items_by_index[idx] = (key, value)
            return

        idx = len(self.items_by_index)
        self.items_by_key[key] = (idx, value)
        self.items_by_index.append((key, value))
    def get_key_by_index(self, idx):
        return self.items_by_index[idx][0]
    def get_value_by_index(self, idx):
        key = self.get_key_by_index(idx)
        return self.items_by_key[key][1]
    def set_value_by_index(self, idx, value):
        key = self.items_by_index[idx][0]
        self[key] = value
    def __iter__(self):
        for key, value in self.items_by_index:
            yield key