tableCapacity обычно следует хранить в соотношении sane к количеству ключей, которые будут хэшироваться в таблицу. Какое соотношение зависит от того, как будут обрабатываться коллизии хешей, а именно:
будут найдены альтернативные области ( "открытая адресация" или "закрытое хеширование" ): с хорошо хеш-функция на 20-50% больше блоков, чем ключей - это обычно нормальный диапазон
каждое ведро содержит некоторую цепочку элементов, которые там хэшируются ( "отдельная цепочка" ): с хэш-функцией good она не не имеет большого значения, так что у вас может быть вдвое меньше ведер, чем ключей, или вдвое больше, и все будет происходить без особой драмы
Тем не менее, когда хеш-функция не является хорошей, а хешируемые ключи не являются достаточно случайными, чтобы помочь хэш-функции работать адекватно, это помогает иметь tableCapacity, который уменьшает коллизии: попробуйте любое простое число вокруг значение, полученное из числа хешируемых ключей и соотношений, перечисленных выше. Например, если у вас есть 6 ключей и вы используете отдельную цепочку, то tableCapacity из 5, 7 или 11 будет нормальным.
Но ваш вопрос не говорит о том, как будут обрабатываться столкновения, поэтому мы оставим это с вами.
Давайте перейдем к рассмотрению самой логики хеширования:
h = (h * hashBase + ord(key[i])) % tableCapacity
Это похоже на упрощенную / скомпрометированную форму "MAD" хеш-подхода, описанного в этом вопросе - в моем ответе есть объяснение, которое в дальнейшем я буду считать, что вы ' читаем.
Если мы сопоставим вашу функцию с обычной формой MAD, мы увидим, что вы используете % tableCapacity для каждого среза (байта?) Ключа. Причина, которая может иметь смысл в python, состоит в том, что в python нет целых чисел с фиксированным числом битов, которые переполняются, как многие языки нижнего уровня (и сам процессор), поэтому, если у вас нет операции % внутри цикла значение h может вырасти до размера, аналогичного всему ключу - если вы генерируете хеш видеофайла в виде дешевой контрольной суммы, это будет очень медленным и бесполезным расходом памяти. Таким образом, использование % для ограничения размера h после каждой итерации является нормальным, но по причинам, объясненным в другом ответе, особенно важно, чтобы tableCapacity было простым, и hashBase должен быть выбран, чтобы обычно производить значения, намного превышающие tableCapacity, чтобы минимизировать количество, на которое более ранние хэш-блоки используются более интенсивно, чем более поздние (см. пример 200/255 в моем другом ответе, связанном выше).
Вкратце: выберите большое псевдослучайное hashBase - скажем, 32- или даже 64-битное случайное число и простое tableCapacity в нормальном соотношении к количеству ключей, учитывая, что вы открываете / закрываете хеширование ' мы выбрали.
Почему выбор hashBase = 1 увеличивает временную сложность операций хеш-таблицы?
hashBase не должно быть небольшим - это означает, что вклад key[i] вряд ли обернет h вокруг стола много раз, прежде чем операция % будет применена снова, теряя все преимущества от этого разбрасывая карту вокруг.
Почему лучше выбрать большой стол? Емкость?
Что ж, большие таблицы означают больше сегментов - при одинаковом количестве клавиш будет меньше столкновений, но при достойном хешировании вам не нужно выходить за борт. Чем больше сегментов, тем больше используется памяти и меньше попаданий в кэш, что замедляет работу.
Кроме того, почему то есть. hashBase = 250726 и емкость таблицы = 250727 приводят к замедлению работы?
Как объяснено выше, вы хотите, чтобы hashBase была намного больше, чем емкость таблицы.