Python中支持O(1)查找、允许重复且保留插入顺序的数据结构咨询

符合需求的实现方案 #

你需要的是支持索引访问的有序多重集合，Python没有内置该结构，你可以选择第三方现成实现，也可以自行基于内置结构封装。

方案1：第三方库现成实现 #

直接使用ordered-multiset或者list-plus第三方库的对应结构即可，原生满足所有要求：

• O(1)时间复杂度的元素存在性校验，支持value in obj语法
• 严格保留元素插入顺序
• 支持通过索引随机访问元素
• 允许存储重复元素，不会做自动聚合统计

方案2：自行封装无依赖实现 #

核心思路是同时维护两个内置结构，不需要引入额外依赖，实现成本极低：

1. 普通list：按插入顺序存储所有元素，用于支持索引访问
2. defaultdict(set)：key为存储的元素，value为该元素在列表中所有出现位置的索引集合，用于支持O(1)的存在性校验

示例实现代码：

from collections import defaultdict

class OrderedMultiList:
    def __init__(self):
        self._element_list = []
        self._value_index_map = defaultdict(set)
    
    def append(self, value):
        # 插入元素时同步更新两个结构
        current_idx = len(self._element_list)
        self._element_list.append(value)
        self._value_index_map[value].add(current_idx)
    
    def __contains__(self, value):
        # 直接查询映射表，O(1)复杂度
        return value in self._value_index_map
    
    def __getitem__(self, index):
        # 直接查询列表，O(1)复杂度
        return self._element_list[index]
    
    # 可按需扩展删除、插入到指定位置等方法，注意操作时同步更新两个结构的映射关系即可

如果你的场景有高频删除需求，可以把存储元素的list替换为双向链表，映射表中存储对应链表节点的引用，避免删除元素时需要批量更新索引的性能损耗。

内容的提问来源于stack exchange，提问作者Jack Avante