Что такое хэш-таблица

Хэш-таблица — это структура данных, которая хранит пары ключ–значение и использует хэш-функцию для быстрого доступа к элементам по ключу.

При хорошей хэш-функции и умеренном числе коллизий операции поиска, вставки и удаления в хэш-таблице в среднем выполняются за O(1).

Определение:

• Данные хранятся в виде пар ключ-значение.
• Хэш-функции принимают ключ и возвращают выходные данные, соответствующие только этому ключу.
• Этот процесс называется хэшированием: однозначным сопоставлением друг другу входных и выходных данных.
• Хэш-функции возвращают для данных уникальные адреса в памяти.

Что вам нужно знать:

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

Эффективность («O» большое, в среднем случае):

• Индексирование: хэш-таблицы — O(1)
• Поиск: хэш-таблицы — O(1)
• Вставка: хэш-таблицы — O(1)