Хеширане - Решаване на проблеми с алгоритми и структури от данни
В предишните раздели успяхме да усъвършенстваме алгоритмите си за търсене, като се възползвахме от информация за това къде се съхраняват елементите един спрямо друг. Например, знаейки, че списъкът е подреден, можем да търсим в логаритмично време, използвайки двоичен алгоритъм. В този раздел ще се опитаме да отидем още една стъпка по-нататък: да изградим структура от данни, която да може да се търси за \ (O (1) \) време. Тази концепция се нарича хеширане.
Сега трябва да знаем не само местоположението на елемента, когато го търсим в колекцията. Ако всеки елемент е там, където трябва да бъде, тогава търсенето може да използва сравнения само за откриване на присъствието на търсеното. По-нататък обаче ще видим, че това по правило не е единственият изход.
Хеш таблица - това е колекция от предмети, които се съхраняват, за да могат лесно да бъдат намерени по-късно. Всяка позиция в хеш таблицата (често се нарича слот) може да съдържа самия елемент и цяло число, започващо от нула. Например имаме слот 0, слот 1, слот 2 и т.н. Първоначално хеш таблицата не съдържа елементи, така че всеки е празен. Можем да направим реализация на хеш таблица, като използваме списък, в който всеки елемент се инициализира със специалната стойност на Python None. Фигура 4 показва хеш таблица с размер \ (m = 11 \). С други думи, има \ (m \) слотове, номерирани от 0 до 10.
Фигура 4: Хеш таблица с 11 празни слота
Извиква се връзката между елемент и слота, в който е поставен хеш функция. Той взема всеки елемент от колекцията и връща цяло число от диапазона на имената на слотове (0 до \ (m-1 \)). Да предположим, че имаме набор от цели числа 54, 26, 93, 17, 77 и 31. Нашата първа хеш функция, понякога наричана „метод на остатъка“, просто взема елемент и го разделя на размера на таблицата, връщайки остатъка като хеш стойности (\ (h (item) = item \% 11 \)). Таблица 4 показва всички хеш стойности на числата от нашия пример. Забележка: методът на остатъка (модулна аритметика) обикновено присъства под някаква форма във всички хеш функции, тъй като резултатът трябва да е в диапазона от имената на слотове.