Хаш-функция, $ h (k)=lfloor km \ Rfloor $ - простая форма для реальных $ k $ независимо, равномерно распределена в диапазоне $ 0 \ leq k <1 $

Question

Я проходил через текстовое введение в алгоритмы Cormen et. al. где я наткнулся на следующее утверждение:

Если известно, что ключей являются случайными реальными числами $ k $ независимо и равномерно распределены в диапазоне $ 0 \ leq k <1 $ , хеш-функция

$$ h (k)=lfloor km \ Rfloor $$ удовлетворяет условию простого равномерного перемешивания.

Теперь, что я могу понять, что они, вероятно, рассматривают равномерное нарушение в «постоянном» смысле, а не в дискретный смысл. Тогда имело место в дискретному смыслу, то предположим, что $ n $ Клавиши, функция массы вероятностей (PMF) должна быть постоянной и равной $ 1 / n $ И поэтому он должен быть одинаково, вероятно, для каждого ключа, который будет использоваться в хешинге - путем езжи на желаемый результат.

Но мы кажемся в беде, если распределение упоминается, является непрерывным (я чувствую себя так из-за линии: «равномерно распределен в Диапазон $ 0 \ leq k <1 $ ")

Пусть $ f (x) $ - связанная функция плотности вероятности (PDF) и из данной информации у нас есть $ f (x)= 1 $ , (который довольно легко найден, интегрируя $ f (x) $ в диапазоне $ 0 $ to $ 1 $ и приравнивающую его с помощью $ 1 $ и отмечая, что В равномерном распределении PDF является постоянным).

Теперь, хотя p.d.f постоянна, но p.d.f не является вероятностью. Скорее вероятность в точке спектра составляет $ 0 $ . Теперь, как использовать этот результат, чтобы добраться до претензии авторов.

или я полностью не виноват, что распределение будет непрерывным?

(есть ответ здесь , но он не входит в эту деталь, как вопрос другой Ведь).

Answer 1

$ h \ in [m] ^ u $ удовлетворяет простому унифицированному предположению одинакового хеширования, если когда $ x \ in u$ Одноредно выбрано во случайном порядке, то $ h (x) $ равномерно распределен по $ [m]$ или эквивалентно $ \ forall i \ in [m]: \ pr \ limits_ {x \ k u} [h (x)= i]=frac {1} {m} $ .В нашем случае у нас есть:

$ \ pr [h (x)= i]=pr \ big [\ lfloor mx \ Rfloor= i \ big]=pr [i \ le mx .

Мы использовали тот факт, что если $ x $ равномерно распределен по $ [0,1] $ Тогда $ \ pr [a \ le x \ le b]= ba $ (равенство держит со всеми четырьмя комбинациями $ \ le $ и $ <$ ).