Hash tabula

Šajā apmācībā jūs uzzināsiet, kas ir jaukšanas tabula. Jūs atradīsit arī piemērotus hash tabulas operāciju piemērus C, C ++, Java un Python.

Hash tabula ir datu struktūra, kas attēlo datus atslēgas vērtību pāru veidā. Katra atslēga tiek kartēta ar vērtību jaukšanas tabulā. Taustiņi tiek izmantoti vērtību / datu indeksēšanai. Līdzīgu pieeju izmanto asociatīvs masīvs.

Dati tiek parādīti atslēgas vērtību pārī ar taustiņu palīdzību, kā parādīts attēlā zemāk. Visi dati ir saistīti ar atslēgu. Galvenais ir vesels skaitlis, kas norāda uz datiem.

1. Tiešā adrešu tabula

Tiešās adrešu tabula tiek izmantota, ja tabulas izmantotais vietas apjoms programmai nav problēma. Šeit mēs to pieņemam

  • taustiņi ir mazi veseli skaitļi
  • taustiņu skaits nav pārāk liels, un
  • diviem datiem nav vienādas atslēgas

Tiek uzskatīts, ka veselu skaitļu kopums tiek saukts par Visumu U = (0, 1,… ., n-1).
Katrā tiešās adreses tabulas slotā T(0… n-1)ir norāde uz elementu, kas atbilst datiem.
Masīva indekss Tir pati atslēga, un tā saturs Tir rādītājs kopai (key, element). Ja atslēgai nav elementa, tas tiek atstāts kā NULL.

Dažreiz pats galvenais ir dati.

Pseidokods operācijām

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

Tiešās adrešu tabulas ierobežojumi

  • Atslēgas vērtībai jābūt mazai.
  • Atslēgu skaitam jābūt pietiekami mazam, lai tas nepārsniegtu masīva lieluma ierobežojumu.

2. Hash tabula

Jaukšanas tabulā atslēgas tiek apstrādātas, lai izveidotu jaunu indeksu, kas kartē nepieciešamo elementu. Šo procesu sauc par jaukšanu.

Ļaut h(x)būt hash funkcija un kbūt atslēga.
h(k)tiek aprēķināts, un to izmanto kā elementa indeksu.

Hash tabulas ierobežojumi

  • Ja vienu un to pašu indeksu rada jaucējfunkcija vairākiem taustiņiem, rodas konflikts. Šo situāciju sauc par sadursmi.
    Lai no tā izvairītos, tiek izvēlēta piemērota hash funkcija. Bet nav iespējams izgatavot visas unikālās atslēgas, jo |U|>m. Tādējādi laba jaukšanas funkcija var pilnībā neaizkavēt sadursmes, tomēr tā var samazināt sadursmju skaitu.

Tomēr mums ir citas metodes, kā atrisināt sadursmi.

Hash tabulas priekšrocības salīdzinājumā ar tiešo adrešu tabulu:

Galvenās tiešās adrešu tabulas problēmas ir masīva lielums un, iespējams, lielā atslēgas vērtība. Hash funkcija samazina indeksa diapazonu un tādējādi tiek samazināts arī masīva lielums.
Piemēram, Ja k = 9845648451321, tad h(k) = 11(izmantojot kādu jaucējfunkciju). Tas palīdz ietaupīt iztērēto atmiņu, vienlaikus nodrošinot 9845648451321masīva indeksu

Sadursmes atrisināšana, izmantojot ķēdi

Šajā metodē, ja jaucējfunkcija rada vienu un to pašu indeksu vairākiem elementiem, šie elementi tiek glabāti tajā pašā indeksā, izmantojot divreiz saistītu sarakstu.

Ja jir vairāku elementu slota, tajā ir norāde uz elementu saraksta galvu. Ja elementa nav, jsatur NIL.

Pseidokods operācijām

 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

Python, Java, C un C ++ ieviešana

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(); )

Labas hash funkcijas

Labai hash funkcijai ir šādas īpašības.

  1. Tam nevajadzētu ģenerēt pārāk lielas atslēgas un maza vieta. Vieta ir izšķiesta.
  2. Ģenerētajām atslēgām nevajadzētu būt ne ļoti tuvu, ne pārāk tālu.
  3. Sadursme ir pēc iespējas jāsamazina.

Dažas no sajaukšanai izmantotajām metodēm ir:

Dalīšanas metode

Ja kir atslēga un mhash tabulas lielums, hash funkcija h()tiek aprēķināta šādi:

h(k) = k mod m

Piemēram, ja jaucējtabulas izmērs ir 10un k = 112pēc tam h(k) = 112mod 10 = 2. Vērtība mnedrīkst būt 2. Tas ir tāpēc, ka 2binārā formāta pilnvaras ir 10, 100, 1000,… . Kad atradīsim k mod m, mēs vienmēr iegūsim zemākas kārtas p-bitus.

 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,

  • c1un ir pozitīvas palīgkonstantes,c2
  • i = (0, 1,… .)

Dubultā jaukšana

Ja pēc hash funkcijas izmantošanas notiek sadursme h(k), tiek aprēķināta cita hash funkcija, lai atrastu nākamo slotu.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash tabulas lietojumi

Hash tabulas tiek ieviestas kur

  • Nepieciešama pastāvīga laika meklēšana un ievietošana
  • kriptogrāfijas lietojumprogrammas
  • ir nepieciešami indeksēšanas dati

Interesanti raksti...