Данный метод требует фиксированного, обычно малого времени на выполнение операции поиска. Выделяют 2 вида хеширования:
- Открытое, внешнее или расширенное
- Закрытое, внутреннее или прямое
  
Термин "хеширование" произошел от глагола "to hash" - рубить, измельчать, перемешивать. Все множество значений ключа разбивается на $B$ классов, пронумерованных от $0$ до $B-1$. Далее строится хеш-функция $h$, что для любого элемента $x$ из исходного множества ключей функция $h(x)$ принимает целочисленные значения из отрезка от $0$ до $B-1$. Это значение и есть номер класса, в который помещается элемент $x$.
## Открытое хеширование
Хеш-таблица представляет собой $B$ указателей, каждый из которых хранит адрес списка элементов с одним и тем же хешем, равным индексу ячейки. 
Пример:  
```
13, 19, 3, 52, 59, 14, 64, 69, 34
```
$B = 5$, $h(x) = x$ % $B$    
![Хеш-таблица](../Pictures/10_01.%20Хеш-таблица.png)  
Поиск по такой таблице происходит вычислением значения $h(x)$ и прохождением по списку сегмента $x$. Например, нахождение элемента 52 произойдет на 1 шаге. Самые большие проблемы происходят в 4 сегменте. Ситуация, когда 2 элемента имеют один и тот же хеш, называется **коллизией**. Размер таблицы $B$ и вид хеш-функции $h$ обычно выбираются такими, чтобы количество коллизий сводилось к минимуму. 
## Закрытое хеширование
При закрытом хешировании в таблице сегментов хранятся сами элементы. Поэтому в каждом сегменте может находится лишь 1 элемент. А это значит, что в закрытой хеш-таблице не может быть размещено более $B$ элементов, где $B$ - размер таблицы. Кроме того, возникают проблемы в виде коллизий. На помощь приходит **технология повторного хеширования**.  
Если на функции $h_0(x)$ произошла коллизия, к объекту применяются функции $h_1(x)$, $h_2(x)$, ..., пока не будет найдена свободная ячейка. Вид функции для повторного хеширования может быть, например, такой: $h_i(x)=(h_0(x)+i)$ % $B$  
При закрытом хешировании возникает еще одна проблема - удаление элементов. Сегмент, из которого удален элемент, с одной стороны должен быть пустым, чтобы в него можно было поместить новый, а с другой - не совсем пустым, чтобы не потерять элементы с тем же хешем, расположенные из-за коллизии после удаленной ячейки. Поэтому в закрытой хеш-таблице помимо хешей приходится держать еще 2 значения: пустая ячейка (в нее производится новая запись и до нее поиск элементов) и  "удаленная" ячейка (в нее также возможна запись, но поиск элементов в случае коллизии продолжается дальше)  

| 0   | 1   | 2   | 3   | 4   | 5   | 6         | 7   | 8   | 9   |
| --- | --- | --- | --- | --- | --- | --------- | --- | --- | --- |
|     |     |     |     | 4   | 14  | ~~44~~ 34 | 54  |     |     |

  
Вставить **4, 14, 44, 54**  
Удалить **44**  
Вставить **34**  
Формула выше является не очень хорошей с точки зрения разрешения коллизий при закрытом хешировании. Поэтому рекомендуют использовать другие варианты.  
Например: $h_i(x)=(h_0(x)+С_i)$ % $B$, где на каждом $i$-том шаге $C_i$ - новая константа, взаимно простая с $B$.  
$h_i(x)=(h_0(x)+d_i)$ % $B$, где $d_1, d_2, d_3, ..., d_{B-1}$ - некоторая перестановка чисел $1$, $2$, $3$, ... $B-1$.