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

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

0 голосов
/ 20 мая 2018

Привет, я новичок в 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

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

1 Ответ

0 голосов
/ 20 мая 2018

Если вы заметите последовательность квадратичных чисел: 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
...