Универсальное хэширование, должно иметь одинаковое значение хэша для одного и того же ключа?

Question

Я имею в виду, что я использовал универсальную хэширующую функцию, используя это выражение:

h (k) = ((a * k + b) mod p) mod m; (от Кормена)

где: -p - большое простое число больше k; -a и b - это два числа, которые случайным образом выбирают первый в диапазоне [1, p-1], а второй - [0, p-1].

Теперь я реализовал это, и для случайной функции я выбрал семя, равное k. Это потому, что, если я этого не сделаю, когда я вставляю значение с ключом k, он генерирует хеш-значение, которое будет зависеть от значения по умолчанию для функции Random (возможно, времени). Поэтому, если я хочу снова искать ключ, я не могу этого сделать, потому что теперь универсальная хеширующая функция возвращает мне другое значение. Итак, я был бы признателен, если бы вы сказали мне, правильно ли я рассуждаю или нет. Я сомневаюсь, что теперь, если два элемента имеют один и тот же ключ, они будут ирримически сохранены в том же связанном списке (вещь, которую я не понял, если она правильная или нет).

Заранее спасибо.

Answer 1

Я думаю, что у вас есть небольшое недоразумение о том, как работает универсальное хэширование. Вместо того, чтобы выбирать a и b в случайном порядке каждый раз, когда вы вычисляете хэш, вместо этого, прежде чем делать какие-либо хэширования, выберите случайные a и b. Как только вы это сделаете, каждый раз, когда вам нужно вычислить хеш, перейдите и вычислите его, используя формулу выше, исходя из входного значения k и значений a и b, которые вы выбрали изначально.