В този урок ще научите какво е хеширане.
Хеширането е техника за картографиране на голям набор от произволни данни в таблични индекси с помощта на хеш функция. Това е метод за представяне на речници за големи масиви от данни.
Тя позволява на заявки, актуализиране и извличане на операция, за да се случи в момент, постоянно т.е. O(1)
.
Защо е необходимо хеширане?
След съхраняване на голямо количество данни трябва да извършим различни операции с тези данни. Търсенията са неизбежни за наборите от данни. Линейното търсене и двоичното търсене извършват справки / търсене със сложност във времето O(n)
и O(log n)
съответно. Тъй като размерът на набора от данни се увеличава, тези сложности също стават значително високи, което не е приемливо.
Нуждаем се от техника, която не зависи от размера на данните. Разместване позволява заявки да се появят в постоянен време т.е. O(1)
.
Хеш функция
Хеш функция се използва за картографиране на всеки елемент от набор от данни към индекси в таблицата.
За повече информация относно хеш таблицата, техниките за разрешаване на сблъсъци и хеш функциите, моля, посетете Хеш таблица.