03 — Карта (Map) и хэш-таблица (hash map), хэш-функции и коллизии

Карта (Map)

Её ещё называют ассоциативным массивом или словарём. Данные здесь хранятся в паре «ключ/значение», причем каждый ключ уникален, а вот значения могут повторяться. То есть определённому уникальному ключу всегда соответствует конкретное значение.

Зная ключ, данные в Map можно искать быстрее, чем в других структурах.

Как применяют Карту:

• Для быстрого поиска данных.
• Для создания баз, в которых нужно хранить уникальное соответствие между двумя множествами значений. Их помещают в ключ, и структура проверяет, чтобы ключ не повторялся.

Хэш-таблица (Hash map)

Частный случай map — это hash-map, или хэш-таблица. В ней есть ключи и значения, а для их реализации добавляются индексы. Специальная хэш-функция позволяет по ключу вычислить индекс, чтобы найти нужные данные.

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

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