Heširanje ulančavanjem

Primer heširanja ulančavanjem. Unos u tabeli koja se koristi za smeštanje parova ključ/vrednost zove se bucket. Za potrebe ovog primera sudari bucketa su označeni su u rastućem poretku, počevši od bucketa 0.

Heširanje ulančavanjem, koje se drugačije naziva i heširanje spajanjem, je strategija za rešavanja sudara u heš tabeli koja predstavlja hibrid odvojenog nizanja i otvorenog adresiranja. Kod heširanja ulančanjem, više ključeva se preslikava u isti broj, tj. elementi sa različitim ključevima se mogu smestiti u isto polje hash tabele. Ova tehnika može zahtevati dosta memorije zato što tabela mora biti dovoljno velika da održi faktor opterećenja koji obezbeđuje dobre performanse (obično je broj stavki u tabeli dva puta veći od broja ključeva), i dodatna memorija mora biti obezbeđena za sve prve ključeve u lancu (osim ukoliko se koriste zaglavlja listi, kada dodatna memorija mora biti obezbeđena za sve ključeve u lancu).

Posmatrajuci niz "qrj", "aty", "qur", "dim", "ofu", "gci" , "rhv", "clq", "ecd", "qsu" slučajno generisanih stringova dužine tri karaktera, tabela koja sledi bila bi generisana (koristeći Bob Jenkins' One-at-a-Time hash algorithm) tabelom veličine 10:

(null)
"clq"
"qur"
(null)
(null)
"dim"
"aty"	"qsu"
"rhv"
"qrj"	"ofu"	"gcl"	"ecd"
(null)

Karakteristike

Ova strategija je efikasna i veoma jednostavna za implementaciju. Međutim, ponekad upotreba dodatne memorije može biti nepristupačna, a najčesće korišćena alternativa, otvoreno adresiranje, ima nedostatke koje umanjuju performanse. Glavni nedostatak otvorenog adresiranja je primarno i sekundarno grupisanje, u kojima se pristupa dugačkim nizovima korišćenih bucketa koji sadrze elemente sa različitim hash adresama; elementi koji odgovaraju jednoj hash adresi mogu na ovaj način produžiti pretragu za elementima sa drugim hash adresama.

Jedno rešenje ovog problema je heširanje ulančavanjem. Heširanje ulančavanjem koristi sličnu tehniku kao i odvojeno nizanje, ali umesto alociranja novih čvorova za povezanu listu, buketi u postojećoj tabeli su iskorišćeni. Prvi prazan bucket u tabeli u trenutku sudara se smatra buketom sudara. Kada dođe do sudara bilo gde u tabeli, element se smešta u buket kolizije i na taj način je napravljena veza izmedju lanca i buketa kolizije. Moguce je da se novoubačeni element sudari sa elementima sa različitim hash-adresama, kao sto je slučaj u prethodnom primeru kada je element "clq" ubacen. Lanac za "clq" je "rekao" da se spoji sa lancem elementa "qrj", odakle sledi naziv algoritma. Međutim, stepen grupisanja je manji u poređenju sa grupisanjem koje je posledica otvorenog adresiranja. Na primer, kada do spajanja dodje, dužina lanca raste samo za 1, dok kod otvorenog adresiranja dužina lanca povećava se proizvoljno.

Važna optimizacija, da bi se smanjio efekat spajanja, jeste da se ograniči adresni prostor hash funkcije samo na podskup tabele. Na primer, ako je tabela veličine M sa buketima numerisanim od 0 do M − 1, mozemo ograničiti adresni prostor tako da hash-funkcija dodeljuje samo adrese prvim N lokacijama u tabeli. Preostalih M − N buketa, koji se nazivaju cellar, koriste se isključivo za skladištenje elemenata dovode do sudara tokom ubacivanja. Ne moze doći do spajanja dok je cellar ne isprazni.

Optimalan izbor odnosa N i M zavisi od faktora opterećenja (ili popunjenosti tabele). Pažljiva analiza pokazuje da vrednost N = 0.86 × M doprinosi optimalnim performansama za većinu faktora opterecenja. Druge varijante su takođe moguće kako bi smanjile vreme pretraživanja.

Implementacija u C-u

/* htab je veličina heš tabele,
   N je veličina adresnog prostora heš funkcije, i 
   M je veličina cele tabele uključujuci i cellar.
   Sudari bucketa su predstavljeni u opadajućem poretku, počevši od bucketa M-1. */

int insert ( char key[] )
{
  unsigned h = hash ( key, strlen ( key ) ) % N;

  if ( htab[h] == NULL ) {
    /* Kreirati novi lanac */
    htab[h] = make_node ( key, NULL );
  } else {
    struct node *it;
    int cursor = M-1;

    /* Pronađi prvi prazan bucket */
    while ( cursor >= 0 && htab[cursor] != NULL )
      --cursor;

    /* Tabela je puna, kraj programa */
    if ( cursor == -1 )
      return -1;

    htab[cursor] = make_node ( key, NULL );
    
    /* Pronađi poslednji čvor u lancu označi ga*/
    it = htab[h];

    while ( it->next != NULL )
      it = it->next;

    it->next = htab[cursor];
  }

  return 0;
}

Jedna od prednosti ove strategije je da algoritam pretrage kod odvojenog nizanja moze biti korišćcen bez promene i kod heširanja ulančavanjem.

Pregled u C-u:

char *find ( char key[] )
{
  unsigned h = hash ( key, strlen ( key ) ) % N;

  if ( htab[h] != NULL ) {
    struct node *it;

    /* Pronađi lanac sa indeksom h */
    for ( it = htab[h]; it != NULL; it = it->next ) {
      if ( strcmp ( key, it->data ) == 0 )
        return it->data;
    }
  }

  return NULL;
}

Performanse

Heširanje spajanjem sprečava primarno i sekundarno grupisanje, i ovo se može iskoristiti prilikom implementacije efikasnog algoritma pretrage kod odvojenog nizanja. Ako su lanci kratki, ova strategija je veoma efikasna i koristi malo memorije. Kao i kod otvorenog adresiranja, brisanje iz hash tabele koja koristi ulančavanje je nezgodno i potencijalno skupo, i promena veličine tabele je izuzetno skupa i treba retko da se obavlja.