Cтраница 4
На этих диаграммах показано размещение записей при их вставке в хеш-таблицу с использованием линейного зондирования ( рисунок в центре) и двойного хеширования ( рисунок внизу), при распределении ключей, показанном на верхней диаграмме. По мере заполнения таблицы записи объединяются в кластеры, разделенные пустыми позициями таблицы. Длинные кластеры нежелательны, поскольку средние затраты на поиски одного ключа в кластере пропорциональны длине кластера. При использовании линейного зондирования чем длиннее кластеры, тем более вероятно увеличение их длины, поэтому по мере заполнения таблицы несколько длинных кластеров оказываются доминирующими. При использовании двойного хеширования этот эффект значительно менее выражен и кластеры остаются сравнительно короткими. [46]
Сравнение линейного зондирования и двойного хеширования с раздельным связыванием выполнить сложнее, поскольку необходимо точно учитывать используемый объем памяти. Раздельное связывание использует дополнительный объем памяти для связей; методы с открытой адресацией используют дополнительную память неявно внутри таблицы для завершения последовательностей зондирования. Следующий конкретный пример иллюстрирует ситуацию. Предположим, что имеется таблица М списков, построенная при помощи раздельного связывания, что средняя длина списков равна 4, а каждый элемент и каждая связь занимают по одному машинному слову. Предположение, что элементы и ссылки занимают одинаковый объем памяти, оправдано во многих ситуациях, поскольку очень большие элементы будут заменены ссылками на них. В этом случае таблица занимает 9М слов в памяти ( 4Л / для элементов и 5М для связей), и для выполнения поиска в среднем требуется 2 зондирования. Но при линейном зондировании для 4Л / элементов в таблице размером 9 Л / требуется всего ( 1 1 / ( 1 - 4 / 9)) / 2 1.4 зондирований для обнаружения попадания при поиске - что на 30 процентов меньше, чем требуется для раздельного связывания при том же объеме используемой памяти; а при линейном зондировании для 4Л / элементов в таблице размером 6М требуется 2 зондирования для обнаружения попадания при поиске ( в среднем) и, следовательно, используется памяти на 33 процента меньше, чем при раздельном связывании при том же времени выполнения. [47]
Сравнение линейного зондирования и двойного хеширования с раздельным связыванием выполнить сложнее, поскольку необходимо точно учитывать используемый объем памяти. Раздельное связывание использует дополнительный объем памяти для связей; методы с открытой адресацией используют дополнительную память неявно внутри таблицы для завершения последовательностей зондирования. Следующий конкретный пример иллюстрирует ситуацию. Предположим, что имеется таблица М списков, построенная при помощи раздельного связывания, что средняя длина списков равна 4, а каждый элемент и каждая связь занимают по одному машинному слову. Предположение, что элементы и ссылки занимают одинаковый объем памяти, оправдано во многих ситуациях, поскольку очень большие элементы будут заменены ссылками на них. В этом случае таблица занимает 9М слов в памяти ( 4Л / для элементов и 5М для связей), и для выполнения поиска в среднем требуется 2 зондирования. Но при линейном зондировании для 4Л / элементов в таблице размером 9 Л / требуется всего ( 1 1 / ( 1 - 4 / 9)) / 2 1.4 зондирований для обнаружения попадания при поиске - что на 30 процентов меньше, чем требуется для раздельного связывания при том же объеме используемой памяти; а при линейном зондировании для 4Л / элементов в таблице размером 6М требуется 2 зондирования для обнаружения попадания при поиске ( в среднем) и, следовательно, используется памяти на 33 процента меньше, чем при раздельном связывании при том же времени выполнения. [48]