Удаление элементов из хэш таблицы

Question

Всем здравствуйте! Делаю несложную хэш таблицу. Для этого написал вот такой класс:

class HashTable:
    size = 20

    def __init__(self):
        self.data = [None] * self.size

    def __getitem__(self, key):
        h = self.get_hash(key)
        try:
            while self.data[h]:
                if self.data[h] and self.data[h]["key"] == key:
                    return self.data[h]
                h = self.get_rehash(h)
        except IndexError:
            return

    def __setitem__(self, key, value):
        h = self.get_hash(key)
        if self.data[h] is None:
            self.data[h] = {"key": key, "value": value}
            return

        next_h = self.get_rehash(h)
        try:
            while self.data[next_h] is not None:
                if self.data[next_h]["key"] == key:
                    self.data[next_h]["key"] = value
                    break
                next_h = self.get_rehash(next_h)
        except IndexError:
            raise
        self.data[next_h] = {"key": key, "value": value}

    def get_hash(self, name):
        return len(name) % self.size

    def get_rehash(self, oldhash):
        return oldhash + 1

Исходные данные для формирования хэш таблицы такие:

d = {'Водоросли': 280,
 'Картофель': 260,
 'Лук-порей': 59,
 'Манго': 291,
 'Орехи грецкие': 266,
 'Салями': 225,
 'Специи': 283,
 'Сыр сливочный': 152,
 'Творог': 215,
 'Тофу': 142,
 'Хек': 248,
 'Чай черный': 118,
 'Чернила каракатицы': 95,
 'Шампиньоны': 101,
 'Финик': 104}

table = HashTable()
for k, v in d.items():
    table[k] = v

print(table.data)

Для удаления элемента из хэш таблицы написал такую функцию в классе

def delete(self, key):
    h = self.get_hash(key)
    if self.data[h]["key"] == key:
        self.data[h] = None
        return

    h_next = self.get_rehash(h)
    try:
        while self.data[h_next] is not None:
            if self.data[h_next]["key"] == key:
                self.data[h_next] = None
                break
            h_next = self.get_rehash(h_next)
    except IndexError:
        raise
    self.data[h_next] = None

Но работает она не совсем правильно. Если я, например, удаляю элемент по ключу "Водоросли", то потом не могу найти "Картофель" и "Лук-порей", т.к. у них одинаковый хэш (9). Помогите сделать корректное удаление.

Спасибо!

Answer 1

По идее нужно при удалении помечать место в хеш-таблице специальным маркером, который при дальнейшем поиске нужно пропускать.

Вот, попытался что-то изобразить с минимумом изменений:

class HashTable:
    class Deleted:
        pass
    size = 20

    def __init__(self):
        self.data = [None] * self.size

    def __getitem__(self, key):
        h = self.get_hash(key)
        try:
            while self.data[h]:
                while isinstance(self.data[h], HashTable.Deleted): # skip deleted
                    h = self.get_rehash(h)
                if self.data[h] and self.data[h]["key"] == key:
                    return self.data[h]
                h = self.get_rehash(h)
        except IndexError:
            return

    def __setitem__(self, key, value):
        h = self.get_hash(key)

        try:
            while self.data[h] is not None:
                if self.data[h]["key"] == key:
                    self.data[h]["key"] = value
                    return
                h = self.get_rehash(h)
        except IndexError:
            raise
        self.data[h] = {"key": key, "value": value}

    def get_hash(self, name):
        return len(name) % self.size

    def get_rehash(self, oldhash):
        return oldhash + 1

    def delete(self, key):
        h = self.get_hash(key)
        if self.data[h] and self.data[h]["key"] == key:
            self.data[h] = HashTable.Deleted()
            return

        h_next = self.get_rehash(h)
        try:
            while self.data[h_next] is not None:
                while isinstance(self.data[h_next], HashTable.Deleted): # skip deleted
                    h_next = self.get_rehash(h_next)

                if self.data[h_next]["key"] == key:
                    self.data[h_next] = HashTable.Deleted()
                    break
                h_next = self.get_rehash(h_next)
        except IndexError:
            raise
        self.data[h_next] = None

d = {'Водоросли': 280,
 'Картофель': 260,
 'Лук-порей': 59,
 'Манго': 291,
 'Орехи грецкие': 266,
 'Салями': 225,
 'Специи': 283,
 'Сыр сливочный': 152,
 'Творог': 215,
 'Тофу': 142,
 'Хек': 248,
 'Чай черный': 118,
 'Чернила каракатицы': 95,
 'Шампиньоны': 101,
 'Финик': 104}

table = HashTable()
for k, v in d.items():
    table[k] = v

print(*table.data,'\n', sep='\n')

table.delete('Водоросли')
print(*table.data,'\n', sep='\n')

print(table['Картофель'])

Периодически необходимо запускать ремаппинг, с очисткой удалённых слотов и переразмещением элементов по пересчитанным в связи с этим «адресам»

Также rehash+=1 недостаточно, нужно замыкать пространство индексов в кольцо, останавливаясь после полного прохода.

Размер хранилища/область определения хеш-функции слишком малы по сравнению с количеством элементов, которые вы пытаетесь в нём хранить.

БЛОГ НА HUSL

Удаление элементов из хэш таблицы

Ответы (1 шт):