哈希算法题目：常数时间插入、删除和获取随机元素

题目描述：
设计一个数据结构，支持在平均 O(1) 时间复杂度内执行以下操作：

1. insert(val)：向集合中插入元素 val
2. remove(val)：从集合中删除元素 val
3. getRandom()：随机返回集合中的一个元素，每个元素被返回的概率相等

解题过程：

步骤1：分析需求

• 插入和删除需要O(1)时间，这提示我们需要使用哈希表
• 随机获取需要等概率，这意味着我们需要能够通过索引直接访问元素
• 单独使用哈希表无法实现getRandom()的等概率要求
• 单独使用数组虽然可以随机访问，但删除操作需要O(n)时间

步骤2：设计数据结构组合
我们使用"数组+哈希表"的组合：

• 动态数组：存储实际的值，支持随机访问
• 哈希表：存储值到数组索引的映射，用于快速定位

步骤3：详细设计插入操作

1. 检查值是否已存在（通过哈希表）
2. 如果存在，返回false（避免重复）
3. 将值追加到数组末尾
4. 在哈希表中记录值对应的索引
5. 时间复杂度：O(1)

示例：插入值[1,2,3]
数组：[1,2,3]
哈希表：{1:0, 2:1, 3:2}

步骤4：详细设计删除操作
这是最复杂的部分，需要特殊技巧：

1. 检查值是否存在（通过哈希表）
2. 如果不存在，返回false
3. 获取要删除值的索引
4. 将数组最后一个元素移动到要删除的位置
5. 更新哈希表中该最后一个元素的索引
6. 删除数组最后一个元素
7. 从哈希表中删除要删除值的映射
8. 时间复杂度：O(1)

示例：删除值2
原状态：
数组：[1,2,3]，哈希表：{1:0, 2:1, 3:2}
操作过程：

• 将最后一个元素3移动到索引1位置：[1,3,3]
• 删除最后一个元素：[1,3]
• 更新哈希表：3→1，删除2的映射
  结果：数组：[1,3]，哈希表：{1:0, 3:1}

步骤5：详细设计获取随机操作

1. 生成一个随机索引（0到数组长度-1）
2. 返回数组中对应位置的元素
3. 时间复杂度：O(1)

步骤6：边界情况处理

• 空集合时调用getRandom()：返回错误或特定值
• 删除不存在的元素：返回false
• 插入重复元素：返回false

步骤7：代码实现思路

class RandomizedSet:
    def __init__(self):
        self.nums = []  # 存储值的数组
        self.val_to_index = {}  # 值到位置的映射
    
    def insert(self, val: int) -> bool:
        if val in self.val_to_index:
            return False
        self.val_to_index[val] = len(self.nums)
        self.nums.append(val)
        return True
    
    def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        
        # 将要删除的元素与最后一个元素交换
        index = self.val_to_index[val]
        last_val = self.nums[-1]
        
        # 交换位置
        self.nums[index] = last_val
        self.val_to_index[last_val] = index
        
        # 删除最后一个元素
        self.nums.pop()
        del self.val_to_index[val]
        return True
    
    def getRandom(self) -> int:
        return random.choice(self.nums)

这个设计巧妙地结合了数组的随机访问优势和哈希表的快速查找优势，通过元素交换技巧解决了删除操作的效率问题。