Итак, здесь нужно учитывать две вещи - hashing time complexity и collision resolution time complexity.
Как правило, время работы функций ha sh является постоянным или линейно зависит от размера клавиши ввода. Это означает, что constant время не означает, что оно не зависит от размера ключа, а только от того факта, что если операции выполняются с целыми числами, типичные компьютеры сегодня довольно быстры, и их можно рассматривать как константу.
Итак, если у вас есть более простая функция ha sh, такая как h(k) = k % m, где % - оператор по модулю, она будет выполняться быстрее, чем другие функции, скажем h(k) = ( (k << 16) ^ k ) % m, где ^ является побитовым оператором xor.
Именно вторая функция ha sh имеет на две операции больше целых, чем первая, хотя она все еще является константой. Если вы запускаете бенчмарк-тест на быстром языке, таком как C ++, и строите таблицу ha sh, выполняя более чем 1014 * вставок, разница будет порядка нескольких milliseconds. Точная разница будет зависеть от аппаратной среды. Тем не менее, разница точно не будет большой.
Более того, если вы спросите опытного программиста, какой из них он выберет, я уверен, что он будет вторым, потому что он менее подвержен к столкновениям. Обратите внимание, что любое изменение в последних 16 битах также приведет к изменению битов более высокого порядка. В большинстве случаев налогообложение, вызванное конфликтами производительности, намного больше, чем налогообложение, вызванное вычислением значений ha sh.
Кроме того, если вы просто выполняете операции вставки, то имеет смысл использовать цепочку для разрешения коллизий, поскольку это обеспечивает O(1) вставки даже во время коллизий, в отличие от методов зондирования. Обратите внимание, что это верно только для операций вставки в таблице ha sh. Следовательно, если ваш вопрос касается только построения таблицы ha sh, то go с более простой функцией ha sh с цепочкой. Столкновения все еще были бы там, но вставки будут O(1)
Более подробную информацию о таблицах ha sh и о том, как избежать высокой сложности времени выполнения для столкновений, можно найти здесь .