Проблемы распределения

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

Поэтому нам выгодно выбрать такую хэш-функцию, которая равномерно распределяет записи по сегментам. Можно улучшить рассмотренную систему, изменив количество сегментов. Чтобы понять почему, вспомните, что если у делимого и делителя есть общий множитель, этот множитель будет и множителем остатка. Предположим, что мы создали хэш-систему из 40 сегментов, и все ключи делятся на 5. Так как 40 также делится на 5, число 5 будет присутствовать в остатках, полученных в процессе деления, и записи распределятся по сегментам, соответствующим остаткам 0, 5, 10, 15, 20, 25, 30 и 35. Аналогично с ключами, которые делятся на 2, 4, 8, 10 и 20, так как эти числа также являются множителями 40. Такая ситуация приводит к частному решению выбрать количество сегментов, являющееся простым числом, минимизируя возможность появления общих множителей. Например, можно существенно снизить вероятность кластеризации (неравномерного распределения) в примере с записями сотрудников, используя 41 сегмент вместо 40.

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

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

Такой анализ позволяет нам подсчитать вероятность того, что первые восемь записей попадут в пустые сегменты — она равна произведению вероятности для каждой записи попасть в пустой сегмент, предполагая, что предыдущие записи размещены именно в пустых сегментах. Таким образом, вероятность равна (41/41)х(40/41)х(39/41)х(38/41)х... х(34/41) = 0.482

Мы видим, что вероятность меньше половины. Таким образом, вероятность того, что по меньшей мере две из первых восьми записей попадут в один сегмент, больше, чем вероятность того, что они попадут в разные сегменты. То есть коллизия, скорее всего, произойдет даже при хранении только восьми записей в системе хэширования с 41 сегментом.