Криптиране ли е хеширането?

    В най-общият смисъл на думата "криптиране", се предполага, че ако се разполага с нужните ключове, обратната операция е възможно, тоест от криптираното съобщение, използвайки ключа, можем да получим изходното съобщение.
    В случая със хеш функциите, това въобще не е така.
    Някои използват термина "еднопосочно криптиране", който според мене също не е особенно точен, тък като в думата "криптиране" винаги се подразбира двупосочност и използването и с думата "еднопосочно" крие логическо противоречие.
    Според мене, най-точното описание на хеширането е "еднопосочно преобразование" или "необратимо преобразование".

Уникални ли са хеш стойностите?

    Не се заблуждавайте. Хеш стойностите не са уникални за даден входен стринг!
    В зависимост от дължината на хеш стойността и алгоритъма на хеширане има по-голяма или по-малка вероятност за т.н. хеш колизии - това е когато два различни стринга имат една и съща хеш стойност.
    При някои алгоритми тази вероятност е по-голяма при друга по-малка, но никога не е нула. Като пример ще дам елементарният (но все още използван тук-там) алгоритъм - хеш стойността се получава като се сумират един след друг всички символи на стринга. Очевидно е, че при произволна размяна на символите във стринга, ще се получи стринг, който има същият хеш.
    При по-сложните хеш функции, намирането на втори стринг със същата хеш функция не е тривиална задача, но това не значи, че хеш стойностите никога няма да съвпаднат. Самият факт, че хеш стойността е винаги по-малка от стринга гарантира съвпадения на хешовете за някои входни стойности.
    Правилото е такова - колкото дължината на хеша е по-голяма, толкова по-рядко стават колизии. Ако дължината на хеша е по-голяма от най-дългият стринг, може да се намери такава функция, която никога няма да дава колизии, но разбира се, използването не толкова дълги хеш стойности е допустимо само за много специфични задачи.


За какво се използва?

    Има няколко главни сфери на приложение на хеширането. Тъй като са доста различни, ще ги разгледаме поотделно:
   
1. Търсене на стрингове в големи масиви. Хеш таблици.
   
    Да предположим, че имаме някакъв голяма таблица (масив) със произволни, уникални стрингове и имаме нов стринг, който искаме да разберем има ли го в таблицата или не. Тривиалното решение е да сканираме масива елемент по елемент и да сравняваме нашият стринг със всеки стринг в таблицата.
    Това решение обаче е крайно неефективно. Наистина, сравняването на стрингове е много скъпа операция, която вътрешно се реализира със цикли, и сравняване символ по символ на двата стринга. От друга страна, сравняването на числа е евтина операция, която се реализира с 1, 2 инструкции на процесора.
    Как можем да заменим сравняването на стрингове със сравняване на числа?
    Да предположим, че когато запълваме масива, заедно със всеки стринг, изчисляваме и записваме и неговата хеш стойност.
    Тогава при търсенето, можем да изчислим хеша на търсеният стринг и да сканираме масива, сравнявайки не директно стринговете, а хеш стойностите им. Разбира се задължително трябва да предвидим колизиите - ако хешовете съвпадат, трябва да направим задължително сравнение директно между стринговете, за да сме сигурни че търсеният стринг е намерен - но тук имаме само едно сравнение, а не хиляди.
    Това решение веднага може да ни даде значително увеличаване на скоростта на търсенето. Но все пак остава сканиране на масива, макар и сравнявайки числа, а не стрингове.
    Скоростта на алгоритъма е O(n) - тоест времето нараства линейно с увеличаване на размера на масива.
    Можем ли да се отървем и от това сканиране и да направим скоростта да не зависи от размера на масива, а да бъде константа?
    Да, можем, и това всъщност е най-голямото предимство на хеширането.
    Да кажем, че имаме хеш функция, която дава като резултат еднобайтово число, тоест за всеки входен стринг се получава стойност 0..255
    Създаваме си масив със 256 елемента, които съдържат указатели към стрингове или 0 - това ще бъде нашата "хеш таблица", ще я обозначаваме със HashTable[0..255].
    При попълването на масива в който ще търсим, изчисляваме хеш стойността на всеки стринг и записваме в съответният елемент от хеш таблицата, указател към стринга:

CODE

1 2	h := Hash(NewString); HashTable[h] := ptr(NewString);

    След това, ако имаме стринг, който искаме да потърсим в таблицата, ще е достатъчно да изчислим хеш стойността му и да видим, дали на съответната позиция има 0 или указател. Това ще изглежда така:
   
CODE

1 2 3

h :=  Hash(SearchString); if HashTable[h] = 0 then "Стринга не е в масива"                else "Стринга е намерен."

    Никога не трябва да забравяме за колизиите! Това е особенно добре видно в горният пример. В най-добрият случай, ако искаме да добавим повече от 256 стринга, таблицата ще се препълни и поне 2 различни стринга ще имат еднакви хеш стойности.
    Обикновенно колизии настъпват значително по-рано. Основното правило е да не се допуска напълване на хеш таблицата повече от половината. Тоест, ако искаме да работим с максимум 1000 стринга,трябва да изберем хеш таблица с поне 2000 елемента.
    Това не значи, че в такава таблица няма да има колизии! Ще има. Просто, достатъчният размер на таблицата ще държи колизиите в допустими граници, които не се отразяват на скоростта на алгоритъма.