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

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

    Пример от практиката: Парсерът на FASM (flatassembler) използва хеш функция с дължина 32бита за бързо търсене в списъка с етикети по време на компилацията. При първата реализация (до версия 1.51 - ако си спомням добре) се използваше директно търсене в списъка с етикети, като се сравняваха хеш стойностите.
    При компилиране на големи сорсове с много етикети, бързодействието бързо започваше да пада и по същество времето за компилация зависеше от квадрата на броя редове в програмата.
    Когато тези ефекти се появиха (при появяването на достатъчно големи програми, написани на FASM), Томаш Гриштар (автора на FASM), смени алгоритъма за търсене с описаният по-горе алгоритъм с двоично хеш дърво.
    Това увеличи скоростта на парсера 4 до 5 пъти.
    Следващата стъпка беше наистина впечатляваща: След замяна на предишната хеш функция в компилатора с нова (по алгоритъма <A HREF="http://www.isthe.com/chongo/tech/comp/fnv/" TARGET="_blank" class="grau_normal">FNV-1a</A>), скоростта на парсера се увеличи <b>25 пъти</b> на някои тестове.
    От този момент, работата на парсера стана толкова бърза, че при всички практически случаи съставлява малка част от цялото време на компилацията.
    Можете да погледнете цялата дискусия свързана с тази история тук: <A HREF="http://board.flatassembler.net/viewtopic.php?t=854" TARGET="_blank" class="grau_normal">Дискусия за промените във FASM 1.51 (en)</A>

    Ето и като пример, сорса на алгоритъма FNV-1a, използван във <A HREF="http://flatassembler.net" TARGET="_blank" class="grau_normal">FASM (flatassembler)</A>, а също и в <A HREF="http://fresh.flatassembler.net" TARGET="_blank" class="grau_normal">проекта Fresh</A>:

CODE

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

;------------------------------------------------- ; 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 кода на всеки символ се правят някакви сложни аритметични или логически дествия, с цел да се направи изходното число да бъде по възможност зависимо от всички входни символи. Често се използват ротация и умножения на прости числа и т.п. Всеки алгоритъм си е сам за себе си...