Хеш-таблица это разреженный массив (массив, в котором имеются незаполненные позиции). В стандартных англоязычных учебниках ячейки хеш-таблицы называются "bucket". В хеш-таблице dict каждому элементу соотвествует ячейка, содержащая два поля: ссылку на ключ и ссылку на значение элемента. Поскольку размер всех ячеек одинаков, доступ к отдельной ячейке производится по смещению.

Python стремится оставить не менее трети ячеек пустыми; если хеш-таблица становится чрезмерно заполненной, то она копируется в новый участок памяти, где есть место для большего числа ячеек.

Для помещения элемента в хеш-таблицу нужно первым делом вычислить хеш-значение ключа элемента. Это делает встроенная функция hash().

Для выборки значения с помощью выражения my_dict[search_key] Python обращается к функции hash(search_key), чтобы получить хеш-значение search_key, и использует несколько младших битов полученного числа как смещение ячейки относительно начала хеш-таблицы (сколько именно битов зависит от текущего размера таблицы). Если найденная ячейка пуста, возбуждается исключение KeyError. В противном случае, в найденной ячейке есть какой-то элемент - пара ключ:значение - и тогда Python проверяет, верно ли то, что search_key == found_key. Если да, то элемент найден и возвращается found_value. Если же search_key и found_key не совпали, то имеет место коллизия хеширования. Для разрешения коллизии алгоритм берет различные биты хеш-значения, производит над ними определенные действия и использует результат как смещение другой ячейки.

Oct. 12, 2023, Источник

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

Oct. 12, 2023, Источник

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

Вот основные шаги работы:

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

2. Разрешение коллизий: Поскольку разные ключи могут быть преобразованы в один и тот же хэш (коллизия), необходимо иметь механизм разрешения коллизий. Существуют различные методы разрешения коллизий, такие как метод цепочек (chaining) и метод открытой адресации (open addressing).

• Метод цепочек: В этом методе каждая ячейка представляет собой связный список элементов с одним и тем же хэшем. При коллизии элемент добавляется в соответствующий список.

    

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

3. Доступ к элементам: Для доступа к элементу нужно выполнить следующее:

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

4. Вставка и удаление элементов: Процесс вставки и удаления элементов аналогичен процессу доступа к элементам. Сначала вычисляется хэш ключа, затем используется метод разрешения коллизий для вставки или удаления элемента.

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

Feb. 18, 2024, easyoffer