Как преобразовать линейный датчик в хэш-таблицу в квадратный датчик?

Question

Привет, я новичок в Python, и у меня есть хэш-таблица, которая использует линейное зондирование для разрешения конфликтов. Я знаю, что линейный зонд - это когда N+1,N+2, N+3, но квадратичный зонд - это когда n+1, n+4, n+9 ... Это моя заданная функция для линейного зондирования.

def __setitem__(self, key, value):
    position = self.hash_value(key)
    for _ in range(self.table_size):
        if self.array[position] is None:#found empty slot
            self.array[position] = (key, value)
            self.count += 1
            return
        elif self.array[position][0] == key:#found key
            self.array[position] = (key, value)#update value
            return
        else:#not found try next
            position = (position+1) % self.table_size
    raise ValueError("Table is Full!")

Чтобы преобразовать его в квадратичный зонд, я попытался изменить положение на

position = (position+(i+1)**2) % self.table_size

но ясно, что это неправильно, потому что квадратичный индекс добавляется к последней позиции, а не к исходной позиции? Любая помощь будет оценена!

Answer 1

Если вы заметили последовательность квадратичных чисел: 1, 4, 9, 16, 25, ...вы заметите, что разница между последовательными элементами 3, 5, 7, 9 то есть нечетные числа. Поэтому вы можете использовать переменную i который действует как счетчик / индекс и использует его для увеличения вашей позиции для следующей итерации следующим образом:

position = (position + (2 * i + 1)) % self.table_size

где position это индекс, который был только что использован для текущей итерации.

expected    |  i  |    new_position
1           |  0  |     0 + (2 * 0 + 1) = 1
4           |  1  |     1 + (2 * 1 + 1) = 4
9           |  2  |     4 + (2 * 2 + 1) = 9
16          |  3  |     9 + (2 * 3 + 1) = 16
25          |  4  |    16 + (2 * 4 + 1) = 25

Однако вам нужно будет изменить количество раз, которое вы увеличиваете i, Распространенный выбор - просто использовать длину таблицы, но вы должны знать, что при квадратичном зондировании можно не найти действительный индекс в таблице, даже если он существует, просто итерируя значения table_length, а иногда он может даже не найти его, даже если вы продолжай зондирование навсегда. Поэтому вам нужно быть осторожным, чтобы установить правильное ограничение на количество попыток выполнить одну операцию.

Кроме того, вы можете отслеживать первый рассчитанный / хешированный индекс и всегда рассчитывать position как:

current_position = original_position + i**2