Asociatívne pole viete používať podobne ako klasické pole, ale ako kľúč môžete využiť ľubovoľný objekt, napr. reťazec. Pri vonkajšom pohľade, asociatívne pole vyzerá takto:

    Kľúč         Hodnota

Prešov       20
Košice       3
Bratislava   11

Asociatívne pole ale nie je súčasťou jazyka C a tak si ho budeme musieť vytvoriť. Klasické pole na vytvorenie asociatívneho poľa nebude stačiť, lebo operácia vyhľadania je neefektívna - silno (lineárne) závisí od počtu prvkov.

Hešovacia funkcia

Skúsime si premeniť asociatívne pole na klasické. Stačilo by zmeniť reťazce na čísla z intervalu 0 až N - 1, kde N je veľkosť poľa. Tak po zadaní reťazca budeme viedieť, kde v poli sa záznam nachádza bez toho aby sme museli prechádzať všetky miesta v poli.

Hešovacia funkcia je navrhnutá tak, aby počet operácií na jej výpočet závisel iba od veľkosti kľúča. Ak je v poli dosť miesta, tak je zložitosť uloženia alebo výberu závislá iba od veľkosti kľúča a nie od počtu uložených prvkov.

Reťazec na číslo vieme zmeniť pomerne jednoducho - spočítame ASCII hodnoty znakov. Špeciálny súčet všetkých bajtov v kľúči nazývame hešovacia funkciua. Hešovacia funkcia zoberie kľúč, väčšinou reťazec, pod ktorým je uložený záznam. Pre rovnaký reťazec nám vyjde stále rovnaké číslo.

Mapovanie bude vyzerať takto:

reťazce    =>   ľubovoľné celé číslo  =>  celé číslo z intervalu 0 až N - 1
          hešovanie                  delenie modulo

Prehľadanie jedného zoznamu bude trvať podstatne kratší čas, lebo vo väčšine prípadov sa záznam bude nachádzať hneď na prvom mieste. Z tohto reťazca hešovacia fumkcia vypočíta kontrolný súčet - číslo získané špeciálnym súčtom hodnôt znakov v reťazci. Z toho kontrolného súčtu určíme index s ktorým budeme pracovať.

Kolízie hešovacej funkcie

Trik s použitím hešovacej funkcie má jedno slabé miesto. Je možné, že vybratá hešovacia funkcia dvom rôznym reťazcom pridelí rovnaké číslo.

    prvý reťazec  --\
                     \
    druhý reťazec ---- hash 

Na rovnakom mieste v poli sa tak nachádzajú dva rôzne záznamy. To prináša viaceré komplikácie. Ak by všetky záznamy boli smerované na jediné miesto, tak by sa asociatívne pole degradovalo na spojkový zoznam. Hešovacia funkcia má za úlohu zabezpečiť, aby sa jednotlivé záznamy v poli rozdelili rovnomerne. Z toho dôvodu hešovacia funkcia nie je klasický súčet, ale komplikovaná funkcia.

Obyčajný súčet znakov nestačí, vo výpočte hodnoty hešovacej funkcie sa nachádzajú aj ďalšie operácie tak aby súčet spĺňal určité vlastnosti. Budete musieť využiť cyklus, ktorý prejde všetky znaky reťazca. Nezabudnite, že posledný znak je vždy nula. V každom kroku upravíme hodnotu hash funkcie podľa aktuálneho znaku.

Pri návrhu sa môžete inšpirovať niektorou z existujúcih hešovacích funkcií:

• Rozsiahly článok o HASH
• Niekoľko HASH funkcií
• na Wikipédii

Pri výpočte hodnoty hash je potrebné použiť bezznamienkovú reprezentáciu unsigned long. Na konci je potrebné hodnotu hešu upraviť pomocou operátora delenia modulo (%) tak aby patrilo do intervalu 0 až N-1.

Hešovacia tabuľka so zreťazením

Aj tá najlepšia hešovacia funkcia môže spôsobiť kolíziu. Množstvo všetkých možných reťazcov je väčšie ako množstvo celých čísel typu int a tak je možné, že viac rôznych reťazcov bude mať priradenú rovnakú hodnotu.

V prípade kolízie nám pomôže spojkový zoznam, ktorý umožní na jednu pozíciu uchovať viac hodnôt. Ak sa na jednom mieste nachádza viac hodnôt, použijeme prehľadávanie vo všetkých hodnotách, až kým nenájdeme hľadanú hodnotu.

Príklad hešovacej tabuľky so zreťazením :

                hash 0: Prešov -> Košice -> Liptovský Mikuláš -> NULL
    stanica     hash 1: Spišská Nová Ves -> Margecany -> NULL
                hash 2: NULL
                hash 3: Kysak-> Dobšiná -> Levoča -> NULL
                hash 4: NULL

Ak je v poli dosť voľného miesta a hešovacia funkcia produkuje málo kolízií tak je táto možnosť málo pravdepodobná. V prípade, že je v poli málo miesta, asociatívne pole sa degraduje na spojkový zoznam. Nové miesto do hešovacej tabuľky pridáme tak, že vytvoríme novú hešovaciu tabuľku s väčšou kapacitou a vložíme do nej obsah starej hešovacej tabuľky.