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

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

```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>

![](/files/YF3ui02RmqqmqmdblF9J)

```c
//пример реализации хэш-функции
long hash_function(char* str) {
    long i = 0;
    for (int j = 0; str[j]; j++)
        i += str[j];
    return i % CAPACITY;
}

//пример структуры хэш-таблицы
typedef struct Ht_item Ht_item;
struct Ht_item {
    char* key;
    char* value;
};
```

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

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

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

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

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

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

* Метод цепочек
* Открытая адресация\
  \~ линейное зондирование(пробирование)\
  \~ квадратичное зондирование(пробирование)\
  \~ двойное хэширование

## **Метод цепочек**

Проще понять этот метод на примере реализации  при разрешении коллизий:

* на ключ 002 претендуют два значения, которые организуются в линейный список.&#x20;

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

* Простыми словами: в хэш-таблице вместо ключа хранится массив ключей.

![](/files/IrzeNGQxgsLq724Jjgsg)

Такой метод используется в большинстве современных языков программирования(Python, Java и т.д.).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/30.-khesh-tablicy.-kollizii.-sposoby-razresheniya-kollizii.-metod-cepochek..md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.