Хеш-таблицы
Структура данных, использующая метод сопоставления больших диапазонов с меньшими, называется хеш-таблицей. Она хранит ключи и их значения, используя хэш-функцию для сопоставления. Хеш-таблица — это одна из наиболее эффективных структур данных со временем выполнения O(1) для поиска, вставки и удаления. В худшем случае, особенно когда связанные списки хранятся как значения, время выполнения может быть O(n).
С точки зрения структуры хеш-таблица больше похожа на массив; однако способ обращения к элементам отличается. В массиве элементы адресуются с использованием прямой адресации. При прямой адресации доступ к элементу в позиции k осуществляется с использованием значения индекса k. В хеш-таблицах ключи вычисляются с помощью хэш-функции. Суть хеш-таблицы заключается в возможности разработать хэш-функцию, которая эффективно отображает реальный или проблемный диапазон и диапазон, доступный (или выделенный) в компьютере. Хорошая хэш-функция может равномерно распределять реальные ключи в памяти компьютера без каких-либо коллизий. Коллизия возникает, когда два или более реальных ключа сопоставляются с одним ключом хеш-таблицы. Когда ключи проблемного пространства имеют очень большой диапазон, может оказаться невозможным иметь уникальные соответствующие ключи в хеш-таблице. В таких сценариях связанные списки используются для обеспечения дополнительной идентификации. Помимо ключа, можно сравнивать значения объектов. В таких реализациях в худшем случае поиск элемента в хэш-таблице может занять время O(n). Это в первую очередь потому, что задействованы связанные списки.
Ссылки: