Datová struktura a algoritmy – Hash tabulka

Hash tabulka je datová struktura, která ukládá data asociativním způsobem. V hashovací tabulce jsou data uložena ve formátu pole, kde každá datová hodnota má svou vlastní jedinečnou hodnotu indexu. Přístup k datům se stává velmi rychlým, pokud známe index požadovaných dat.

Stává se tak datovou strukturou, ve které jsou operace vkládání a vyhledávání velmi rychlé bez ohledu na velikost dat. Hašovací tabulka používá pole jako paměťové médium a ke generování indexu, kam má být prvek vložen nebo odkud má být vyhledán, používá techniku hašování.

Hašování

Hašování je technika pro převod rozsahu hodnot klíčů na rozsah indexů pole. K získání rozsahu hodnot klíčů použijeme operátor modulo. Uvažujme příklad hashovací tabulky o velikosti 20 a následující položky mají být uloženy. Položky jsou ve formátu (klíč,hodnota).

• (1,20)
• (2,70)
• (42,80)
• (4,25)
• (12,44)
• (14,32)
• (17,11)
• (13,78)
• (37,98)

.

Lineární sondování

Jak vidíme, může se stát, že technika hashování je použita k vytvoření již použitého indexu pole. V takovém případě můžeme hledat další prázdné místo v poli tak, že se podíváme do další buňky, dokud nenajdeme prázdnou buňku. Tato technika se nazývá lineární sondování.

Základní operace

Následují základní primární operace hašovací tabulky.

• Vyhledávání – vyhledá prvek v hašovací tabulce.

• Vkládání – vloží prvek do hašovací tabulky.

• odstranění – odstraní prvek z hašovací tabulky.

DataItem

Definuje datový prvek s nějakými údaji a klíčem, na jehož základě má být provedeno vyhledávání v hašovací tabulce.

struct DataItem { int data; int key;};

Metoda hašování

Definice hašovací metody pro výpočet hašovacího kódu klíče datové položky.

int hashCode(int key){ return key % SIZE;}

Vyhledávací operace

Kdykoli se má vyhledat prvek, vypočítá se hašovací kód předaného klíče a prvek se vyhledá pomocí tohoto hašovacího kódu jako indexu v poli. Pokud není prvek nalezen ve vypočteném hash kódu, použijte lineární sondování k získání prvku dopředu.

Příklad

struct DataItem *search(int key) { //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray != NULL) { if(hashArray->key == key) return hashArray; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Operace vložení

Kdykoli má být vložen prvek, vypočítejte hash kód předaného klíče a najděte index pomocí tohoto hash kódu jako indexu v poli. Pokud je prvek nalezen na vypočteném hash kódu, použijte lineární sondování prázdného umístění.

Příklad

void insert(int key,int data) { struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data; item->key = key; //get the hash int hashIndex = hashCode(key); //move in array until an empty or deleted cell while(hashArray != NULL && hashArray->key != -1) { //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } hashArray = item; }

Operace odstranění

Kdykoli má být prvek odstraněn, vypočítejte hash kód předaného klíče a vyhledejte index pomocí tohoto hash kódu jako indexu v poli. Pokud není prvek nalezen na vypočteném hash kódu, použijte lineární sondování pro získání prvku dopředu. Když je nalezen, uložte tam fiktivní prvek, abyste zachovali výkonnost hašovací tabulky.

Příklad

struct DataItem* delete(struct DataItem* item) { int key = item->key; //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray !=NULL) { if(hashArray->key == key) { struct DataItem* temp = hashArray; //assign a dummy item at deleted position hashArray = dummyItem; return temp; } //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Chcete-li se dozvědět o implementaci hašování v programovacím jazyce C, klikněte zde.

.