Jadual Hash

Dalam tutorial ini, anda akan mengetahui apa itu jadual hash. Anda juga akan mendapat contoh operasi jadual hash di C, C ++, Java dan Python.

Jadual Hash adalah struktur data yang mewakili data dalam bentuk pasangan nilai-kunci . Setiap kunci dipetakan ke nilai dalam jadual hash. Kekunci digunakan untuk mengindeks nilai / data. Pendekatan serupa diterapkan oleh array bersekutu.

Data ditunjukkan dalam pasangan nilai kunci dengan bantuan kekunci seperti yang ditunjukkan dalam gambar di bawah. Setiap data dikaitkan dengan kunci. Kuncinya adalah bilangan bulat yang menunjukkan data.

1. Jadual Alamat Langsung

Jadual alamat langsung digunakan apabila jumlah ruang yang digunakan oleh jadual tidak menjadi masalah untuk program ini. Di sini, kita menganggap bahawa

  • kunci adalah bilangan bulat kecil
  • bilangan kunci tidak terlalu besar, dan
  • tidak ada dua data yang mempunyai kunci yang sama

Kumpulan bilangan bulat diambil disebut alam semesta U = (0, 1,… ., n-1).
Setiap slot jadual alamat langsung T(0… n-1)mengandungi penunjuk ke elemen yang sesuai dengan data.
Indeks array Tadalah kunci itu sendiri dan kandungannya Tadalah penunjuk ke set (key, element). Sekiranya tidak ada unsur untuk kunci itu, ia dibiarkan sebagai NULL.

Kadang-kadang, kunci itu sendiri adalah data.

Pseudocode untuk operasi

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

Batasan Jadual Alamat Langsung

  • Nilai kunci mestilah kecil.
  • Bilangan kunci mestilah cukup kecil sehingga tidak melepasi had ukuran array.

2. Jadual Hash

Dalam jadual hash, kunci diproses untuk menghasilkan indeks baru yang memetakan elemen yang diperlukan. Proses ini dipanggil hashing.

Biarkan h(x)menjadi fungsi hash dan kmenjadi kunci.
h(k)dikira dan ia digunakan sebagai indeks untuk elemen.

Batasan Jadual Hash

  • Sekiranya indeks yang sama dihasilkan oleh fungsi hash untuk beberapa kunci, konflik akan timbul. Keadaan ini disebut perlanggaran.
    Untuk mengelakkan ini, fungsi hash yang sesuai dipilih. Tetapi, mustahil untuk menghasilkan semua kunci unik kerana |U|>m. Oleh itu, fungsi hash yang baik tidak dapat mencegah perlanggaran sepenuhnya namun dapat mengurangkan jumlah perlanggaran.

Namun, kami mempunyai teknik lain untuk menyelesaikan perlanggaran.

Kelebihan jadual hash berbanding jadual alamat langsung:

Masalah utama dengan jadual alamat langsung adalah ukuran susunan dan nilai kunci yang mungkin besar. Fungsi hash mengurangkan julat indeks dan dengan itu ukuran array juga dikurangkan.
Contohnya, Jika k = 9845648451321, maka h(k) = 11(dengan menggunakan beberapa fungsi hash). Ini membantu menyelamatkan memori yang terbuang sambil memberikan indeks 9845648451321kepada array

Penyelesaian perlanggaran dengan merantai

Dalam teknik ini, jika fungsi hash menghasilkan indeks yang sama untuk beberapa elemen, elemen-elemen ini disimpan dalam indeks yang sama dengan menggunakan senarai berganda yang dihubungkan.

Sekiranya jslot untuk pelbagai elemen, ia mengandungi penunjuk ke bahagian kepala senarai elemen. Sekiranya tidak ada unsur, jmengandungi 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

Pelaksanaan Python, Java, C dan C ++

Python Java C 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 mempunyai ciri-ciri berikut.

  1. Ia tidak boleh menghasilkan kunci yang terlalu besar dan ruang baldi kecil. Ruang terbuang.
  2. Kekunci yang dihasilkan tidak boleh terlalu dekat atau terlalu jauh.
  3. Perlanggaran mesti dikurangkan semaksimum mungkin.

Beberapa kaedah yang digunakan untuk hashing adalah:

Kaedah Pembahagian

Jika kadalah kunci dan mukuran jadual hash, fungsi hash h()dikira sebagai:

h(k) = k mod m

Sebagai contoh, Sekiranya saiz jadual hash 10dan k = 112kemudian h(k) = 112mod 10 = 2. Nilai mmust be the power of 2. Ini kerana kekuatan 2dalam format binari adalah 10, 100, 1000,… . Apabila kita dapati k mod m, kita akan selalu mendapat p-bit 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 pemalar bantu positif,c2
  • i = (0, 1,… .)

Pencucian berganda

Sekiranya perlanggaran berlaku setelah menerapkan fungsi hash h(k), maka fungsi hash lain dikira untuk mencari slot seterusnya.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplikasi Meja Hash

Jadual Hash dilaksanakan di mana

  • pencarian dan penyisipan masa yang berterusan diperlukan
  • aplikasi kriptografi
  • data pengindeksan diperlukan

Artikel menarik...