Введение в хэширование — учебные пособия по структуре данных и алгоритмам

Hashing refers to the process of generating a fixed-size output from an input of variable size using the mathematical formulas known as hash functions. This technique determines an index or location for the storage of an item in a data structure.

Содержание/Дорожная карта

Потребность в хэш-структуре данных

Каждый день данные в Интернете увеличиваются в несколько раз, и всегда сложно эффективно хранить эти данные. В повседневном программировании этот объем данных может быть не таким уж большим, но, тем не менее, его необходимо хранить, получать к нему доступ и обрабатывать легко и эффективно. Очень распространенной структурой данных, которая используется для такой цели, является структура данных Array.

Теперь возникает вопрос, если Array уже был, зачем нужна была новая структура данных! Ответ на это в слове « эффективность ». Хотя сохранение в массиве занимает O(1) времени, поиск в нем занимает не менее O(log n) времени. Это время кажется небольшим, но для большого набора данных оно может вызвать массу проблем, а это, в свою очередь, делает структуру данных Array неэффективной.

Итак, теперь мы ищем структуру данных, которая может хранить данные и выполнять поиск в них за постоянное время, то есть за время O(1). Вот как в игру вступила структура данных хеширования. С введением структуры данных Hash теперь можно легко хранить данные в постоянное время и извлекать их также в постоянное время.

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

Есть три основных компонента хеширования:

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

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

Предположим, у нас есть набор строк {"ab", "cd", "efg"}, и мы хотели бы сохранить его в таблице.

Нашей основной целью здесь является быстрый поиск или обновление значений, хранящихся в таблице, за время O(1), и нас не беспокоит порядок строк в таблице. Таким образом, данный набор строк может действовать как ключ, а сама строка будет действовать как значение строки, но как сохранить значение, соответствующее ключу?

• Шаг 1: Мы знаем, что хэш-функции (которые представляют собой некоторую математическую формулу) используются для вычисления хеш-значения, которое выступает в качестве индекса структуры данных, в которой будет храниться значение.
• Шаг 2: Итак, давайте назначим
  • «а» = 1,
  • «b»=2, .. и т. д. для всех букв алфавита.
• Шаг 3: Таким образом, числовое значение путем суммирования всех символов строки:

• “ab” = 1 + 2 = 3, 
• “cd” = 3 + 4 = 7 , 
• “efg” = 5 + 6 + 7 = 18  

• Шаг 4: Теперь предположим, что у нас есть таблица размера 7 для хранения этих строк. Используемая здесь хэш-функция представляет собой сумму символов в ключе mod Table size . Мы можем вычислить расположение строки в массиве, взяв сумму (строку) по модулю 7 .
• Шаг 5: Итак, мы сохраним
  • «аб» в 3 по модулю 7 = 3,
  • «cd» в 7 mod 7 = 0, и
  • «efg» в 18 mod 7 = 4.

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

Что такое хэш-функция?

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

Например: рассмотрите массив как карту, где ключ — это индекс, а значение — это значение по этому индексу. Таким образом, для массива A, если у нас есть индекс i , который будет рассматриваться как ключ, мы можем найти значение, просто взглянув на значение в A[i].
просто ища A[i].

Типы хеш-функций:

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

1. Метод деления.
2. Метод среднего квадрата.
3. Складной метод.
4. Метод умножения.

Свойства хорошей хеш-функции

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

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

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

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

Сложность вычисления хэш-значения с помощью хеш-функции

• Временная сложность: O(n)
• Сложность пространства: O(1)

Проблема с хешированием

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

Например: {"ab", "ba"} имеют одинаковое хеш-значение, а строка {"cd", "be"} также генерирует одинаковое хеш-значение и т. д. Это известно как коллизия и создает проблемы при поиске. , вставка, удаление и обновление значения.

Что такое столкновение?

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

Как обрабатывать столкновения?

В основном есть два метода обработки коллизий:

1. Отдельная цепочка:
2. Открытая адресация:

1) Раздельная цепочка

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

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

Hash function = key % 5, 
Elements = 12, 15, 22, 25 and 37.

Давайте посмотрим пошаговый подход к решению вышеуказанной проблемы:

• Шаг 1: Сначала нарисуйте пустую хеш-таблицу, которая будет иметь возможный диапазон хеш-значений от 0 до 4 в соответствии с предоставленной хеш-функцией.
  

• Шаг 2: Теперь вставьте все ключи в хеш-таблицу один за другим. Первым вставляемым ключом является 12, который сопоставляется с номером корзины 2, который вычисляется с помощью хеш-функции 12%5=2.

• Шаг 3: Следующий ключ — 15. Он будет отображаться в слоте номер 0, потому что 15% 5 = 0. Так вставьте его в ведро номер 5.

• Шаг 4: Теперь следующий ключ — 22. Он будет отображаться на корзину номер 2, потому что 22% 5 = 2. Но корзина 2 уже занята ключом 12. Таким образом, отдельный метод цепочки обработает это столкновение, создав связанный список для корзины 2.

• Шаг 5: Теперь следующий ключ — 25. Его номер корзины будет 25%5=0. Но корзина 0 уже занята ключом 25. Таким образом, метод отдельного связывания снова обработает коллизию, создав связанный список для корзины 0.

Таким образом, метод отдельной цепочки используется в качестве метода разрешения коллизий.

2) Открытая адресация

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

2.a) Линейное зондирование

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

Алгоритм:

1. Calculate the hash key. i.e. key = data % size
2. Check, if hashTable[key] is empty
   • store the value directly by hashTable[key] = data
3. If the hash index already has some value then
   1.  check for next index using key = (key+1) % size
4. Check, if the next index is available hashTable[key] then store the value. Otherwise try for next index.
5. Do the above process till we find the space.

Пример: давайте рассмотрим простую хеш-функцию как «модуль ключа 5» и последовательность ключей, которые нужно вставить: 50, 70, 76, 85, 93.

• Шаг 1: Сначала нарисуйте пустую хеш-таблицу, которая будет иметь возможный диапазон хеш-значений от 0 до 4 в соответствии с предоставленной хеш-функцией.

• Шаг 2: Теперь вставьте все ключи в хеш-таблицу один за другим. Первый ключ — 50. Он будет отображаться в слоте номер 0, потому что 50%5=0. Поэтому вставьте его в слот номер 0.

• Шаг 3: Следующий ключ — 70. Он будет сопоставлен со слотом номер 0, потому что 70% 5 = 0, но 50 уже находится в слоте номер 0, поэтому найдите следующий пустой слот и вставьте его.

• Шаг 4: Следующий ключ — 76. Он будет сопоставлен со слотом номер 1, потому что 76% 5 = 1, но 70 уже находится в слоте номер 1, поэтому найдите следующий пустой слот и вставьте его.

• Шаг 5: Следующий ключ — 93. Он будет отображаться в слоте номер 3, потому что 93% 5 = 3, поэтому вставьте его в слот номер 3.

2.b) Квадратичное зондирование

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

Пример последовательности с использованием квадратичного зондирования:

H + 1², H + 2², H + 3², H + 4²…………………. H + k²

Этот метод также известен как метод средних квадратов, потому что в этом методе мы ищем i ² -й зонд (слот) в i-й итерации и значение i = 0, 1, . . . n – 1. Мы всегда начинаем с исходного местоположения хеша. Если занята только локация, то проверяем остальные слоты.

Пусть hash(x) — индекс слота, вычисленный с помощью хеш-функции, а n — размер хеш-таблицы.

If the slot hash(x) % n is full, then we try (hash(x) + 1²) % n.
If (hash(x) + 1²) % n is also full, then we try (hash(x) + 2²) % n.
If (hash(x) + 2²) % n is also full, then we try (hash(x) + 3²) % n.
This process will be repeated for all the values of i until an empty slot is found

Пример: Предположим, что размер таблицы = 7, хэш-функция как Hash(x) = x % 7 и стратегия разрешения коллизий как f(i) = i ² . Вставка = 25, 33 и 105

• Шаг 1: Создайте таблицу размера 7.

• Шаг 2 – Вставьте 22 и 30
  • Хэш(25) = 22 % 7 = 1, поскольку ячейка с индексом 1 пуста, мы можем легко вставить 22 в слот 1.
  • Хэш(30) = 30 % 7 = 2, поскольку ячейка с индексом 2 пуста, мы можем легко вставить 30 в слот 2.

• Шаг 3: Вставка 50
  • Хэш(25) = 50 % 7 = 1
  • В нашей хеш-таблице слот 1 уже занят. Итак, будем искать слот 1+1 ² , т.е. 1+1 = 2,
  • Снова слот 2 оказывается занятым, поэтому мы будем искать ячейку 1+2 ² , т.е. 1+4 = 5,
  • Теперь ячейка 5 не занята, поэтому мы поместим 50 в слот 5.

2.c) Двойное хеширование

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

• Первая хэш-функция — это h1(k) , которая берет ключ и выдает местоположение в хеш-таблице. Но если новое место не занято и не пусто, мы можем легко разместить наш ключ.
• Но в случае, если ячейка занята (коллизия), мы будем использовать вторичную хеш-функцию h2(k) в сочетании с первой хеш-функцией h1(k) , чтобы найти новую ячейку в хеш-таблице.

Эта комбинация хеш-функций имеет вид

h(k, i) = h1(k) + i * h2(k)) % n 

куда

• i — неотрицательное целое число, указывающее номер столкновения,
• k = элемент/ключ, который хэшируется
• n = размер хеш-таблицы.

Сложность алгоритма двойного хеширования:

Time complexity: O(n)

Пример: Вставьте ключи 27, 43, 692, 72 в хеш-таблицу размера 7, где первая хэш-функция равна h1​(k) = k mod 7 , а вторая хеш-функция равна h2(k) = 1 + (k мод 5)

• Шаг 1: Вставьте 27
  • 27 % 7 = 6, ячейка 6 пуста, поэтому вставьте 27 в ячейку 6.

• Шаг 2: Вставьте 43
  • 43 % 7 = 1, ячейка 1 пуста, поэтому вставьте 43 в 1 ячейку.

• Шаг 3: Вставьте 692
  • 692 % 7 = 6, но позиция 6 уже занята и это коллизия
  • Поэтому нам нужно разрешить это столкновение с помощью двойного хеширования.

hnew = [h1(692) + i * (h2(692)] % 7
= [6 + 1 * (1 + 692 % 5)] % 7
= 9 % 7
= 2

Now, as 2 is an empty slot, 
so we can insert 692 into 2nd slot.

• Шаг 4: Вставьте 72
  • 72 % 7 = 2, но ячейка 2 уже занята, и это коллизия.
  • Поэтому нам нужно разрешить это столкновение с помощью двойного хеширования.

hnew = [h1(72) + i * (h2(72)] % 7
= [2 + 1 * (1 + 72 % 5)] % 7
= 5 % 7
= 5, 

Now, as 5 is an empty slot, 
so we can insert 72 into 5th slot.

Что подразумевается под коэффициентом нагрузки при хешировании?

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

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

Load Factor = Total elements in hash table/ Size of hash table 

Что такое перефразировать?

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

Применение структуры хеш-данных

• Хэш используется в базах данных для индексации.
• Хэш используется в дисковых структурах данных.
• В некоторых языках программирования, таких как Python, хэш JavaScript используется для реализации объектов.

Применение структуры хеш-данных в реальном времени

• Хэш используется для отображения кеша для быстрого доступа к данным.
• Хэш можно использовать для проверки пароля.
• Хэш используется в криптографии как дайджест сообщения.

Преимущества структуры хеш-данных

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

Недостатки структуры хеш-данных

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

Вывод

Из приведенного выше обсуждения мы делаем вывод, что цель хеширования — решить проблему быстрого поиска элемента в коллекции. Например, если у нас есть список из миллионов английских слов, и мы хотим найти определенный термин, мы будем использовать хеширование, чтобы найти и найти его более эффективно. Было бы неэффективно проверять каждый элемент в миллионах списков, пока мы не найдем совпадение. Хэширование сокращает время поиска, ограничивая поиск меньшим набором слов в начале.