Линейное хэширование и сравнительный анализ структур массив
Хеширование, которое родилось еще в середине прошлого века, активно используется в наши дни везде, где требуется произвести быструю выборку данных. Появились новые методы хеширования, новые модификации алгоритмов, написанных ранее. По мнению Дональда Кнута наиболее важным открытием в области хеширования со времен 70 годов, вероятно, является линейное хеширование Витольда Литвина. Линейное хеширование, которое не имеет ничего общего с классической технологией линейной адресации, позволяет многим хеш-адресам расти и/или выступать в поли вставляемых и удаляемых элементов. Линейное хеширование может также использоваться для огромных баз данных, распределенных между разными узлами в сети.
Разумеется, методы и сферы применения хеширования не ограничиваются тем, что представлено в этой работе. Не вдаваясь в строгий анализ эффективности, были рассмотрены только базовые, наиболее известные методы. Помимо них можно отметить полиномиальное хеширование (М. Ханан и др., 1963), упорядоченное хеширование (О. Амбль, 1973), линейное хеширование (В. Литвин, 1980).