Tabel Hash

Dalam tutorial ini, Anda akan mempelajari apa itu tabel hash. Selain itu, Anda akan menemukan contoh kerja operasi tabel hash di C, C ++, Java dan Python.

Tabel hash merupakan struktur data yang merepresentasikan data berupa key-value pair. Setiap kunci dipetakan ke nilai dalam tabel hash. Kunci digunakan untuk mengindeks nilai / data. Pendekatan serupa diterapkan oleh array asosiatif.

Data direpresentasikan dalam pasangan nilai kunci dengan bantuan kunci seperti yang ditunjukkan pada gambar di bawah ini. Setiap data dikaitkan dengan sebuah kunci. Kuncinya adalah bilangan bulat yang mengarah ke data.

1. Tabel Alamat Langsung

Tabel alamat langsung digunakan ketika jumlah ruang yang digunakan oleh tabel tidak menjadi masalah untuk program. Di sini, kami berasumsi bahwa

  • kuncinya adalah bilangan bulat kecil
  • jumlah tombol tidak terlalu besar, dan
  • tidak ada dua data yang memiliki kunci yang sama

Kumpulan bilangan bulat diambil disebut alam semesta U = (0, 1,… ., n-1).
Setiap slot tabel alamat langsung T(0… n-1)berisi penunjuk ke elemen yang sesuai dengan data.
Indeks dari array Tadalah kunci itu sendiri dan isinya Tadalah penunjuk ke set (key, element). Jika tidak ada elemen untuk kunci, maka dibiarkan sebagai NULL.

Terkadang, kuncinya sendiri adalah datanya.

Pseudocode untuk operasi

 directAddressSearch(T, k) return T(k) directAddressInsert(T, x) T(x.key) = x directAddressDelete(T, x) T(x.key) = NIL

Batasan Tabel Alamat Langsung

  • Nilai kunci harus kecil.
  • Jumlah kunci harus cukup kecil agar tidak melewati batas ukuran larik.

2. Tabel Hash

Dalam tabel hash, kunci diproses untuk menghasilkan indeks baru yang memetakan ke elemen yang diperlukan. Proses ini disebut hashing.

Membiarkan h(x)menjadi fungsi hash dan kmenjadi kunci.
h(k)dihitung dan digunakan sebagai indeks untuk elemen.

Batasan Tabel Hash

  • Jika indeks yang sama dihasilkan oleh fungsi hash untuk beberapa kunci, maka konflik muncul. Situasi ini disebut tabrakan.
    Untuk menghindari ini, fungsi hash yang sesuai dipilih. Namun, tidak mungkin untuk menghasilkan semua kunci unik karena |U|>m. Oleh karena itu, fungsi hash yang baik mungkin tidak dapat mencegah tabrakan sepenuhnya, namun dapat mengurangi jumlah tabrakan.

Namun, kami memiliki teknik lain untuk mengatasi tabrakan.

Keuntungan tabel hash dibandingkan tabel alamat langsung:

Masalah utama dengan tabel alamat langsung adalah ukuran larik dan kemungkinan nilai kunci yang besar. Fungsi hash mengurangi jangkauan indeks dan dengan demikian ukuran array juga berkurang.
Misalnya, If k = 9845648451321, then h(k) = 11(dengan menggunakan beberapa fungsi hash). Ini membantu dalam menghemat memori yang terbuang saat memberikan indeks 9845648451321ke array

Resolusi tabrakan dengan rantai

Dalam teknik ini, jika fungsi hash menghasilkan indeks yang sama untuk beberapa elemen, elemen ini disimpan dalam indeks yang sama dengan menggunakan daftar tertaut ganda.

Jika jmerupakan slot untuk beberapa elemen, ini berisi penunjuk ke kepala dari daftar elemen. Jika tidak ada elemen, jberisi NIL.

Pseudocode untuk operasi

 chainedHashSearch(T, k) return T(h(k)) chainedHashInsert(T, x) T(h(x.key)) = x //insert at the head chainedHashDelete(T, x) T(h(x.key)) = NIL

Implementasi Python, Java, C dan C ++

Python Java C ++ 
 # Python program to demonstrate working of HashTable hashTable = ((),) * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable(index) = (key, data) def removeData(key): index = hashFunction(key) hashTable(index) = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
 // Java program to demonstrate working of HashTable import java.util.*; class HashTable ( public static void main(String args()) ( Hashtable ht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); ) ) 
 // Implementing hash table in C #include #include struct set ( int key; int data; ); struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) ( return (key % capacity); ) int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i < n / 2; i++) ( if (n % i == 0) ( return 0; ) ) return 1; ) int getPrime(int n) ( if (n % 2 == 0) ( n++; ) while (!checkPrime(n)) ( n += 2; ) return n; ) void init_array() ( capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) ( array(i).key = 0; array(i).data = 0; ) ) void insert(int key, int data) ( int index = hashFunction(key); if (array(index).data == 0) ( array(index).key = key; array(index).data = data; size++; printf(" Key (%d) has been inserted ", key); ) else if (array(index).key == key) ( array(index).data = data; ) else ( printf(" Collision occured "); ) ) void remove_element(int key) ( int index = hashFunction(key); if (array(index).data == 0) ( printf(" This key does not exist "); ) else ( array(index).key = 0; array(index).data = 0; size--; printf(" Key (%d) has been removed ", key); ) ) void display() ( int i; for (i = 0; i < capacity; i++) ( if (array(i).data == 0) ( printf(" array(%d): / ", i); ) else ( printf(" key: %d array(%d): %d ", array(i).key, i, array(i).data); ) ) ) int size_of_hashtable() ( return size; ) int main() ( int choice, key, data, n; int c = 0; init_array(); do ( printf("1.Insert item in the Hash Table" "2.Remove item from the Hash Table" "3.Check the size of Hash Table" "4.Display a Hash Table" " Please enter your choice: "); scanf("%d", &choice); switch (choice) ( case 1: printf("Enter key -: "); scanf("%d", &key); printf("Enter data -: "); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d", n); break; case 4: display(); break; default: printf("Invalid Input"); ) printf("Do you want to continue (press 1 for yes): "); scanf("%d", &c); ) while (c == 1); )
 // Implementing hash table in C++ #include #include using namespace std; class HashTable ( int capacity; list *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i  capacity = size; table = new list(capacity); ) void HashTable::insertItem(int key, int data) ( int index = hashFunction(key); table(index).push_back(data); ) void HashTable::deleteItem(int key) ( int index = hashFunction(key); list::iterator i; for (i = table(index).begin(); i != table(index).end(); i++) ( if (*i == key) break; ) if (i != table(index).end()) table(index).erase(i); ) void HashTable::displayHash() ( for (int i = 0; i < capacity; i++) ( cout << "table(" << i << ")"; for (auto x : table(i)) cout < " << x; cout << endl; ) ) int main() ( int key() = (231, 321, 212, 321, 433, 262); int data() = (123, 432, 523, 43, 423, 111); int size = sizeof(key) / sizeof(key(0)); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key(i), data(i)); h.deleteItem(12); h.displayHash(); )

Fungsi Hash yang Baik

Fungsi hash yang baik memiliki karakteristik sebagai berikut.

  1. Ini tidak boleh menghasilkan kunci yang terlalu besar dan ruang keranjang kecil. Ruang terbuang.
  2. Kunci yang dihasilkan tidak boleh terlalu dekat atau terlalu jauh.
  3. Tabrakan harus diminimalkan semaksimal mungkin.

Beberapa metode yang digunakan untuk hashing adalah:

Metode Pembagian

Jika kadalah kunci dan mmerupakan ukuran tabel hash, fungsi hash h()dihitung sebagai:

h(k) = k mod m

Sebagai contoh, Jika ukuran tabel hash 10dan k = 112kemudian h(k) = 112mod 10 = 2. Nilai mtidak boleh menjadi kekuatan 2. Ini karena kekuatan 2dalam format biner adalah 10, 100, 1000,… . Ketika kami menemukan k mod m, kami akan selalu mendapatkan p-bit urutan yang lebih rendah.

 if m = 22, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 01 if m = 23, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 001 if m = 24, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 0001 if m = 2p, then h(k) = p lower bits of m

Multiplication Method

h(k) = ⌊m(kA mod 1)⌋
where,

  • kA mod 1 gives the fractional part kA,
  • ⌊ ⌋ gives the floor value
  • A is any constant. The value of A lies between 0 and 1. But, an optimal choice will be ≈ (√5-1)/2 suggested by Knuth.

Universal Hashing

In Universal hashing, the hash function is chosen at random independent of keys.

Open Addressing

Multiple values can be stored in a single slot in a normal hash table.

By using open addressing, each slot is either filled with a single key or left NIL. All the elements are stored in the hash table itself.

Unlike chaining, multiple elements cannot be fit into the same slot.

Open addressing is basically a collision resolving technique. Some of the methods used by open addressing are:

Linear Probing

In linear probing, collision is resolved by checking the next slot.
h(k, i) = (h'(k) + i) mod m
where,

  • i = (0, 1,… .)
  • h'(k) is a new hash function

If a collision occurs at h(k, 0), then h(k, 1) is checked. In this way, the value of i is incremented linearly.
The problem with linear probing is that a cluster of adjacent slots is filled. When inserting a new element, the entire cluster must be traversed. This adds to the time required to perform operations on the hash table.

Quadratic Probing

In quadratic probing, the spacing between the slots is increased (greater than one) by using the following relation.
h(k, i) = (h'(k) + c1i + c2i2) mod m
where,

  • c1dan merupakan konstanta bantu positif,c2
  • i = (0, 1,… .)

Hash ganda

Jika tabrakan terjadi setelah menerapkan fungsi hash h(k), maka fungsi hash lainnya dihitung untuk menemukan slot berikutnya.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplikasi Tabel Hash

Tabel hash diimplementasikan di mana

  • pencarian dan penyisipan waktu konstan diperlukan
  • aplikasi kriptografi
  • data pengindeksan diperlukan

Artikel yang menarik...