# 31. Хеш-таблицы. Коллизии. Способы разрешения коллизий. Открытая адресация

**Хэш-таблица** - структура данных, в которой все элементы хранятся в виде пары "ключ-значение". По-другому, это ассоциативный массив. Самый частный пример хэш-таблицы - словарь.

```c
data_1["BMSTU"] = "МГТУ"
DATA_2[3.14] = "Pi"
```

**Хэширование -** процесс преобразования ключа в некоторый индекс с помощью некоторой функции, которую также называют **хэш-функцией.**

<pre class="language-c"><code class="lang-c"><strong>h("a") -> 1
</strong>h("b") -> 2
h("c") -> 3
</code></pre>

![](https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2FxD7HduVua4tfx3cwT6P1%2Fimage.png?alt=media\&token=5215a1f0-920b-4e4e-8815-9815ab352be2)

### Преимущества хэш-таблиц:

* Сложность алгоритма: О(n)
* Быстрый поиск
* Равномерное распределение в памяти

### Недостатки хэш-таблиц:

Зачастую возникают проблемы в связи с ограниченностью размера типа данных "значений".  Количество ключей и количество значений может не совпадать, из-за этого возникает **коллизия хэш-функций**.

## **Коллизия хэш-функции** - получение одинакового индекса для разных ключей.&#x20;

Существует 2 основных типа борьбы с коллизиями:

* Метод цепочек
* Открытая адресация(3 типа)

**Линейное зондирование(пробирование)**\
\
\&#xNAN;*Линейное опробование* сводится к последовательному перебору сегментов таблицы с некоторым фиксированным шагом

```c
h'(k, i) = (h(k) + i) % size;
```

**Минус:** метод приводит к образованию кластеров (когда несколько ячеек подряд заняты). Кластер приводит к тому, что увеличивается время доступа к данным.

**Квадратичное зондирование(пробирование)**

*Квадратичное опробование* отличается от линейного тем, что шаг перебора сегментов нелинейно зависит от номера попытки найти свободный сегмент:

```c
h'(k, i) = (h(k) + a*i + b*i*i) % size;
```

**Минус:** относительно небольшое число проб может быстро при­вести к выходу за адресное пространство небольшой таблицы вслед­ствие квадратичной зависимости адреса от номера попытки.

**Двойное хеширование**

Двойное хеширование основано на нелинейной ад­ресации, достигаемой за счет суммирования значений основной и дополнительной хеш-функций

```c
h'(k, i) = (h1(k) + i*h2(k)) % size;
```

Минус: нерациональное использование огромного количества памяти.