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

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 была намного больше, чем емкость таблицы.