Как хеш-база и размер таблицы влияют на временную сложность хэша?

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

Вот код моей хеш-функции:

h = 0
for i in range(len(key)):
    h = (h * hashBase + ord(key[i])) % tableCapacity
return h

Почему выбор hashBase = 1 увеличивает временную сложность операций хеш-таблицы? Почему лучше выбрать большую емкость стола? Кроме того, почему ie. hashBase = 250726 и емкость таблицы = 250727 замедляют его работу?

Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения текстовых сообщений может быть настолько сложным или простым, насколько вы его сделаете. Как и в любом ML-проекте, вы можете выбрать...
7 лайфхаков для начинающих Python-программистов
7 лайфхаков для начинающих Python-программистов
В этой статье мы расскажем о хитростях и советах по Python, которые должны быть известны разработчику Python.
Установка Apache Cassandra на Mac OS
Установка Apache Cassandra на Mac OS
Это краткое руководство по установке Apache Cassandra.
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
В одном из недавних постов я рассказал о том, как я использую навыки количественных исследований, которые я совершенствую в рамках программы TPQ...
Создание персонального файлового хранилища
Создание персонального файлового хранилища
Вы когда-нибудь хотели поделиться с кем-то файлом, но он содержал конфиденциальную информацию? Многие думают, что электронная почта безопасна, но это...
Создание приборной панели для анализа данных на GCP - часть I
Создание приборной панели для анализа данных на GCP - часть I
Недавно я столкнулся с интересной бизнес-задачей - визуализацией сбоев в цепочке поставок лекарств, которую могут просматривать врачи и...
3
0
1 438
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

  1. будут найдены альтернативные сегменты ("открытая адресация", он же "закрытое хеширование"): с хеш-функцией хорошо на 20-50% больше сегментов, чем ключей, это в целом разумный диапазон

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

Тем не менее, когда хеш-функция не очень хороша, а хешируемые ключи недостаточно случайны, чтобы помочь хеш-функции работать адекватно, полезно иметь tableCapacity, который уменьшает коллизии: попробуйте любое простое число вокруг значения, полученного из количество хешируемых ключей и коэффициенты, перечисленные выше. Например, если у вас есть 6 ключей и вы используете отдельную цепочку, tableCapacity из 5, 7 или 11 будет разумным.

Но в вашем вопросе не говорится, как будут обрабатываться коллизии, поэтому мы оставим это вам.

Перейдем к рассмотрению самой логики хеширования:

h = (h * hashBase + ord(key[i])) % tableCapacity

Это похоже на упрощенную / скомпрометированную форму хеш-подхода «MAD», описанного в этот вопрос — в мой ответ есть объяснение, которое, как я предполагаю, вы прочитали.

Если мы сравним вашу функцию с общей формой MAD, мы увидим, что вы используете % tableCapacity для каждого фрагмента (байта?) ключа. Причина, которая может иметь смысл в python, заключается в том, что python не имеет целых чисел с фиксированным числом битов, которые переполняются, как многие низкоуровневые языки (и сам ЦП), поэтому, если у вас нет какой-либо % операции внутри loop значение h может вырасти до такого же размера, как и весь ключ - если вы генерируете хэш видеофайла в качестве дешевой контрольной суммы, это будет очень медленно и расточительно для памяти. Таким образом, использование % для ограничения того, насколько большим h может стать после каждой итерации, разумно, но по причинам, объясненным в другом ответе, особенно важно, чтобы tableCapacity было простым, и hashBase следует выбирать, чтобы обычно давать значения, намного большие, чем tableCapacity, чтобы минимизировать сумма, на которую более ранние сегменты хеширования используются более интенсивно, чем более поздние (см. пример 200/255 в моем другом ответе, указанном выше).

Подводя итог: выберите большое псевдослучайное hashBase — скажем, 32- или даже 64-битное случайное число и простое tableCapacity в разумном соотношении с вашим количеством ключей, учитывая выбранный вами дизайн открытого/закрытого хеширования.

Why does picking hashBase = 1 increase the time complexity of the hash table's operations?

hashBase не должен быть маленьким — это означает, что вклад key[i] вряд ли будет оборачивать h по таблице много раз, прежде чем операция % будет применена снова, теряя все преимущества от этого рассеяния отображения.

Why is it better to pick a large tableCapacity?

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

Also, why does ie. hashBase = 250726 and table capacity = 250727 cause its operations to slow down?

Как объяснялось выше, вы хотите, чтобы hashBase была намного больше, чем емкость таблицы.

Другие вопросы по теме