Хеши: в поисках правды

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

На практике это Θ(1), то есть, в среднем и сбалансированном анализе это константа. В худшем случае это O(N).

Однако же, быстрая сортировка, применяемая в хвост и в гриву в библиотечных функциях (например, в bash-функции sort, в Array#sort в Руби, тысячи их), имеет сходные характеристики - несмотря на то, что он в большинстве случаев O(N*log(N)), в худших случаях он O(n^2), что ставит его на одну доску с пузырьком и делает асимптотически хуже той же сортировки слиянием. Но ведь в большинстве случаев используется именно он! А дело в том, что худшие случаи редки, а в сбалансированном случае он не только имеет хорошую алгоритмическую сложность, но и правильно расходует память и имеет чрезвычайно низкий коэффициент при этой самой "тэте".

Теперь посмотрим на хэш-таблицы. Мы привыкли думать о операции вставки в хэш-таблицу как O(1), но это не так, поскольку на каком-то этапе нужно перевыделить память и в ходе этого выполняется rehash. Именно поэтому в приложениях, в требованиях к которым числится гарантированное время отклика, использование хэш-таблиц как структур хранения данных противопоказанно, или хотя бы требует осторожности, поскольку на очередной вставке всё может тупо подлагнуть и довольно сильно.

Однако же, давайте представим, что у нас не приложение, а вычислительный скрипт. Нам не важно время одной операции. Давайте посмотрим, как часто выполняется rehash. Вот принятие решения, делать или не делать rehash: https://github.com/ruby/ruby/blob/trunk/st.c#L487. _Если среднее число записей в одной корзинке больше магического числа 5_. Новый же размер определяется ближайшими простыми числами к степеням двойки. То есть, при вставке N элементов, будет выполнено O(log(N)) операций rehash. А каждый rehash (например, i-тый по счёту rehash) будет выполнен не на N элементах, а на простом числе, ближайшем к 2^i. В итоге, имеем сумму геометрической прогрессии с шагом 2, заканчивающейся на N/2. То есть, асимптотически, N.

Итого на N операций вставки имеем (N*O(1) + O(N)) вычислительную сложность.

Теперь с чтением из хэша. Тут сложнее и здесь асимптотически действительно всё плохо, потому что именно здесь вступает в силу то самое вероятностное поведение. Если, к примеру, реализовать хэш-функцию, как return 666, будем иметь ярко выраженную O(N) сложность на произвольный доступ. К счастью, так хэш-функцию никто не реализует.

Руби 1.8, 1.9 и 2.0 используют так называемый Murmur hash (https://github.com/ruby/ruby/blob/trunk/st.c#L1252). Этот алгоритм проходит "пыточный тест Боба Дженкинса" и не даёт коллизий на 4-х байтных ключах даже худшем случае. 4-х байтные ключи - это целые числа до двух миллиардов по модулю. В целом же, для любой разумной практической реализации верен тот факт, что коллизий немного. Конечно же, даже очень большое поле возможных хэшей для не очень большого подмножества значений будет давать коллизию с весьма высокой вероятностью. Так называемый парадокс дней рождения. Но одна коллизия - это в среднем пять операций (помните магическое число). А 1000 коллизий в Murmur hash случится и вовсе с вероятностью в миллиард раз меньшей, чем вероятность попадения метеора в ваш офис, если вероятность одной будет составлять аж 95%.

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

Подвожу итог.

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