为键值哈希结构添加undo/redo功能，咨询Python栈适用性

Python中的栈完全可以用来实现哈希表的撤销（undo）和重做（redo）功能，核心思路是用两个栈配合记录操作历史：

• undo_stack：存储所有修改哈希表状态的操作（仅put/remove，get不改变状态无需记录），每执行一次修改操作，就把能反向恢复该操作的信息存入栈。
• redo_stack：存储被撤销的操作，每次执行undo时，把当前被撤销的操作存入这个栈，后续可以通过redo重新执行。

具体实现逻辑 #

每次执行put或remove时，先记录操作前的状态：

• 执行put时：先获取key的旧值，将操作类型、key、旧值、新值存入undo_stack，再执行原put逻辑。
• 执行remove时：先获取key的旧值（如果存在），将操作类型、key、旧值存入undo_stack，再执行原remove逻辑。

undo操作时：

1. 从undo_stack弹出最近一次操作记录。
2. 根据操作类型执行反向恢复：
   • 若原操作是put：如果旧值是-1（说明是新增key），则删除该key；否则将key恢复为旧值。
   • 若原操作是remove：将key和旧值重新存入哈希表。
3. 把当前被撤销的操作存入redo_stack，方便后续重做。

redo操作时：

1. 从redo_stack弹出最近一次被撤销的操作记录。
2. 根据操作类型重新执行原操作：
   • 若原操作是put：重新执行put(key, 新值)。
   • 若原操作是remove：重新执行remove(key)。
3. 把重做后的操作重新存入undo_stack。

修改后的完整代码 #

class Bucket:
    def __init__(self):
        self.bucket = []
    
    def get(self, key):
        for(k, v) in self.bucket:
            if k == key:
                return v
        return -1
    
    def update(self, key, value):
        found = False
        for i, kv in enumerate(self.bucket):
            if key == kv[0]:
                self.bucket[i] = (key, value)
                found = True
                break
        if not found:
            self.bucket.append((key, value))

    def remove(self, key):
        for i, kv in enumerate(self.bucket):
            if key == kv[0]:
                del self.bucket[i]
                return kv[1]  # 返回删除前的值，方便记录历史
        return -1  # 没有找到该key，返回-1


class MyHashMap:
    def __init__(self):
        self.key_space = 2069
        self.hash_table = [Bucket() for i in range(self.key_space)]
        self.undo_stack = []  # 存储操作历史，元素格式：(操作类型, key, 旧值, 新值)
        self.redo_stack = []  # 存储被撤销的操作，格式同undo_stack

    def put(self, key: int, value: int) -> None:
        hash_key = key % self.key_space
        old_value = self.hash_table[hash_key].get(key)
        # 记录操作历史：('put', key, 旧值, 新值)
        self.undo_stack.append(('put', key, old_value, value))
        # 清空redo栈：执行新操作后，之前的redo记录失效
        self.redo_stack.clear()
        self.hash_table[hash_key].update(key, value)

    def get(self, key: int) -> int:
        hash_key = key % self.key_space
        return self.hash_table[hash_key].get(key)

    def remove(self, key: int) -> None:
        hash_key = key % self.key_space
        old_value = self.hash_table[hash_key].remove(key)
        if old_value != -1:
            # 仅当确实删除了存在的key时，记录操作历史：('remove', key, 旧值)
            self.undo_stack.append(('remove', key, old_value))
            # 清空redo栈
            self.redo_stack.clear()

    def undo(self) -> None:
        if not self.undo_stack:
            return  # 没有可撤销的操作
        operation = self.undo_stack.pop()
        if operation[0] == 'put':
            _, key, old_value, new_value = operation
            hash_key = key % self.key_space
            if old_value == -1:
                # 原操作是新增key，反向操作是删除
                self.hash_table[hash_key].remove(key)
            else:
                # 原操作是更新key，反向操作是恢复旧值
                self.hash_table[hash_key].update(key, old_value)
            # 将该操作存入redo栈，方便后续重做
            self.redo_stack.append(operation)
        elif operation[0] == 'remove':
            _, key, old_value = operation
            hash_key = key % self.key_space
            # 反向操作是恢复被删除的key
            self.hash_table[hash_key].update(key, old_value)
            self.redo_stack.append(operation)

    def redo(self) -> None:
        if not self.redo_stack:
            return  # 没有可重做的操作
        operation = self.redo_stack.pop()
        if operation[0] == 'put':
            _, key, old_value, new_value = operation
            self.put(key, new_value)
            # 注意：put方法会自动清空redo栈并将操作存入undo栈，这里无需重复操作
        elif operation[0] == 'remove':
            _, key, old_value = operation
            self.remove(key)
            # remove方法会自动清空redo栈并将操作存入undo栈

关键细节说明 #

1. Bucket类修改：给remove方法添加了返回值，返回删除前的value，方便记录操作历史。
2. 操作记录格式：put操作记录包含旧值和新值，remove操作仅记录旧值。
3. redo栈清空逻辑：每次执行新的put/remove操作时，清空redo_stack——因为新操作会打断原有操作序列，之前的redo记录不再有效。
4. 边界处理：undo和redo方法会先检查栈是否为空，避免无操作可执行时出错。

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