Методы сортировки и поиска

       

Методы хэширования для поиска в основной памяти


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

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

Содержание раздела