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

    Справянето с колизиите се състои от две части:
    1. Намаляване на вероятността за възникване на колизии.
    2. Справяне с колизиите, които все пак възникват.
   
    За точка 1 - избираме по-голям хеш, избираме подходяща хеш функция, която дава по-малко колизии за типичните входни данни.
   
    За точка 2 - има няколко начина да се справим с колизиите. Всички те имат предимства и недостатъци и най-общо трябва да се избира в зависимост от конкретната задача. Тук ще разгледаме няколко такива:
   
    а. Затворено хеширане.
    Идеята е, че се използва само наличната хеш таблица, без да се отделя повече място в паметта за решаване на колизиите.
    Това намалява използваната памет, но очевидно в такава таблица можем да добавим ограничен брой стрингове - точно колкото е размера на таблицата.
    Когато при добавяне на стринг в хеш таблицата се стигне до колизия (тоест на мястото където искаме да запишем стринга има вече друг стринг със същият хеш), просто записваме новият стринг на следващото свободно място в таблицата.
    При търсене, алгоритъмът е същият: Ако на мястото в таблицата има записан стринг, но той не е този който търсим, поглеждаме на следващият елемент. Ако и там не е нашият стринг - на следващият и така нататък, докато открием нашият стринг или 0 - което ще значи, че този стринг го няма в масива.
    Забелязахте ли как, при наличие на колизия, този алгоритъм се превръща в обикновенно сканиране. Това може драстично да свали скоростта на целият алгоритъм. Затова колизиите са толкова вредни и трябва да се вземат всички мерки за недопускането им.
   
    б. Отворено хеширане
    Идеята е, че когато се получи колизия, на съответното място в таблицата, записваме не указател към стринг, а указател към списък от стрингове, където записваме различните стрингове с еднакви хешове.
    Това позволява да се записват неограничено количество стрингове в таблицата. Разбира се при търсене, ако срещнем колизия - тоест указател към списък, този списък пак ще трябва да го сканираме елемент по елемент (или по накакъв друг начин - например с двоично търсене) за да установим има ли го нашият стринг или не.
   
    в. Двойно хеширане.
    Идеята е - при попълване на таблицата, ако срещнем колизия, изчисляваме втора хеш стойност със <b>друг</b> алгоритъм и хешираме стринга във втора таблица. При търсене, ако стринга записан във първата таблица не съвпада, изчисляване вторият хеш за търсеният стринг и гледаме във втората таблица.
    Разбира се във втората таблица също ще са възможни колизии и те трябва да се решат с някакъв друг метод. Но такива колизии ще възникват значително по-рядко и затова ще влияят слабо на скоростта на алгоритъма.
   
    г. Динамично изграждане на хеш таблицата
   
    Като най-общо правило,(сигурно сте забелявали вече) винаги се стремим да използваме най-големият възможен размер на хеш таблиците, за да избегнем колизиите и деградирането на скоростта.
    От друга страна обаче сме ограничени от размера на наличната памет, а и тъй като огромната хеш таблица е обикновенно пълна с много нули и малко данни - чувството, че прахосваме памет е особенно силно.
    Можем да опитаме малко по нетривиално решение: Избираме голям размер на хеша (например 32бита или 64 бита) но не създаваме хеш таблицата в паметта (че как бихме могли? - за упражнение можете да пресметнете колко памет изисква 32битова хеш таблица, ако всеки елемент е указател), а я изграждаме в процеса на добавяне на стрингове в нея, като в паметта записваме само частта от таблицата, която е запълнена в момента.
    Как става това: Сканираме хеша на стринга бит по бит, като всеки бит служи за разклонение на съответното ниво на едно двоично дърво. На последният ред на дървото имаме указатели към стринговете. Възли в дървото прибавяме само когато възникне нужда от тях, така че в паметта винаги имаме само частта на таблицата, която е запълнена с данни.
   
    Този алгоритъм осигурява също константно време за търсене независещо от броя на стринговете в масива, защото претърсването на дървото е винаги постоянно и зависи само от дължината на хеш стойността = дълбочината на дървото. Разбира се това време е по-голямо отколкото директна проверка в таблицата, но по-голямата дължина на хеша - съответно малкият брой колизии, компенсират това забавяне с голяма печалба ако броят на стринговете в таблицата е много голям.