Блог

У меня есть класс хэш-таблицы. метод ‘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')
  

Чтобы подробнее остановиться на комментарии @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 s:

 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
  

Симметрия еще более заметна.