На этом шаге рассмотрим коэффициент заполнения хеш-таблицы.
Коэффициент заполнения хеш-таблицы вычисляется по простой формуле.
Хеш-таблицы используют массив для хранения данных, поэтому для вычисления коэффициента заполнения можно подсчитать количество заполненных элементов в массиве. Например, в следующей хеш-таблице коэффициент заполнения равен 0,4.
По коэффициенту заполнения можно оценить количество пустых ячеек в хеш-таблице.
Предположим, в хеш-таблице нужно сохранить цены 100 товаров и хештаблица состоит из 100 элементов. В лучшем случае каждому товару будет выделен отдельный элемент.
Коэффициент заполнения этой хеш-таблицы равен 1. А если хеш-таблица состоит всего из 50 элементов? Тогда ее коэффициент заполнения будет равен 2. Выделить под каждый товар отдельный элемент ни при каких условиях не удастся, потому что элементов попросту не хватит! Коэффициент заполнения больше 1 означает, что количество товаров превышает количество элементов в массиве.
С ростом коэффициента заполнения в хеш-таблицу приходится добавлять новые элементы, то есть изменять ее размер. Представим, что эта хештаблица приближается к заполнению.
Хеш-таблицу необходимо расширить. Расширение начинается с создания нового массива большего размера. Обычно в таком случае создается массив вдвое большего размера.
Теперь все эти элементы необходимо заново вставить в новую хеш-таблицу функцией hash.
Новая таблица имеет коэффициент заполнения ⅜. С меньшим коэффициентом загрузки число коллизий уменьшается, и таблица начинает работать более эффективно. Хорошее приближенное правило: изменяйте размер хеш-таблицы, когда коэффициент заполнения превышает 0,7. Но ведь на изменение размеров уходит много времени! Да, изменение размеров требует значительных затрат ресурсов, поэтому оно не должно происходить слишком часто. В среднем хеш-таблицы работают за время O(1) даже с изменением размеров.
На следующем шаге начнем рассматривать поиск в ширину.
