Энциклопедия Turbo Pascal. Главы 1-4
Страница 38. Анализ хеширования

Анализ хеширования

     При хешировании  в лучшем случае (который встречается доста-
точно редко) каждый полученный хеш-функцией физический индекс яв-
ляется  уникальным и время доступа приближается к времени прямого
индексирования.  Это значит,  что цепочка индексов хеширования не
создается  и  все операции поиска по существу являются операциями
прямого поиска. Однако, это случается редко, поскольку требуется,
чтобы  логический  индекс равномерно распределялся в пространстве
логических индексов.  В худшем случае (который также редок) схема
хеширования  вырождается  в схему поиска в связанном списке.  Это
будет в том случае,  когда все полученные с  помощью  хеш-функции
значения логических индексов будут равны. В среднем случае, кото-
рый на практике встречается чаще всего, время поиска любого конк-
ретного  элемента  посредством  хеширования соответствует времени
прямого индексирования, поделенного на некоторую константу, кото-
рая  пропорциональна  средней длине цепочки индексов хеширования.
Самым существенным при использовании метода хеширования для  реа-
лизации  разряженной  матрицы  является обеспечение равномерности
распределения физических индексов, чтобы не возникало длинных це-
почек.  Кроме того, метод хеширования очень хорошо использовать в
тех случаях,  когда известно какое максимальное  число  элементов
действительно потребуется.