Python HashMap的assign方法访问node.value报LinkedList无value属性问题排查

报错原因分析 #

报错的核心原因是你自定义的LinkedList类没有实现Python的迭代器协议，直接用for node in 链表实例遍历的时候，Python无法正确返回链表存储的Node实例，反而返回了LinkedList对象本身，访问.value属性自然就会提示不存在。 #

问题修复步骤 #

• 第一步：给LinkedList类添加迭代器支持
  要让LinkedList支持类似普通列表的遍历行为，需要在LinkedList类中实现__iter__方法，逐个返回链表中的节点实例，示例代码如下：

class LinkedList:
    # 保留你原有__init__、insert等已有方法不变
    def __iter__(self):
        current_node = self.head_node
        while current_node:
            yield current_node
            current_node = current_node.get_next_node()

如果你的Node类取下一个节点的方法名不是get_next_node()，替换成你自己的方法名即可。

• 第二步：修复assign方法逻辑
  原assign方法即使找到匹配key的节点修改了值，还是会额外插入新的重复节点，修改逻辑为匹配到key之后直接终止方法，不执行后续插入逻辑：

def assign(self, key, value):
    array_index=self.compress(self.hash(key))
    list_at_array = self.array[array_index]
    # 先遍历查找已存在的key
    for node in list_at_array:
        if node.value[0] == key: 
            node.value[1] = value
            # 找到匹配项直接返回，不插入新节点
            return
    # 遍历完没有找到匹配项再插入新节点
    payload = Node([key, value])
    list_at_array.insert(payload)

• 第三步：修复retrieve方法的多处逻辑错误
  原retrieve方法存在两个致命问题：一是首次遍历遇到不匹配的key就直接返回None，不会继续遍历后续节点；二是代码末尾引用了未定义的payload变量，修复后代码如下：

def retrieve(self, key):
    array_index = self.compress(self.hash(key)) 
    list_at_index = self.array[array_index]
    for node in list_at_index:
        if node.value[0] == key:
            return node.value[1]
    # 遍历完所有节点都没找到匹配项就返回None
    return None

额外说明 #

你询问的「直接向LinkedList实例插入节点时，是否需要让LinkedList支持普通列表的遍历行为」的答案是肯定的，只要实现上述的__iter__方法即可支持原生for遍历，不需要额外修改其他逻辑。

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