Хеширование в структуре данных: функции, методы [с примерами]

Опубликовано: 2021-05-02

Оглавление

Введение

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

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

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

Что такое хеширование в структуре данных?

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

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

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

Хеширование в структуре данных — это двухэтапный процесс.

  1. Хэш-функция преобразует элемент в небольшое целое число или хэш-значение. Это целое число используется в качестве индекса для хранения исходных данных.
  2. Он хранит данные в хеш-таблице. Вы можете использовать хеш-ключ для быстрого поиска данных.

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

Ниже приведены реальные примеры хеширования в структуре данных :

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

Оформление заказа: сортировка в структуре данных

Хэш-функция

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

hash = hashfunc(ключ)

индекс = хеш% размер_массива

Функция has должна удовлетворять следующим требованиям:

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

Хеш-таблица

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

Как работает хеширование в структуре данных?

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

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

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

Значения: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

Хэш-таблица будет выглядеть следующим образом:

Серийный номер Ключ Хэш Индекс массива
1 3 3%30 = 3 3
2 1 1%30 = 1 1
3 40 40%30 = 10 10
4 5 5%30 = 5 5
5 11 11%30 = 11 11
6 15 15%30 = 15 15
7 18 18%30 = 18 18
8 16 16%30 = 16 16
9 38 38%30 = 8 8

Читайте также: Типы структур данных в Python

Методы разрешения столкновений

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

Линейное зондирование

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

Пример линейного измерения

Представьте, что вас попросили сохранить некоторые элементы в хэш-таблице размером 30. Элементы уже отсортированы в формате пары ключ-значение. Приведены следующие значения: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

Хэш(n) — это индекс, вычисленный с помощью хеш-функции, а T — размер таблицы. Если индекс слота = (hash(n) % T) заполнен, то мы ищем следующий индекс слота, добавляя 1 ((hash(n) + 1) % T). Если (хэш(n) + 1) % T также заполнен, то мы пробуем (хеш(n) + 2) % T. Если (хэш(n) + 2) % T также заполнен, то мы пробуем (хеш( п) + 3) % Т.

Хэш-таблица будет выглядеть следующим образом:

Серийный номер Ключ Хэш Индекс массива Индекс массива после линейного зондирования
1 3 3%30 = 3 3 3
2 1 1%30 = 1 1 1
3 63 63%30 = 3 3 4
4 5 5%30 = 5 5 5
5 11 11%30 = 11 11 11
6 15 15%30 = 15 15 15
7 18 18%30 = 18 18 18
8 16 16%30 = 16 16 16
9 46 46%30 = 8 16 17

Двойное хеширование

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

Формула метода двойного хэширования выглядит следующим образом:

(firstHash(ключ) + i * secondHash(ключ)) % sizeOfTable

Где я - значение смещения. Это значение смещения увеличивается до тех пор, пока не будет найден пустой слот.

Например, у вас есть две хеш-функции: h1 и h2. Чтобы найти свободный слот, необходимо выполнить следующие шаги:

  1. Убедитесь, что hash1(key) пуст. Если да, то сохраните значение в этом слоте.
  2. Если хэш1(ключ) не пуст, то найти другой слот, используя хеш2(ключ).
  3. Убедитесь, что хэш1 (ключ) + хеш2 (ключ) пуст. Если да, то сохраните значение в этом слоте.
  4. Продолжайте увеличивать счетчик и повторяйте с hash1(ключ)+2hash2(ключ), hash1(ключ)+3hash2(ключ) и так далее, пока не будет найден пустой слот.

Пример двойного хеширования

Представьте, что вам нужно хранить некоторые элементы в хеш-таблице размером 20. Даны следующие значения: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) по модулю 20

н h(n,i) = (h'(n) + i 2 ) %20
16 I = 0, h(n,0) = 16
8 I = 0, h(n,0) = 8
63 I = 0, h(n,0) = 3
9 I = 0, h(n,0) = 9
27 I = 0, h(n,0) = 7
37 I = 0, h(n,0) = 17
48 I = 0, h(n,0) = 8

I = 0, h(n,1) = 9

I = 0, h(n,2) = 12

5 I = 0, h(n,0) = 5
69 I = 0, h(n,0) = 9

I = 0, h(n,1) = 10

34 I = 0, h(n,0) = 14
1 I = 0, ч (n, 0) = 1
Изучайте онлайн -курсы по разработке программного обеспечения в лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

Заключение

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

Вы можете попробовать этот пример, чтобы укрепить свои знания о структуре данных. Если вам интересно узнать больше о структуре данных , ознакомьтесь с программой upGrad Executive PG в курсе Full Stack Development. Этот курс предназначен для работающих профессионалов и предлагает тщательное обучение и трудоустройство в ведущих компаниях.

Что такое хеш-таблица?

Хеш-таблица — это реализация ассоциативного массива, структуры, используемой в компьютерном программировании для реализации абстрактного типа данных (ADT). В абстрактном типе данных программисту не нужно знать о деталях реализации типа данных (например, о том, как данные хранятся в памяти), а только об операциях, которые могут быть выполнены с этим типом данных. Хеш-таблица использует хеш-функцию для вычисления индекса в массиве сегментов или слотов, из которого можно найти желаемое значение. Хеш-таблицы используются для реализации карт, подобных структурам данных. Хеш-таблицы очень часто используются в современных компьютерах для реализации таких вещей, как словари (как в python), ассоциативные массивы (как в php), хэш-таблицы Java и т. д. Хеш-таблицы обычно реализуются в языках как массив значений, отсортированных по их ключам. . Это делает операции поиска и вставки/удаления очень быстрыми, поскольку данные систематически хранятся в памяти.

Каковы приложения хеш-функций?

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

Каковы методы разрешения коллизий при хешировании?

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