Python实现特殊数组类的可行性：能否O(1)完成更新与查询？

核心思路是用数组+两个哈希表+双向链表队列的组合，解决更新操作中旧值索引的快速移除问题：

数据结构设计 #

• 基础数组 arr：存储每个索引对应的当前值，支持O(1)的索引访问与更新。
• 值到索引队列的哈希表 value_to_indices：键是数组中的值，值是一个双向链表实现的队列，按索引出现顺序存储该值的所有索引（队头为最早出现的索引），保证查询最早索引时直接取队头，O(1)完成。
• 索引到队列节点的哈希表 index_to_entry：键是数组索引，值是该索引在value_to_indices对应队列中的链表节点引用，支持O(1)找到并删除旧值对应的索引节点。

操作流程 #

1. 查询值的最早索引 #

直接从value_to_indices[val]的队列中取出队头元素即可，时间复杂度O(1)。如果val不在哈希表中，返回-1或自定义标识。

2. 按索引更新值 #

假设要更新索引i的旧值old_val为new_val：

• 如果old_val == new_val，无需操作，直接返回。
• 通过index_to_entry[i]找到value_to_indices[old_val]队列中对应的节点，O(1)删除该节点。如果删除后队列变为空，从value_to_indices中移除old_val键。
• 将索引i添加到value_to_indices[new_val]队列的队尾（如果new_val不存在则新建队列），并在index_to_entry[i]中记录这个新节点的引用。
• 更新arr[i]为new_val，完成操作。整个过程每一步都是O(1)。

为什么你之前的方法没成功？ #

如果只使用“值→最早索引”的哈希表，当更新的恰好是某个值的最早出现索引时，你需要重新遍历数组找下一个最早的索引，这会导致更新操作退化为O(n)。而通过存储所有索引的队列+索引到节点的映射，我们可以在O(1)时间内移除旧索引，无需遍历数组。

示例 #

初始数组：[2, 3, 2, 4]

• arr = [2, 3, 2, 4]
• value_to_indices: {2: [0, 2], 3: [1], 4: [3]}（队列用双向链表实现）
• index_to_entry: {0: 指向2队列的0节点, 1: 指向3队列的1节点, 2: 指向2队列的2节点, 3: 指向4队列的3节点}

更新索引0的值为5：

1. 取出old_val = 2，new_val = 5
2. 通过index_to_entry[0]找到2队列中的0节点，O(1)删除，2队列变为[2]
3. 为5新建队列并加入0，value_to_indices[5] = [0]，更新index_to_entry[0]指向该节点
4. 更新arr[0] = 5

此时查询2的最早索引为2，查询5的最早索引为0，均为O(1)；后续任意索引更新也都保持O(1)。

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