Cтраница 4
Одно из преимуществ этого метода заключается в том, что связанные хеш-таблицы никогда не переполняются. [46]
Одной из проблем для методов хеширования является проблема выбора размера хеш-таблицы, так как изменение размера хотя и возможно, но очень трудоемко. Если взять размер таблицы исходя из расчета на максимальное число ключей, то эффективность использования памяти будет низкой, в противном случае рано или поздно наступит ее переполнение и потребуется увеличить размер таблицы. Кроме того, для методов хеширования характерна зависимость времени обработки от коэффициента заполнения таблицы: чем ниже коэффициент заполнения, тем меньше времени требуют поиск и вставка. Поэтому необходимость в увеличении размера таблицы возникает обычно из-за резкого увеличения времени обработки, а не физического переполнения таблицы. [47]
На этих диаграммах показано размещение записей при их вставке в хеш-таблицу с использованием линейного зондирования ( рисунок в центре) и двойного хеширования ( рисунок внизу), при распределении ключей, показанном на верхней диаграмме. [48]
Если элемент так и не найден, то его в хеш-таблице нет. [49]
После того как вы пометите как удаленные большое количество элементов, хеш-таблица может заполниться мусором и на поиск элементов будет уходить много времени. [50]
Реализация этого метода возможнатолвко в том случае, если элементы в хеш-таблице отсортированы так, чтобы программа исследовала их всегда в порядке возрастания. Существует достаточно простой способ добавления элементов, который гарантирует такое расположение. [51]
Маркировать элемент как удаленный быстрее и проще, чем удалять его из хеш-таблицы, но в конце концов таблица может заполниться пустыми ячейками. [52]
Наконец, положим Pk равным вероятности того, что при вставке в хеш-таблицу ( Л / 1) - го ключа понадобится ровно ( & 1) проб. [53]
Если можно заранее предусмотреть количество элементов, которые должны быть помещены в хеш-таблицу, и при наличии достаточно большой непрерывной области памяти, в которой можно хранить все ключи при некотором остающемся свободном объеме памяти, в хеш-таблице, вероятно, вообще не стоит использовать какие-либо связи. Существует несколько методов хранения TV элементов в таблице размером М N, при которых разрешение конфликтов основывается на наличии пустых мест в таблице. Такие методы называются методами хеширования с открытой адресацией. [54]