Что такое хеширование?

Предположим, мы хотим разработать систему хранения записей о сотрудниках с номерами телефонов (в качестве ключей ). И мы хотим, чтобы следующие запросы выполнялись эффективно:

1. Введите номер телефона и соответствующую информацию.
2. Найдите номер телефона и получите информацию.
3. Удалить номер телефона и связанную с ним информацию.

Мы можем подумать об использовании следующих структур данных для хранения информации о разных телефонных номерах.

1. Массив телефонных номеров и записей.
2. Связанный список телефонных номеров и записей.
3. Сбалансированное бинарное дерево поиска с телефонными номерами в качестве ключей.
4. Таблица прямого доступа.

Для массивов и связанных списков нам нужно искать линейным способом, который на практике может быть дорогостоящим. Если мы используем массивы и храним данные отсортированными, то номер телефона можно найти за время O(Logn) с помощью двоичного поиска, но операции вставки и удаления становятся дорогостоящими, поскольку мы должны поддерживать порядок сортировки.

Со сбалансированным бинарным деревом поиска мы получаем умеренное время поиска, вставки и удаления. Все эти операции могут быть гарантированно выполнены за время O(Logn).

Другое решение, которое можно придумать, — это использовать таблицу прямого доступа , в которой мы создаем большой массив и используем телефонные номера в качестве индекса в массиве. Запись в массиве равна NIL, если номер телефона отсутствует, иначе в записи массива хранится указатель на записи, соответствующие номеру телефона. С точки зрения временной сложности это решение является лучшим среди всех, мы можем выполнять все операции за время O (1). Например, чтобы вставить номер телефона, мы создаем запись с подробностями данного номера телефона, используем номер телефона в качестве индекса и сохраняем указатель на созданную запись в таблице.
Это решение имеет много практических ограничений. Первая проблема с этим решением заключается в том, что требуется огромное дополнительное пространство. Например, если номер телефона состоит из n цифр, нам нужно O (m * 10 ⁿ ) места для таблицы, где m — размер указателя для записи. Другая проблема заключается в том, что целое число в языке программирования не может хранить n цифр.

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

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

Зачем использовать хеширование?

Если вы внимательно наблюдаете, в сбалансированном двоичном дереве поиска, если мы попытаемся выполнить поиск, вставить или удалить любой элемент, тогда временная сложность для того же будет O (logn). Теперь может возникнуть ситуация, когда наши приложения хотят выполнять те же операции быстрее, то есть более оптимизированным способом, и здесь в игру вступает хеширование. При хэшировании все вышеперечисленные операции могут быть выполнены за O(1), т.е. за постоянное время. Важно понимать, что в худшем случае временная сложность хеширования остается O(n), но в среднем временная сложность составляет O(1).
Теперь давайте разберемся с несколькими основными операциями хеширования.

Основные операции:

• HashTable: эта операция используется для создания новой хеш-таблицы.
• Удалить: эта операция используется для удаления определенной пары ключ-значение из хеш-таблицы.
• Получить: эта операция используется для поиска ключа внутри хеш-таблицы и возврата значения, связанного с этим ключом.
• Поместить: эта операция используется для вставки новой пары ключ-значение в хеш-таблицу.
• DeleteHashTable: эта операция используется для удаления хеш-таблицы.

Компоненты хеширования:

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

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

Хорошая хэш-функция должна обладать следующими свойствами:

1. Эффективно вычислим.
2. Следует равномерно распределить ключи (каждая позиция таблицы равновероятна для каждого).
3. Должен свести к минимуму коллизии.
4. Должен иметь низкий коэффициент загрузки (количество элементов в таблице, деленное на размер таблицы).

Например, для телефонных номеров плохая хеш-функция должна принимать первые три цифры. Лучшей функцией является рассмотрение последних трех цифр. Обратите внимание, что это может быть не лучшая хэш-функция. Могут быть лучшие способы.

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

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

Следующие сообщения:
Отдельная цепочка для обработки столкновений
Открытая адресация для обработки конфликтов