Datastruktur och algoritmer – Hashtabell

Hashtabell är en datastruktur som lagrar data på ett associativt sätt. I en hashtabell lagras data i ett matrisformat, där varje datavärde har sitt eget unika indexvärde. Tillgången till data blir mycket snabb om vi känner till indexet för den önskade datan.

Det blir därmed en datastruktur där insättning och sökning går mycket snabbt oberoende av datans storlek. Hashtabellen använder en array som lagringsmedium och använder hashteknik för att generera ett index där ett element ska införas eller placeras från.

Hashing

Hashing är en teknik för att omvandla en rad nyckelvärden till en rad index i en array. Vi kommer att använda modulooperatören för att få fram ett intervall av nyckelvärden. Ta ett exempel på en hashtabell av storlek 20, och följande objekt ska lagras. Posterna är i formatet (nyckel, värde).

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

Linjär sondering

Som vi kan se, kan det hända att hash-tekniken används för att skapa ett redan använt index i matrisen. I ett sådant fall kan vi söka efter nästa tomma plats i matrisen genom att titta i nästa cell tills vi hittar en tom cell. Denna teknik kallas linear probing.

Grundläggande operationer

Följande är de grundläggande primära operationer som utförs av ett hashbord.

• Sök – söker ett element i en hashtabell.

• Insätt – sätter in ett element i en hashtabell.

• Släpp – tar bort ett element från en hashtabell.

DataItem

Definiera ett dataelement med vissa data och en nyckel, utifrån vilket sökningen ska utföras i en hashtabell.

struct DataItem { int data; int key;};

Hashmetod

Definiera en hashmetod för att beräkna hashkoden för datapostens nyckel.

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

Sökoperation

När ett element ska sökas, beräkna hashkoden för den nyckel som överlämnats och hitta elementet med hjälp av den hashkoden som index i matrisen. Använd linjär probing för att få elementet framåt om elementet inte hittas vid den beräknade hashkoden.

Exempel

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; }

Insert Operation

När ett element ska sättas in, beräkna hashkoden för den nyckel som överlämnats och lokalisera indexet med hjälp av den hashkoden som index i matrisen. Använd linjär sökning för tom plats om ett element hittas vid den beräknade hashkoden.

Exempel

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; }

Släpp operation

När ett element ska tas bort, beräkna hashkoden för den nyckel som överlämnats och hitta indexet genom att använda den hashkoden som index i matrisen. Använd linjär probing för att få elementet framåt om ett element inte hittas vid den beräknade hashkoden. När den hittas, lagra ett dummyelement där för att hålla hashtabellens prestanda intakt.

Exempel

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; }

För att få veta mer om hashimplementering i programmeringsspråket C, klicka här.