\Section{Хеширование}{29 апреля}{Глеб Винерский}


\Subsection{Введение}
 
\begin{Def}
 
Хеш-функция.

Сжимающее отображение $h: U \rightarrow M$, $|U| > |M|$, $|M| = m$.
 
\end{Def}
 
\begin{Def}
 
Универсальная система хеш-функций.

$H$ - множество хеш-функций:

Для случайной $h \in H$, $\forall x,y$  $x \neq y$: $\underset{h \in H}{pr}[h(x) = h(y)] \leq \frac{1}{m}$.
 
\end{Def}

\begin{Def}
 
Универсальная система хеш-функций 2.

$\underset{h \in H}{\sum}[h(x) = h(y)] \leq \frac{|H|}{m}$.
 
\end{Def}

\begin{Thm}

$H_{p,m} = \{(a, b) : x \rightarrow ((ax+b) \mod p) \mod m \}$, $a \in [1, p), b \in [0, p)$ - универсальное для $|U| \le p$.

\begin{proof}

Зафиксируем входные $x, y: x \neq y$.
$$
 \begin{cases}
   ax + b \equiv r \pmod p \\
   ay + b \equiv s \pmod p
 \end{cases}
$$

$\underset{(a, b)}{\sum} = \underset{r \neq s}{\sum} [r \equiv s \pmod m] \le \frac{p(p-1)}{m} = \frac{|H|}{m}$

\end{proof}
\end{Thm}

\Subsection{Хеш-таблица}

Мы будем рассматривать реализацию на списках, которая использует случайную хеш-функцию $h$ из универсальной системы $H$.

$n$ - количество элементов в таблице, $m$ - количество списков.
\\

Оценим количество коллизий и матожидание длины списка.
\begin{MyList}
\item
Количество пар $x, y: x \neq y, h(x) = h(y)$

$E \le \frac{n(n-1)}{2} \cdot \frac{1}{m} \le \frac{n-1}{2}$

\item
Для фиксированного $x$, матожидание длины списка $h(x)$

$E \le (n-1)\frac{1}{m} + 1 \Rightarrow$
\end{MyList}

Add: $\O(1)$

Find, Del: $E = \O(1)$

\Subsection{Хеширование Кукушки}

Add: $E = \O(1)$

Find, Del: $\O(1)$ в худшем случае
\\

Заведём массив размера $m$ и две хеш-функции: $h_1, h_2 \in H$.

Find($x$): достаточно найти в любой из $h_1(x), h_2(x)$.

Del($x$): аналогично.

Add($x$): добавляем в любую из свободных $h_1(x), h_2(x)$. Если заняты обе - начинаем перемещать элементы в альтернативные ячейки. Берём элемент из $h_1(x)$ или $h_2(x)$ и перемещаем его в ячейку, соответствующую его второй хеш-функции, а в текущую помещаем новый элемент. Повторяем пока все элементы не найдут место. Если зациклились, то берём новые случайные $h_1, h_2$ и перестраиваем всю таблицу.

Если представить себе граф с рёбрами между $h_1(x)$ и $h_2(x)$, то можно понять, что циклов мало.

\Subsection{Perfect Hashing}

Даны $n$ элементов, необходимо построить хеш-функцию, сопоставляющую им числа от 0 до $m$-1 без коллизий. $n \le m$.

\begin{MyList}

\item
Двухуровневая схема

Возьмем $h \in H_{p,n}: x_i \rightarrow 0..n-1$.

Пусть в $i$-ой ячейке $k_i$ элементов. Заведём $h_i: x_i \rightarrow 0..k_i^2 - 1$.

\begin{Lm}

$\Pr[$у $h_i$ нет коллизий$] \ge \frac{1}{2}$

\begin{proof}

$E=\frac{k_i(k_i-1)/2}{k_i^2}$

\end{proof}

\end{Lm}

$E[\sum k_i^2] = E\left[\underset{x, y}{\sum}[h(x) = h(y)]\right] = \underset{x, y}{\sum} \Pr [h(x) =h(y)] = n + n(n-1)\frac{1}{n} = 2n - 1$

\begin{Lm}

$\Pr[\sum k_i^2 \le 4n] \ge \frac{1}{2}$

\end{Lm}

\item
Ацикличный граф

$x_i$ - ребро между $h_1(x_i)$ и $h_2(x_i)$.

$m$ вершин и $n$ рёбер.

\begin{Lm}

$m \ge 3n \Rightarrow \Pr[$нет циклов$] \ge \frac{1}{2}$

\end{Lm}

$hash(x_i) = (f[h_1(x_i)] + f[h_2(x_i)]) \mod m$, где $f$ - значение в вершине графа, которые проставляются обходом в глубину.

\end{MyList}