哈希表和键的最后一个值

Question

我有一类哈希表。方法“add”添加键和值。当我为同一个键添加另一个值时，我希望将旧值替换为新值。但我不知道我要改变什么：）

class HashNode:
    def __init__(self, key, value):
        self.next = None
        self.key = key
        self.value = value


class HashTable:
    def __init__(self):
        self.table = [None] * 1000

    def hash(self, key):
        hashed = 0
        for i in range(len(key)):
            hashed = (256 * hashed + ord(key[i])) % 1000
        return hashed

    def add(self, key, value):
        bucket = self.hash(key)
        if self.table[bucket]:
            temp = self.table[bucket]
            while temp.next:
                temp = temp.next
            temp.next = HashNode(key, value)
        else:
            self.table[bucket] = HashNode(key, value)

    def find(self, key):
        bucket = self.hash(key)
        if not self.table[bucket]:
            return 'none'
        else:
            temp = self.table[bucket]
            while temp:
                if temp.key == key:
                    return temp.value
                temp = temp.next
            return 'none'

            

table = HashTable()
table.add('a', 1)
table.add('a', 2)

我正在获取键值“1”，但我想要“2”

table.find('a')

Answer 1

详细说明@mkrieger1的评论：您的问题是为什么存储桶不是简单的单元格，以及为什么将密钥存储在存储桶中。如果没有冲突，即key1 != key2意味着hash(key1) != hash(key2)¹，则不需要存储密钥：

def add(self, key, value):
    bucket = self.hash(key)
    self.table[bucket] = value

def find(self, key, value):
    bucket = self.hash(key)
    return self.table[bucket]

但是你可能有碰撞。这就是为什么要使用链表为具有相同散列的键存储几个(key, value)对。您在find方法中正确处理了冲突：

temp = self.table[bucket]
while temp:
    if temp.key == key:      # key found!
        return temp.value    # return the value
    temp = temp.next
return 'none' # why not None?

您应该在add方法中执行相同的操作：

temp = self.table[bucket]
while temp.next:
    if temp.key == key:     # key found!
        temp.value = value  # update the value
        return              # and return
    temp = temp.next
temp.next = HashNode(key, value) # key not found: create the entry

这两种方法现在是对称的

¹在数学术语中，hash是内射的。假设某些条件很少满足，这在理论上是可能的

---

备注：您可以利用查找HashNode的方法：

def _find(self, bucket, key):
    temp = self.table[bucket]
    while temp:
        if temp.key == key:
            return temp
        temp = temp.next
    return None

并在开始处插入新键：

def add(self, key, value):
    bucket = self.hash(key)
    node = self._find(bucket, key)
    if node is None:
        self.table[bucket] = HashNode(key, value, self.table[bucket]) # last parameter is next
    else:
        node.value = value

def find(self, key):
    bucket = self.hash(key)
    node = self._find(bucket, key)
    if node is None:
        return None
    else:
        return node.value

对称性更加明显