Още една магическа дума - "хеш".

Основната цел на статията е да изясни на начинаещите същността на нещата. Оттам нататък е много лесно да се намерят подробности и конкретни реализации, използвайки Google.

На английски: "hash, hashing".

Превежда се буквално като "кълцам" или "бъркотия". Понякога се използва: "message digest", което може да се преведе буквално като "смляно съобщение" или "извлечение от съобщение". Друг път ще го срещнете като "digital fingerprint" - буквално "цифров пръстов отпечатък".

Какво обаче означава това, отнесено към компютрите и информатиката?

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

1. Да е необратим - тоест да не съществува алгоритмичен начин за възстановяване на изходния стринг от хеш стойността. (Казвам "алгоритмичен", защото винаги съществува начина с "груба сила" - тоест, изброяваме всички възможни комбинации от входни данни и пробваме за всяка от тях, докато намерим решението.)

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

3. Хеш функцията трябва, по възможност, да се изпълнява бързо. Това не е абсолютно задължителност, но повече скорост никога не вреди

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

В случая със хеш функциите, това въобще не е така.

Някои използват термина "еднопосочно криптиране", който, според мен, също не е особенно точен, тъй като в думата "криптиране" винаги се подразбира двупосочност и използването й с думата "еднопосочно" крие логическо противоречие. 

Според мен, най-точното описание на хеширането е "еднопосочно преобразование" или "необратимо преобразование".

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

Не се заблуждавайте. Хеш стойностите не са уникални за даден входен стринг!

В зависимост от дължината на хеш стойността и алгоритъма на хеширане, има по-голяма или по-малка вероятност за т.н. хеш колизии - това е, когато два различни стринга имат една и съща хеш стойност.

При някои алгоритми тази вероятност е по-голяма, при друга - по-малка, но никога не е нула. Като пример ще дам елементарния (но, все още използван тук-там) алгоритъм - хеш стойността се получава като се сумират един след друг всички символи на стринга. Очевидно е, че при произволна размяна на символите в стринга, ще се получи стринг, който има същият хеш.

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

Правилото е такова - колкото дължината на хеша е по-голяма, толкова по-рядко стават колизии. Ако дължината на хеша е по-голяма от най-дългия стринг, може да се намери такава функция, която никога няма да дава колизии, но, разбира се, използването на толкова дълги хеш стойности е допустимо само за много специфични задачи.

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

1. Търсене на стрингове в големи масиви. Хеш таблици.

Това решение обаче е крайно неефективно. Наистина, сравняването на стрингове е много скъпа операция, която вътрешно се реализира с цикли и сравняване символ по символ на двата стринга. От друга страна, сравняването на числа е евтина операция, която се реализира с 1, 2 инструкции на процесора.

Как можем да заменим сравняването на стрингове със сравняване на числа?

Да предположим, че, когато запълваме масива, заедно с всеки стринг, изчисляваме и записваме и неговата хеш стойност.

Тогава при търсенето можем да изчислим хеша на търсения стринг и да сканираме масива, сравнявайки не директно стринговете, а хеш стойностите им. Разбира се, задължително трябва да предвидим колизиите - ако хешовете съвпадат, трябва да направим задължително сравнение директно между стринговете, за да сме сигурни, че търсеният стринг е намерен - но тук имаме само едно сравнение, а не хиляди.
Това решение веднага може да ни даде значително увеличаване на скоростта на търсенето. Но, все пак, остава сканиране на масива, макар и сравнявайки числа, а не стрингове.

Скоростта на алгоритъма е O(n) - тоест, времето нараства линейно с увеличаване на размера на масива.

Можем ли да се отървем и от това сканиране и да направим скоростта да не зависи от размера на масива, а да бъде константа?

Да, можем, и това всъщност е най-голямото предимство на хеширането.

Да кажем, че имаме хеш функция, която дава като резултат еднобайтово число, тоест, за всеки входен стринг се получава стойност 0..255
Създаваме си масив с 256 елемента, които съдържат указатели към стрингове или 0 - това ще бъде нашата "хеш таблица", ще я обозначаваме със HashTable[0..255].
При попълването на масива, в който ще търсим, изчисляваме хеш стойността на всеки стринг и записваме в съответния елемент от хеш таблицата указател към стринга:

Код:

---

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

---

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

Код:

---

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

---

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

Това не значи, че в такава таблица няма да има колизии! Ще има. Просто достатъчният размер на таблицата ще държи колизиите в допустими граници, които не се отразяват на скоростта на алгоритъма.

Справяне с колизиите.

Справянето с колизиите се състои от две части:
1. Намаляване на вероятността за възникване на колизии.
2. Справяне с колизиите, които все пак възникват.

За точка 1 - избираме по-голям хеш, избираме подходяща хеш функция, която дава по-малко колизии за типичните входни данни.

За точка 2 - има няколко начина да се справим с колизиите. Всички те имат предимства и недостатъци и, най-общо, трябва да се избира в зависимост от конкретната задача. Тук ще разгледаме няколко такива:

а. Затворено хеширане

Идеята е, че се използва само наличната хеш таблица, без да се отделя повече място в паметта за решаване на колизиите.
Това намалява използваната памет, но очевидно в такава таблица можем да добавим ограничен брой стрингове - точно колкото е размерът на таблицата.

Когато, при добавяне на стринг в хеш таблицата, се стигне до колизия (тоест, на мястото, където искаме да запишем стринга, има вече друг стринг със същия хеш), просто записваме новия стринг на следващото свободно място в таблицата.
При търсене алгоритъмът е същият: Ако на мястото в таблицата има записан стринг, но той не е този, който търсим, поглеждаме на следващия елемент. Ако и там не е нашият стринг - на следващия и така нататък, докато открием нашия стринг или 0 - което ще значи, че този стринг го няма в масива.
Забелязахте ли как при наличие на колизия този алгоритъм се превръща в обикновено сканиране? Това може драстично да свали скоростта на целия алгоритъм. Затова колизиите са толкова вредни и трябва да се вземат всички мерки за недопускането им.

б. Отворено хеширане

Идеята е, че, когато се получи колизия, на съответното място в таблицата записваме не указател към стринг, а указател към списък от стрингове, където записваме различните стрингове с еднакви хешове.
Това позволява да се записват неограничено количество стрингове в таблицата. Разбира се при търсене, ако срещнем колизия - тоест, указател към списък, този списък пак ще трябва да го сканираме елемент по елемент (или по някакъв друг начин - например с двоично търсене), за да установим има ли го нашия стринг, или не.

в. Двойно хеширане.

Идеята е - при попълване на таблицата, ако срещнем колизия, изчисляваме втора хеш стойност с друг алгоритъм и хешираме стринга във втора таблица. При търсене, ако стрингът, записан в първата таблица, не съвпада, изчисляваме втория хеш за търсения стринг и гледаме във втората таблица.
Разбира се, във втората таблица също ще са възможни колизии и те трябва да се решат с някакъв друг метод. Но такива колизии ще възникват значително по-рядко и затова ще влияят слабо на скоростта на алгоритъма.

г. Динамично изграждане на хеш таблицата

Като най-общо правило, (сигурно сте забелявали вече) винаги се стремим да използваме най-големия възможен размер на хеш таблиците, за да избегнем колизиите и деградирането на скоростта.

От друга страна, обаче, сме ограничени от размера на наличната памет, а и тъй като огромната хеш таблица е обикновено пълна с много нули и малко данни - чувството, че прахосваме памет, е особено силно.
Можем да опитаме малко по-нетривиално решение: Избираме голям размер на хеша (например 32 бита или 64 бита), но не създаваме хеш таблицата в паметта (че как бихме могли - за упражнение можете да пресметнете колко памет изисква 32-битова хеш таблица, ако всеки елемент е указател), а я изграждаме в процеса на добавяне на стрингове в нея, като в паметта записваме само частта от таблицата, която е запълнена в момента.

Как става това: Сканираме хеша на стринга бит по бит, като всеки бит служи за разклонение на съответното ниво на едно двоично дърво. На последния ред на дървото имаме указатели към стринговете. Възли в дървото прибавяме, само когато възникне нужда от тях, така че в паметта винаги имаме само частта на таблицата, която е запълнена с данни.

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

Алгоритми за хеширане

Изборът на "правилен" алгоритъм за хеширане е много отговорна задача, от която, до голяма степен, зависи ефективността на програмите.

Пример от практиката: Парсерът на FASM (flatassembler) използва хеш функция с дължина 32 бита за бързо търсене в списъка с етикети по време на компилацията. При първата реализация (до версия 1.51 - ако си спомням добре) се използваше директно търсене в списъка с етикети като се сравняваха хеш стойностите.

При компилиране на големи сорсове с много етикети, бързодействието бързо започваше да пада и, по същество, времето за компилация зависеше от квадрата на броя редове в програмата.

Когато тези ефекти се появиха (при появяването на достатъчно големи програми, написани на FASM), Томаш Гриштар (автора на FASM), смени алгоритъма за търсене с описания по-горе алгоритъм с двоично хеш дърво.
Това увеличи скоростта на парсера 4 до 5 пъти.
Следващата стъпка беше наистина впечатляваща: След замяна на предишната хеш функция в компилатора с нова (по алгоритъма FNV-1a), скоростта на парсера се увеличи 25 пъти на някои тестове.

От този момент работата на парсера стана толкова бърза, че при всички практически случаи съставлява малка част от цялото време на компилацията.
Можете да погледнете цялата дискусия, свързана с тази история, тук: Дискусия за промените във FASM 1.51 (en)

Ето и като пример сорса на алгоритъма FNV-1a, използван във FASM (flatassembler), а също и в проекта Fresh

Код:

---

;-------------------------------------------------
; function StrHash
;   Computes 32 bit hash value from the string.
;   The function is compatible with FASM hash
;   function if OrMask = 0.
; Algorithm: FNV-1a
;
; Arguments:
;   hString - handle/pointer of the string.
;   OrMask  - every byte from the string will be ORed
;             with this value (byte)
; Return:
;   eax - 32bit hash value.
;-------------------------------------------------
proc StrHash, hString, OrMask
begin
push    esi edi ebx ecx edx

stdcall StrPtr, [hString]
mov     esi, eax

xor     ebx, ebx
mov     eax,2166136261
xor     ecx, ecx
mov     edi, 16777619
.hashloop:
mov     cl, [esi+ebx]
jecxz   .endstring
inc     bl
or      cl, byte [OrMask]
xor     al,cl
mul     edi
jmp     .hashloop

.endstring:
mov     edx,eax
and     eax,0FFFFFFh
shr     edx,24
xor     eax,edx
shl     ebx,24
or      eax,ebx
pop     edx ecx ebx edi esi
return
endp

---

Кодът е без обяснения, защото всъщност алгоритмите за хеширане не могат да се обясняват. Просто се сканира стринга и с ASCII кода на всеки символ се правят някакви сложни аритметични или логически действия с цел да се направи изходното число да бъде по възможност зависимо от всички входни символи. Често се използват ротация и умножения на прости числа и т.н. Всеки алгоритъм си е сам за себе си.

2. Пароли, идентификация

Другата голяма област на приложение на хеш функциите е идентификацията на потребители и разпознаване на пароли. Тук се използва свойството на хеша, че е необратим. Тоест, няма алгоритмичен начин, чрез който по хеш стойността да определим началния стринг.

При използване на хеширането в тази област колизиите нямат значение, защото можем да използваме хешове с произволна дължина, дори и  по-голяма такава от тази на входния стринг. Тук не се гони бързодействие, а сигурност. А знаем, че, ако дължината на хеша е по-голяма от тази на входния стринг, е възможно да се намери такава функция, която да не дава колизии за целия диапазон на входните стрингове.

Как въобще става разпознаването на потребители по парола?

Най-простият начин е да пазим паролите в масив, заедно с имената на потребителите и директно да ги сравняваме с тези, които потребителят въвежда.

Този метод е безкрайно ненадежден, обаче. Всеки, който има достъп до файла с паролите, ще може да ги види и използва.
При предаване на тези пароли по интернет, нещата са още по-зле, защото може да ги прихване всеки.
Използването на криптиране на файловете с пароли също не е решение, защото всеки криптиращ алгоритъм може да се декриптира.

Всъщност, правилното решение е просто - не пазим въобще паролите на потребителите, а пазим само хеш стойността от тази
парола. При искане на достъп до някой ресурс, потребителят въвежда някаква дума, която се хешира, и така получената стойност се сравнява с базата данни за дадения потребител. Ако хеш стойностите съвпадат, потребителят се пуска.

Дори и някой да има достъп до базата данни, той няма да може да разбере какви са паролите на потребителите, защото хеш функцията не може да се инвертира.
Както вече казахме, колизиите тук нямат значение, защото се избират хешове с голяма дължина (MD5 например е 16 байта - 128 бита дълъг).
Изобщо, приложението на хеш функциите в тази област е тривиално и сравнително лесно, а основният акцент е върху качеството на самите хеш алгоритми.