如何实现具备无序映射渐近复杂度的Python类并支持O(1)等概率取元素？

要同时满足插入、删除、随机返回元素三个操作的O(1)渐近复杂度，仅依赖Python原生字典无法达成——因为从字典生成列表的操作是O(N)。正确的做法是结合哈希表和动态数组两种结构，用数组维护元素的可随机访问性，用哈希表记录元素的位置信息。

核心设计思路 #

• 哈希表（key_map）：存储key到「数组索引+对应value」的映射，保证插入、查找操作的O(1)效率。
• 动态数组（elements）：存储所有key，利用数组随机访问的特性，实现O(1)时间的随机元素选取。
• 删除操作时，通过将待删除元素与数组末尾元素交换，避免数组中间删除的O(N)开销，仅需更新哈希表中对应元素的索引即可。

完整实现代码 #

import random

class UnorderedMap:
    def __init__(self):
        self.key_map = {}  # 结构: key -> (index_in_elements, value)
        self.elements = [] # 存储所有key，用于快速随机访问

    def insert(self, key, value):
        if key in self.key_map:
            # 若key已存在，直接更新对应value
            idx, _ = self.key_map[key]
            self.key_map[key] = (idx, value)
            return
        # 新key：添加到数组末尾，记录索引和value
        self.elements.append(key)
        self.key_map[key] = (len(self.elements) - 1, value)

    def remove(self, key):
        if key not in self.key_map:
            raise KeyError(f"Key {key} not found")
        
        idx_to_remove, _ = self.key_map[key]
        # 取出数组最后一个元素的key
        last_key = self.elements.pop()

        # 若删除的不是最后一个元素，将最后一个元素移到待删除位置并更新索引
        if idx_to_remove != len(self.elements):
            self.elements[idx_to_remove] = last_key
            self.key_map[last_key] = (idx_to_remove, self.key_map[last_key][1])
        
        # 删除当前key的映射
        del self.key_map[key]

    def get_random_element(self):
        if not self.elements:
            raise IndexError("UnorderedMap is empty")
        # 随机选一个key，返回对应的value
        random_key = random.choice(self.elements)
        return self.key_map[random_key][1]

各操作复杂度说明 #

• insert：无论是新增key还是更新已有key，都是哈希表的O(1)操作，数组追加元素也是O(1)。
• remove：哈希表查找、数组末尾弹出、索引更新均为O(1)，无遍历操作。
• get_random_element：random.choice直接通过随机索引访问数组元素，是O(1)操作，再通过哈希表取value也是O(1)。

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