Анализ структур данных. Часть 2: Очередь, стек и хеш-таблица
Страница 8. Уровень заполнения и расширение хеш-таблицы

Уровень заполнения и расширение хеш-таблицы

Класс Hashtable содержит закрытую (private) переменную loadFactor (уровень заполнения), в которой задается максимальное соотношение числа элементов, которые могут храниться в хеш-таблице к общему числу ее ячеек (slots). Например, если loadFactor равен 0,5, то это означает, что не более чем половина ячеек хеш-таблицы может быть заполнена данными. Оставшиеся половина ячеек при этом будут пустыми.

В одной из перегруженных форм конструктора хеш-таблицы вы можете задавать значение loadFactor от 0.1 до 1.0. При этом, однако, независимо от того, какое значение этой переменной вы зададите, оно будет автоматически уменьшено до 72 процентов, так что даже если вы зададите это значение равным 1,0, то на самом деле уровень заполнения хеш-таблицы все равно будет равен 0,72. В Microsoft опытным путем установили, что 0,72 является оптимальным уровнем заполнения хеш-таблицы, так что рекомендуется использовать значение уровня заполнения по умолчанию, равное 1.0 (которое при этом автоматически устанавливается в 0,72 - да, это звучит запутанно, но что поделать).

Примечание Я потратил несколько дней, задавая вопросы в различных форумах и ребятам из Microsoft почему применяется такое автоматическое преобразование уровня заполнения. Мне было интересно, почему они решили не делать диапазон допустимых значений уровня заполнения от 0.072 до 0.72. В конце концов я добрался до той команды в Microsoft, которая работала над реализацией класса Hashtable и они поделились со мной причинами такого решения. А именно, в процессе тестирования они обнаружили, что при уровне заполнения больше 0.72 производительность резко падала. Они решили, что разработчику, который будет использовать класс Hashtable лучше не забивать себе голову таким странным числом как 0.72, вместо этого ему достаточно помнить, что уровень заполнения 1.0 дает наилучший результат. Таким образом, такое решение, немного жертвует функциональностью, зато делает структуру данных более простой в использовании и принесет меньше головных болей сообществу разработчиков.

Каждый раз при добавлении элемента в хеш-таблицу происходит проверка, не превосходит ли уровень заполнения заданного значения. Если данный факт имеет место, то хеш-таблица расширяется (is expanded). Расширение происходит в два этапа:

1. Число ячеек хеш-таблицы приблизительно удваивается. Более точно, число ячеек увеличивается с текущего простого числа до следующего простого числа, хранящегося во внутренней таблице is (вспомним, что для надлежащей работы процесса повторного хеширования необходимо, чтобы размер хеш-таблицыбыл простым числом)
   
2. Поскольку в случае повторного хеширования значение хеш-функций зависит от размера хеш-таблицы, все значения хеш-функций для элементов данных хеш-таблицы вычисляются заново (поскольку размер хеш-таблицы был изменен на первом этапе).

К счастью, класс Hashtable скрывает от разработчика всю сложность метода Add(), так что в реальности вам не придется беспокоиться обо всех этих деталях.

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

Как уже говорилось, в Microsoft настроили хеш-таблицу на использование по умолчанию уровня заполнения 0,72. Следовательно, в среднем при возникновении коллизии будет осуществляться 3.5 пробы. Поскольку эта оценка не зависит от числа ячеек хеш-таблицы, то асимптотическое время доступа хеш-таблицы равно O(1), что конечно же лучше, чем O(n) - время поиска в неотсортированном массиве.

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