Как увеличить хеш-таблицу?

Question

[iegor]

Простенькая задачка из problem solving with algorithms and data structures.
Есть хеш-таблица с определенным размером - равным простому числу.
При определенной заполненности необходимо увеличить ее размер, чтобы избежать чрезмерных коллизий.
Собственно как вычислить эту заполненность?
Как увеличить?(мое предположение в два раза и поиск ближайшего простого числа)
И что делать с элементами, которые уже есть в таблице? (хешировать заново по новому размеру?)
Для наглядности начало таблицы:

class Map:

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

    def put(self, key, data):
        hashvalue = self.hashfunction(key, len(self.slots))
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data
            else:
                nextslot = self.rehash(key, len(self.slots))
                while self.slots[nextslot] != None and \
                    self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot,len(self.slots))
                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                else:
                    self.data[nextslot] = data

Answer 1

[Mrrl]

Заполненность обычно берут 70-75% от размера таблицы. Можете также попробовать посчитать число шагов в цикле rehash, и если оно для какого-то элемента больше критической величины (например, 3 или 5), значит, пора.
"Умножить на 2 и взять следующее простое число" - нормально.
Хешировать заново, конечно, придётся - как же без этого :)
Кстати, то, что rehash не знает про исходный ключ - это правильно? Ведь так получается, что если для двух ключей rehash дал одинаковые результаты, то и вся последующая цепочка для них совпадёт, и будут повышаться шансы, что новые элементы будут попадать именно в эту цепочку.

Comments

[iegor]

При перехэшировании старых элементов необходимо создать временный словарь, куда занести все элементы, потом удалить все элементы из таблицы и занести заново из временного словаря в таблицу исходя из нового ее размера? Как то затратно по вычислениям и памяти выглядит.

[Mrrl]

iegor: Зачем временный словарь? Завести новую таблицу, потом пройтись по старой, и все её непустые элементы занести в новую. Старую удалить.
Если смущает то, что всё это происходит внутри одного класса - то перенести slots и data во временные переменные, проинициализировать класс заново исходя из нового размера, и, пройдясь по старому массиву slots, занести непустые данные в таблицу.

[iegor]

т.е. как то так - temp = Map(23) заношу все элементы в temp, а потом делаю temp новой таблицей. А как последний шаг сделать (сделать temp новой таблицей)?

[Mrrl]

Наоборот. Правда, я питона не знаю, но должно быть как-то так:

temp_slots=self.slots
temp_data=self.data

self.size = new_size
self.slots = [None] * self.size
self.data = [None] * self.size

Дальше проходите по temp_slots и temp_data, вызывая для всех данных метод put().

[iegor]

Mrrl: спасибо, реализовал так

temp_slots = self.slots
            temp_data = self.data
            self.__init__(23)
            for index,item in enumerate(temp_slots):
                if item != None:
                    self.put(item, temp_data[index])

осталось только функцию нахождения размера встроить

Answer 2

[sim3x]

Можно подсмотреть в питоне
https://www.youtube.com/watch?v=JhixzgVpmdM

Comments

[iegor]

посмотрел, ничего про хэш таблицы не увидел. Точно ты ссылка?

[sim3x]

iegor: обновил

[iegor]

sim3x: Вот это то, спасибо