Путаница, связанная с универсальным хешированием

Question

Я читал эту видео-лекцию, касающуюся универсального хеширования. Здесь показан пример хеширования IP-адресов. Каждый IP-адрес состоит из 4-, 32-битных целых чисел (x1,x2,x3,x4), причем любое значение xi имеет максимальное значение 255.

В учебнике говорится, что размер хеш-таблицы должен быть больше 255 или любого другого значения xis. Почему это так?

Answer 1

(Для тех из вас, кто не видел видео, это происходит около 20:45).

Определенный таким образом класс функций является функциями вида

h _a (x ₁, x ₂, x ₃, x ₄) = a ₁ x ₁ + a ₂ x ₂ + a ₃ x ₃ + a ₄ x ₄ (mod n)

где n - количество сегментов, каждый x _i находится в диапазоне от 0 до n - 1, каждый a _i находится в диапазоне от 0 до n - 1, а n - простое число.

Ваш вопрос заключается в том, почему все x _i должны быть меньше n. Причина связана с доказательством универсальности этого семейства хеш-функций. Как объясняет Тим ​​в видео, один из способов доказать универсальность хеш-функции - рассмотреть два разных входа (назовите их x и y). Это означает, что они должны различаться по некоторым компонентам, и идея состоит в том, чтобы предположить без потери общности, что они различаются по четвертому компоненту. То есть x ₄ y ₄. Немного математики, исходя из этого предположения, вы можете показать, что вероятность того, что вы получите столкновение, равна вероятности того, что это утверждение верно:

a ₄ (x ₄ - y ₄) = a ₁ (x ₁ - y ₁) + a ₂ (x ₂ - y ₂) + a ₃ (x ₃ - y ₃) (мод n)

Здесь, поскольку мы выбрали хэш-функцию случайным образом, все a _i являются случайными. Основная идея заключается в том, что если вы рассматриваете ₁, a ₂ и a ₃ как фиксированные значения, то в правой части этого уравнения просто некоторое фиксированное число k. Вы тогда заинтересованы в вероятности того, что

a ₄ (x ₄ - y ₄) = k (mod n)

Потому что мы предполагаем, что n> x ₄, что n> y ₄, что x ₄ n y ₄, и что n простое число. Это говорит нам о двух очень важных фактах:

1. x ₄ - y ₄ mod 0 мод n. Это главная причина того, что нам нужно, чтобы n было больше, чем x _i. Мы увидим почему через минуту.

2. x ₄ - y ₄ взаимно прост с n. Это почему? Ну, мы знаем, что n - простое число. Поскольку n> x ₄ и n> y ₄, мы знаем, что x ₄ - y ₄ должно находиться строго между n-1 и -(n-1). Поскольку мы предполагаем, что n простое, в этом диапазоне есть нетривиальные делители n, поэтому x ₄ - y ₄ и n взаимно просты.

Чтобы понять, почему эти факты имеют значение, давайте рассмотрим два случая для k. Во-первых, возможно, что k = 0. В таком случае, в каком случае будет ₄ (x ₄ - y ₄) = k (mod n)? Поскольку x ₄ - y ₄ ≠ 0, мы знаем, что это происходит только в том случае, если a ₄ = 0. Поскольку a ₄ принимает равномерно-случайное значение в диапазоне от 0 до n-1 включительно, вероятность того, что мы получим столкновение в этом дело 1/ н.

Далее предположим, что k ≠ 0. В таком случае, что должно произойти, чтобы ₄ (x ₄ - y ₄) = k (mod n) было истинным? Хорошо, мы знаем, что x ₄ - y ₄ ≠ 0, поэтому он должен иметь мультипликативный обратный модуль n, потому что x ₄ - y ₄ взаимно прост с n. На самом деле, он имеет ровно один мультипликативный обратный. Единственный возможный выбор _4, который приведет к тому, что это будет истинно, - это выбор, где a ₄ является мультипликативной обратной величиной x ₄ - y ₄ по модулю n, умноженному на k. Существует ровно один вариант выбора числа в диапазоне от 0 до n-1, который работает, поэтому вероятность его выбора равна 1/n.

Обратите внимание, что если x ₄ - y ₄ были равны нулю по модулю n, рассуждения, приведенные выше, не сработают. В первом случае любой выбор ₄ вызовет столкновение, поэтому вероятность столкновения будет равна 1. Во втором случае выбор ₄ не может вызвать столкновение, поэтому вероятность столкновения будет равна 0. Эти условия будут недействительными. доказательство.

Надеюсь это поможет!