Привет!!
Я уверен, что вы видели различные методы поиска, а именно. последовательный поиск, бинарный поиск, где время поиска зависит от количества элементов и задействовано множество ключевых сравнений.
Вы хотите что-то, что может сделать это за вас за постоянное время и с меньшим количеством ключевых сравнений?
Звучит хорошо!
Давайте тогда углубимся в это,
Предположим, нам нужно хранить данные о 'n'учащихся класса, учитывая их номер списка в качестве ключа,и ихименав качестве значения . Мы можем взять массив размера «n» и хранить имена студентов, соответствующие их номеру списка. Поскольку мы однозначно сопоставили каждое имя с номером рулона, мы можем напрямую получить доступ к этим данным, таким образом, мы можем получить любые данные за постоянное время и без ключевых сравнений. Этот метод адресации известен как Прямая адресация. Этот тип адресации полезен только для небольших данных и когда количество возможных значений ключа равно количеству сохраняемых ключей.
Для хранения больших объемов данных и одновременной экономии времени и места мы меняем наш подход к адресации, используя хеширование.
Процесс генерации адресов из значения ключа известен как Хеширование, а массив, в котором поиск и вставка выполняются посредством хеширования, называется Хэш-таблица.
Создание адресов из значения ключа.
Хэш-функция — это обычно математическая функция, которая используется для сопоставления значений ключа и их адресов . Хеш-функция принимает ключ в качестве входных данных и возвращает хеш-значение этого ключа, которое используется в качестве адреса для хранения ключа в массиве. Ключ может быть любого типа, например, целые числа, строки и т. д., но хэш всегда будет целым числом.
Ключ — — — →Хеш-функция — — → Адрес
Мы можем записать это как-
h(k) = a
h - хэш-функция
k -key
a- Адрес
Столкновение:
Коллизия возникает, когда хеш-функция генерирует один и тот же адрес для разных ключей. Ключи, сопоставленные с одним и тем же адресом, называются синонимами.
В идеале хеш-функция должна давать уникальный адрес всем ключам, но это не так. практически возможно. Итак, мы должны попытаться выбрать хеш-функцию, которая минимизирует коллизии.
При создании алгоритмов, использующих хеширование, мы должны в основном сосредоточиться на двух вещах: -
1. Выбор хеш-функции, преобразующей ключи в адреса.
2. Разрешение конфликтов.
Хэш-функция:
Как мы знаем, хэш-функция работает как интерфейс сопоставления между ключами и хеш-таблицей. Если у нас есть хеш-таблица размером n, то нам нужна хэш-функция, которая будет генерировать адреса в диапазоне от 0 до n-1. По сути, мы можем выбрать хеш-функцию, которая:
1. легко вычисляется.
2. генерирует адрес с минимальным коллизией.
(a) Усечение (или извлечение):
Это самый простой метод вычисления адреса из ключа, здесь мы выбираем только часть ключа в качестве адреса, либо крайние правые, либо крайние левые цифры. Этот метод является самым простым, но вероятность коллизии больше.
Например, пусть у нас есть 5-значные ключи, 54678, 87976, 98765, 32662 и размер таблицы 100, и мы решаем возьмите 2 крайние правые цифры в качестве адреса в хеш-таблице, поэтому адреса будут 78, 76, 65, 62 соответственно.
(b) Метод среднего квадрата:
В этом методе ключ возводится в квадрат, и в качестве адреса берется некоторое среднее значение. Сколько цифр выбрать в качестве адреса, зависит от размера таблицы. Если значение ключа очень велико для возведения в квадрат, мы можем взять часть ключа и применить метод среднего квадрата.
Например, скажем, у нас есть ключи = 1337, 1273, 1391, 1026 и при возведении в квадрат получаем, 1787569, 1620529, 1934881, 1052676 соответственно. и у нас есть размер таблицы 1000, поэтому мы можем взять адрес максимум из трех цифр, поэтому адреса будут 1787569, 1620529, 1934881, 1052676, т. е. 875, 205, 348 и 526 являются соответствующими адресами.
(c) Метод складывания:
Shift Folding: в этом методе ключ разбивается на разные части, где длина каждой части такая же, как у требуемого адреса, за исключением, возможно, последней части. После этого сломанные части сдвигаются и располагаются таким образом, что наименее значащие числа выстраиваются в строку, а затем добавляются все.
например- key = 738239456527 и размер хеш-таблицы 1000, поэтому разбивая на группу из трех, 738, 239, 456, 527 и добавляя их все -
738 + 239 + 456 + 527 = 1960, теперь игнорируя последний перенос, хэш-адрес становится = 960.
Складывание границ.В этом методе предполагается, что ключ написан на бумаге, а бумага сгибается на границах частей ключа, поэтому перед добавлением все четные части переворачиваются.
например- key = 738239456527 и размер хеш-таблицы 1000, поэтому складывается и разбивается на группу из трех, 738, 932, 456, 725 и теперь добавляется их все-
738 + 932+ 456 + 725= 2851, теперь игнорируя последний перенос, хэш-адрес становится = 851.
(d) Метод деления (модульное деление):
Здесь ключ делится на размер таблицы, а значение по модулю берется в качестве адреса.
H(k) = k mod m
Конфликт можно свести к минимуму, если размер таблицы взять за простое число.
Например, возьмем размер таблицы 100 и ключи 987, 765, 653, 234
987 % 100 = 87
765 % 100 = 65
653 % 100 = 53
234 % 100 = 34
87, 65, 53 , 34 — соответствующий хеш-адрес.
Спасибо!!!!.
