|
| 1 | +#Хэш таблица |
| 2 | + |
| 3 | +**Хеш-таблица** - структура данных, реализующая абстрактный тип данных*ассоциативный массив*, т.е. структура, которая |
| 4 | +*связывает ключи со значениями*. Хеш-таблица использует*хеш-функцию* для вычисления индекса в массиве, в котором может |
| 5 | +быть найдено желаемое значение. Ниже представлена хеш-таблица, в которой ключём выступает имя человека, а значениями |
| 6 | +являются телефонные номера. Хеш-функция преобразует ключ-имя в индекс массива с телефонными номерами. |
| 7 | + |
| 8 | + |
| 9 | + |
| 10 | +В идеале хеш-функция будет присваивать элементу массива уникальный ключ. Однако большинство реальных хеш-таблиц |
| 11 | +используют несовершенные хеш-функции. Это может привести к ситуациям, когда хеш-функция генерирует одинаковый индекс для |
| 12 | +нескольких ключей. Данные ситуации называются коллизиями и должны быть как-то разрешены. |
| 13 | + |
| 14 | +Существует два варианта решения коллизий - хеш-таблица с цепочками и с открытой адресацией. |
| 15 | + |
| 16 | +Метод цепочек подразумевает хранение значений, соответствующих одному и тому же индексу в виде связного списка(цепочки). |
| 17 | + |
| 18 | + |
| 19 | +Метод открытой адресации помещает значение, для которого получен дублирующий индекс, в первую свободную ячейку. |
| 20 | + |
| 21 | + |
| 22 | +##Ссылки |
| 23 | + |
| 24 | +-[Wikipedia](https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0) |
| 25 | +-[YouTube](https://www.youtube.com/watch?v=rVr1y32fDI0) |
