Хеширование - «Современная техника» | Хеш-функция | Хеш-таблица | Столкновение

Представляем хеш-таблицу

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

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

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

Хеш-таблица

~ Рейвендерлих

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

hashTable["firstName"] = "Steve"

	The hashTable array:
	+--------------+
	| 0:           |
	+--------------+
	| 1:           |
	+--------------+
	| 2:           |
	+--------------+
	| 3: firstName |---> Steve
	+--------------+
	| 4:           |
	+--------------+

В этом примере ключ "firstName" отображается на индекс массива 3. Добавление значения под другим ключом помещает его в другой индекс массива:

hashTable["hobbies"] = "Programming Swift"

	The hashTable array:
	+--------------+
	| 0:           |
	+--------------+
	| 1: hobbies   |---> Programming Swift
	+--------------+
	| 2:           |
	+--------------+
	| 3: firstName |---> Steve
	+--------------+
	| 4:           |
	+--------------+

Другой пример

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

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

Теперь мы можем изменить хеш-функцию, чтобы она занимала мало места.

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

Столкновение

Поскольку может случиться так, что двум или более ключам будет назначен один и тот же индекс массива. Это называется столкновением.

Чтобы избежать этого столкновения, мы можем увеличить размер массива или каким-то образом нам нужно справиться с этим столкновением.

Другой простой и распространенный способ справиться с этим может выглядеть так:

Райверндерлих

buckets:
	+-----+
	|  0  |
	+-----+     +----------------------------+
	|  1  |---> | hobbies: Programming Swift |
	+-----+     +----------------------------+
	|  2  |
	+-----+     +------------------+     +----------------+
	|  3  |---> | firstName: Steve |---> | lastName: Jobs |
	+-----+     +------------------+     +----------------+
	|  4  |
	+-----+

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

В основном столкновения можно избежать следующими способами:

Открытое хеширование:

  • Цепочка

Закрыть хеширование:

  • Лайнер зонд
  • Квадратичное зондирование
  • Двойное хеширование

Коэффициент нагрузки

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

Хеш-функция

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

Теперь давайте поговорим о некоторых методах выбора правильной функции для вашей таблицы.

  1. Мы можем выбрать функцию равномерного распределения или, скажем, функцию, основанную на соотношении один к одному. ч (х) = х
  2. Один из лучших способов - взять модуль 101 или 10 или что-то в этом роде. ч (х) = х% 101. Хорошая рекомендация - использовать основной номер.

Куда пойти отсюда

Мой LinkedIn: linkedin.com/in/my-pro-file

Темы, которые могут вас заинтересовать: