Рубрики

Хеширование | Комплект 1 (Введение)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки:
MIT Video Lecture

IITD Видео Лекция

«Введение в алгоритмы», второе издание Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л. Ривеста и Клиффорда Стейна .

http://www.cs.princeton.edu/~rs/AlgsDS07/10Hashing.pdf

http://www.martinbroadhurst.com/articles/hash-table.html

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

Рекомендуемые посты:

Хеширование | Комплект 1 (Введение)

0.00 (0%) 0 votes