Struktur Data dan Algoritma - Tabel Hash

Tabel Hash adalah struktur data yang menyimpan data secara asosiatif. Dalam tabel hash, data disimpan dalam format array, di mana setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data menjadi sangat cepat jika kita mengetahui indeks dari data yang diinginkan.

Jadi, ini menjadi struktur data di mana operasi penyisipan dan pencarian sangat cepat terlepas dari ukuran datanya. Tabel Hash menggunakan array sebagai media penyimpanan dan menggunakan teknik hash untuk menghasilkan indeks di mana elemen akan disisipkan atau akan ditempatkan.

Hashing

Hashing adalah teknik untuk mengubah rentang nilai kunci menjadi rentang indeks array. Kami akan menggunakan operator modulo untuk mendapatkan berbagai nilai kunci. Pertimbangkan contoh tabel hash ukuran 20, dan item berikut ini akan disimpan. Item dalam format (key, value).

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

Sr.No.	Kunci	Hash	Indeks Array
1	1	1% 20 = 1	1
2	2	2% 20 = 2	2
3	42	42% 20 = 2	2
4	4	4% 20 = 4	4
5	12	12% 20 = 12	12
6	14	14% 20 = 14	14
7	17	17% 20 = 17	17
8	13	13% 20 = 13	13
9	37	37% 20 = 17	17

Pemeriksaan Linier

Seperti yang bisa kita lihat, mungkin saja teknik hashing digunakan untuk membuat indeks array yang sudah digunakan. Dalam kasus seperti itu, kita dapat mencari lokasi kosong berikutnya dalam larik dengan melihat ke sel berikutnya hingga menemukan sel kosong. Teknik ini disebut probing linier.

Sr.No.	Kunci	Hash	Indeks Array	Setelah Probing Linear, Indeks Array
1	1	1% 20 = 1	1	1
2	2	2% 20 = 2	2	2
3	42	42% 20 = 2	2	3
4	4	4% 20 = 4	4	4
5	12	12% 20 = 12	12	12
6	14	14% 20 = 14	14	14
7	17	17% 20 = 17	17	17
8	13	13% 20 = 13	13	13
9	37	37% 20 = 17	17	18

Operasi Dasar

Berikut adalah operasi utama dasar tabel hash.

Search - Mencari elemen dalam tabel hash.
Insert - menyisipkan elemen dalam tabel hash.
delete - Menghapus elemen dari tabel hash.

DataItem

Tentukan item data yang memiliki beberapa data dan kunci, berdasarkan mana pencarian akan dilakukan dalam tabel hash.

struct DataItem {
   int data;
   int key;
};

Metode Hash

Tentukan metode hashing untuk menghitung kode hash dari kunci item data.

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

Operasi Pencarian

Kapanpun sebuah elemen akan dicari, hitung kode hash dari kunci yang dilewatkan dan temukan elemen tersebut menggunakan kode hash tersebut sebagai indeks dalam larik. Gunakan probing linier untuk mendapatkan elemen di depan jika elemen tidak ditemukan pada kode hash yang dihitung.

Contoh

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

   return NULL;        
}

Sisipkan Operasi

Kapan pun sebuah elemen akan disisipkan, hitung kode hash dari kunci yang dilewatkan dan temukan indeks menggunakan kode hash itu sebagai indeks dalam larik. Gunakan probe linier untuk lokasi kosong, jika elemen ditemukan pada kode hash yang dihitung.

Contoh

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[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

Hapus Operasi

Kapan pun sebuah elemen akan dihapus, hitung kode hash dari kunci yang dilewatkan dan temukan indeks menggunakan kode hash itu sebagai indeks dalam larik. Gunakan probing linier untuk mendapatkan elemen di depan jika elemen tidak ditemukan pada kode hash yang dihitung. Saat ditemukan, simpan item dummy di sana untuk menjaga performa tabel hash tetap utuh.

Contoh

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[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
		
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }  
	
   return NULL;        
}

Untuk mengetahui tentang implementasi hash dalam bahasa pemrograman C, silakan klik di sini .