Хеширане

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

Хеш таблица – структура от данни, съдържаща ключ и данни. Ако два елемента имат един и същ ключ, то те са идентични.

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

Хеш функция – функция, която извършва процеса хеширане, т.е. чрез преобразования съспоставя ключ на адрес. Т.е. при n ключа в хеш таблицата, хеш функцията трябва да съпоставя на всеки ключ адрес от таблицата, който в случая е число от 0 до n – 1.

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

Сега нега разгледаме и проблемите в хеширането. Безспорно най-гоемия проблем са тъй наречените синоними или колизии. Тоест два различни ключа сочат един и същи адрес. На практика при паролите това значи, че ако хеширате пароли, могат да се намерят две пароли, които да бъдат „верни” за даден потребител... Колизиите, зависят от алгоритъма за хеширане, но няма алгоритъм, за който няма колизии(освен тривиалния, разбира се, т.е. съпоставяте на даден низ, същият).

Дали даден алгоритъм е удачен, се определя от две неща : изчислителното време, нужно за изпълнение на алгоритъма и това да разпределя относително равномерно в различните хеш адреси. Нека приемем, че ключовете на елементите са цели числа(много удачно за ползване на масиви). Ако не са винаги може да съпоставим такива по някакво правило(например ако ключовете са символни низове, можем да съпоставим на всяко неговият ASCII код, за hello получаваме 104 + 101 + 108 + 108 + 111 + 111 = 532). Понякога е удачно да се взема предвид не само полученият резултат, но и позицията на символа в низа. Така можем за пример да считаме че работим с целочислени ключове : за всеки символен низ от вида a1, a2, … , an можем да представим като число, представено в b-ична бройна система, като b e броят на допустимите символи.

Нека за примерите е дадена хеш таблица с капацитет n и ключ k.

Класически алгоритми за хеш функции:

1. О статък при деление с размера на таблицата(масив в общия случай ).
За всеки елемент , делим позицията му в таблицата на общия брой елементи и записваме остатъка от делението. При този алгоритъм не е удачно да се избира число n, степен на двойката. Ако е така, то хеш кода на даден ключ k, ще бъдат младшите битове на k.

Пример: Нека n = 16, k = 173. Остатъкът 173 % 16 = 13, което можем да запишем като 1101, което всъщност са младшите битове на 173(10101101).

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

2. Мултипликативно
Избираме константа а (реална). 0 < а < 1 . Тогава за даден елемент имаме хеш функцията:

h(k) = [n.{k.a}]

където {k.a} е дробната част на реалното число а, а [] означават цялата част. Въпреки че изборът на константата а е произволен, при някой стойности алгоритъмът се държи по-добре. Кнут(1968) препоръчва да се използва златното сечение : а = 0.6180339887…

3. Извличане на цифри
Избирате само цифри, стоящи на определени позиции в масива - да кажем на 1,3 и 5-то място.
Пример: за ключовете 123569, 425435, 546754, 676576 ще получим съответно 136, 453, 565, 667. В случая n = 1000(тъй като при извличане на 3 цифри можем да получим число в интервала [0…999]) Методът има добра успеваемост, когато числата не съдържат много повтарящи се цифри.

4. Сгъване
Ако ключовете са много големи числа се делят на части и се прилага аритметична операция (предните 3 алгоритъма) . За пример числото 123569425435 можем да разделим на 2 чести, т.е. на 123569 и 425435, да извлечем цифрите от 1, 3 и 5-то място, т.е. 136 и 453 и да ги съберем. Окончателно получаваме 589.

5. Повдигане на средата в квадрат
Извличате средните р цифри и ги повдигате в квадрат. Пр. 12567134280980 има среда 134, т.е. кода е 134.134 = 17956. Ако резултатът надхвърля n, се премахват първите няколко значещи цифри. Т.е. ако n = 10001, то от 17956 се премахва първата цифра и резултатът е 7956. Бих искал да обърна внимание, че последната операция не е еквивалентна на намиране на остатък при делене.

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

result = инициализиране();
while(c = следващ символ())
{
result = комбиниране(result, c);
result = вътрешно_модифициране(result);
}
result = допълнително_модифициране(result);

6. Адитивно хеширане
Това е най-простото, но и най-неефективното решение. Сумирате ASCII кодовете на символите един по един и сумата се взема по модул размера на масива( key % size ) .

unsigned long hashFunction(const char *key, unsigned long size)
{
unsigned long result = 0;
while (*key)
result += (unsigned char) *key++;
return result % size;
}

Обикновено дължината на низа се включва в сумата, за да може изрично да влияе на хеш кода.
unsigned long result = strlen(key);

7. Хеширане по Пиърсън
Въвеждаме допълнителен масив tab[] , съдържащ пермутация на числата от 0 до 255(случайно нареждане, съдържащо всички числа в този интервал). Полученият хеш код е еднобайтов: от 0 до 255. За да бъдат повече от еднобайтови резултатите, може да извикате алгоритъма няколко пъти с различни масиви tab[] (т.е. различни наредби на числата), при което всяко извикване ще дава един байт от резултата. Ето кода:

unsigned char hashFunc(const char *key, unsigned long size, const unsigned char tab[])
{ unsigned long result = strlen(key);
while (*key)
result = tab[ result ^ ( (unsigned char) * key++) ];
return result;

}/ * Този алгоритъм е написан на езика С, може да го модифицирате ако ви трябва да друг език*/

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