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