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