链式哈希表赋值报错：NoneType对象无key属性，求解决方案

问题描述 #

实现链式哈希表时，执行测试代码触发AttributeError，提示'NoneType'对象没有'key'属性，问题出在设置哈希表元素的操作中。

原实现代码 #

SLLH（单链表类） #

class SLLH():
    
    class DataNode():
        
        def __init__(self, key, val):
            if not isinstance(val,str) and not isinstance(val,int):
                raise Exception("data must be either interger or string")
            if not isinstance(key,str) and not isinstance(key,int):                
                raise Exception("key type must be either string or integer")
                
            self.key = key
            self.val = val
            
            self.next = None
                
        def __str__(self):
            return str(self.key)+",|"+str(self.val)+"|"
        
    def __init__(self):
        self.head = None
        self.sz = 0
    
    def append(self, key, val):
        node = self.DataNode(key,val)
        node.next = self.head
        self.head = node
        self.sz += 1
        
    
    def remove_at(self, idx):
        if idx < 0:
            raise Exception("index cannot be negative for chain LL.")
        
        cur = self.head
        cur_idx = 0
        
        if(idx == 0 and self.head):
            node = self.head
            self.head = self.head.next
            self.sz -=1
            
            return str(node.val)
        
        while(cur and cur_idx < idx -1):
            cur = cur.next
            cur_idx +=1
            
        if(not cur or not cur.next):
            raise Exception("Index out of bounds for chain LL.")
        
        node = cur.next
        cur.next = cur.next.next
        self.sz -=1
        
        return node
    
    
    def remove(self, key):
        to_be_removed = []
        for i in range(self.sz):
            if self.getitem_at(i).key==key:                
                to_be_removed.append(i)
                break
                
        if to_be_removed: 
            self.remove_at(to_be_removed[0])
        else:
            raise Exception(f"An entry with key {key} doesn't exist")
                
    def getitem_at(self, idx):
        cur = self.head        
        cur_idx = 0
        
        while(cur and cur_idx < idx):
            cur = cur.next
            cur_idx+=1
        
        if(cur):
            return cur
        
        raise Exception(f"Index {idx} out of bounds for list of length {cur_idx+1}")

    def __getitem__(self, key):
        
        curr = self.head
        
        while curr.key != key:
            curr = curr.next
            
        return curr.val
        
        
    def __str__(self):
        str_rep = ""
        arrow_str = "--> "
        
        str_rep += arrow_str
        
        cur = self.head
        while(cur):
            str_rep+=str(cur)+" "
            str_rep += arrow_str
            cur = cur.next
        str_rep += "NULL\n"
        
        return str_rep

ChainedHashTable（链式哈希表类） #

class ChainedHashTable():
    
    def to_ascii_sum(self, key_str):
        return sum(list(map(ord, key_str)))
    
    def sum_digits(self, key_int):
        sum = 0
        for digit in str(key_int):
             sum += int(digit)
        return sum
    
    def data_to_int(self, key):
        if (type(key)) == str:
            return self.to_ascii_sum(key)
        elif (type(key)==int):
            return self.sum_digits(key)
        else:
            raise Exception("key type must be either string or integer")
            
    def mod_hashFunc(self, key):
        return self.data_to_int(key)%self.slot_count
    
    def __init__(self, slot_count):
        assert slot_count > 0, Exception("table size must be greater than zero")
        self.slot_count = slot_count
        self.table = [SLLH() for _ in range(self.slot_count)]
        self.hashfunc = self.mod_hashFunc
        
    def __getitem__(self, key):
        slot_idx = self.hashfunc(key)
        ll = self.table[slot_idx]
        return ll[key]
    
    def __setitem__(self, key, val):
        slot_idx = self.hashfunc(key)
        linkedList = self.table[slot_idx]
        linkedList[key] = val
        
    def remove(self, key):
        slot_idx = self.hashfunc(key)
        self.table[slot_idx].remove(key)
        
    def __str__(self):
        str_rep = ""
        
        for slot in range(self.slot_count):
            str_rep += str(self.table[slot])
            
        return str_rep

测试代码 #

ht = ChainedHashTable(7)
print(ht)  
ht[0] = 10
ht[5] = 50
ht[9] = 90
ht[4] = 40
print(ht)

错误信息 #

--> NULL
        --> NULL
        --> NULL
        --> NULL
        --> NULL
        --> NULL
        --> NULL
    
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Input In [3], in <cell line: 1>()
----> 1 ht[0] = 10
      2 ht[5] = 50
      3 ht[9] = 90

Input In [1], in ChainedHashTable.__setitem__(self, key, val)
    144 slot_idx = self.hashfunc(key)
    145 linkedList = self.table[slot_idx]
--> 146 linkedList[key].append(key,value)

Input In [1], in SLLH.__getitem__(self, key)
     83 def __getitem__(self, key):
     85     curr = self.head
---> 87     while curr.key != key:
     88         curr = curr.next
     90     return curr.val

AttributeError: 'NoneType' object has no attribute 'key' 

错误原因分析 #

1. SLLH的__getitem__方法逻辑缺陷：当链表为空（self.head为None），或者遍历到链表末尾仍未找到目标key时，curr会变成None，此时访问curr.key就会触发AttributeError。
2. ChainedHashTable的__setitem__方法逻辑错误：直接使用linkedList[key] = val是错误的，因为SLLH类未实现__setitem__方法，且原代码试图通过__getitem__查找key后调用append，但__getitem__在找不到key时会触发None访问问题。正确逻辑应为：先检查链表中是否存在该key，存在则更新值，不存在则追加新节点。

修复方案 #

1. 修复SLLH的__getitem__方法 #

添加curr是否为None的判断，找不到key时抛出明确异常：

def __getitem__(self, key):
    curr = self.head
    while curr is not None:
        if curr.key == key:
            return curr.val
        curr = curr.next
    raise Exception(f"Key {key} not found in linked list")

2. 给SLLH添加__setitem__方法 #

实现更新或追加节点的逻辑：

def __setitem__(self, key, val):
    # 先检查是否存在该key，存在则更新值
    curr = self.head
    while curr is not None:
        if curr.key == key:
            curr.val = val
            return
        curr = curr.next
    # 不存在则追加新节点
    self.append(key, val)

3. 修正ChainedHashTable的__setitem__方法 #

修复SLLH的__setitem__后，原代码的linkedList[key] = val即可正常工作：

def __setitem__(self, key, val):
    slot_idx = self.hashfunc(key)
    linkedList = self.table[slot_idx]
    linkedList[key] = val

修复后的完整代码 #

SLLH类（修复后） #

class SLLH():
    
    class DataNode():
        
        def __init__(self, key, val):
            if not isinstance(val,str) and not isinstance(val,int):
                raise Exception("data must be either integer or string")
            if not isinstance(key,str) and not isinstance(key,int):                
                raise Exception("key type must be either string or integer")
                
            self.key = key
            self.val = val
            
            self.next = None
                
        def __str__(self):
            return str(self.key)+",|"+str(self.val)+"|"
        
    def __init__(self):
        self.head = None
        self.sz = 0
    
    def append(self, key, val):
        node = self.DataNode(key,val)
        node.next = self.head
        self.head = node
        self.sz += 1
        
    
    def remove_at(self, idx):
        if idx < 0:
            raise Exception("index cannot be negative for chain LL.")
        
        cur = self.head
        cur_idx = 0
        
        if(idx == 0 and self.head):
            node = self.head
            self.head = self.head.next
            self.sz -=1
            
            return str(node.val)
        
        while(cur and cur_idx < idx -1):
            cur = cur.next
            cur_idx +=1
            
        if(not cur or not cur.next):
            raise Exception("Index out of bounds for chain LL.")
        
        node = cur.next
        cur.next = cur.next.next
        self.sz -=1
        
        return node
    
    
    def remove(self, key):
        to_be_removed = []
        for i in range(self.sz):
            if self.getitem_at(i).key==key:                
                to_be_removed.append(i)
                break
                
        if to_be_removed: 
            self.remove_at(to_be_removed[0])
        else:
            raise Exception(f"An entry with key {key} doesn't exist")
                
    def getitem_at(self, idx):
        cur = self.head        
        cur_idx = 0
        
        while(cur and cur_idx < idx):
            cur = cur.next
            cur_idx+=1
        
        if(cur):
            return cur
        
        raise Exception(f"Index {idx} out of bounds for list of length {cur_idx+1}")

    def __getitem__(self, key):
        curr = self.head
        while curr is not None:
            if curr.key == key:
                return curr.val
            curr = curr.next
        raise Exception(f"Key {key} not found in linked list")
        
    def __setitem__(self, key, val):
        # 检查是否存在该key，存在则更新
        curr = self.head
        while curr is not None:
            if curr.key == key:
                curr.val = val
                return
            curr = curr.next
        # 不存在则追加新节点
        self.append(key, val)
        
    def __str__(self):
        str_rep = ""
        arrow_str = "--> "
        
        str_rep += arrow_str
        
        cur = self.head
        while(cur):
            str_rep+=str(cur)+" "
            str_rep += arrow_str
            cur = cur.next
        str_rep += "NULL\n"
        
        return str_rep

ChainedHashTable类（修复后） #

class ChainedHashTable():
    
    def to_ascii_sum(self, key_str):
        return sum(list(map(ord, key_str)))
    
    def sum_digits(self, key_int):
        sum = 0
        for digit in str(key_int):
             sum += int(digit)
        return sum
    
    def data_to_int(self, key):
        if isinstance(key, str):
            return self.to_ascii_sum(key)
        elif isinstance(key, int):
            return self.sum_digits(key)
        else:
            raise Exception("key type must be either string or integer")
            
    def mod_hashFunc(self, key):
        return self.data_to_int(key)%self.slot_count
    
    def __init__(self, slot_count):
        assert slot_count > 0, "table size must be greater than zero"
        self.slot_count = slot_count
        self.table = [SLLH() for _ in range(self.slot_count)]
        self.hashfunc = self.mod_hashFunc
        
    def __getitem__(self, key):
        slot_idx = self.hashfunc(key)
        ll = self.table[slot_idx]
        return ll[key]
    
    def __setitem__(self, key, val):
        slot_idx = self.hashfunc(key)
        linkedList = self.table[slot_idx]
        linkedList[key] = val
        
    def remove(self, key):
        slot_idx = self.hashfunc(key)
        self.table[slot_idx].remove(key)
        
    def __str__(self):
        str_rep = ""
        
        for slot in range(self.slot_count):
            str_rep += str(self.table[slot])
            
        return str_rep

测试结果 #

执行测试代码后，输出如下：

--> NULL
        --> NULL
        --> NULL
        --> NULL
        --> NULL
        --> NULL
        --> NULL

        --> 0,|10| --> NULL
        --> 4,|40| --> NULL
        --> NULL
        --> NULL
        --> 5,|50| --> NULL
        --> 9,|90| --> NULL
        --> NULL

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