Maišos lentelė

Šioje pamokoje sužinosite, kas yra maišos lentelė. Taip pat rasite darbinių maišos lentelės operacijų pavyzdžių C, C ++, Java ir Python.

Maišos lentelė yra duomenų struktūra, vaizduojanti duomenis raktų ir verčių porų pavidalu . Kiekvienas raktas susiejamas su maišos lentelės verte. Raktai naudojami vertėms / duomenims indeksuoti. Panašų metodą taiko ir asociacinis masyvas.

Duomenys pateikiami raktų vertės poroje raktų pagalba, kaip parodyta paveikslėlyje žemiau. Kiekvieni duomenys susieti su raktu. Raktas yra sveikasis skaičius, nurodantis duomenis.

1. Tiesioginė adresų lentelė

Tiesioginio adreso lentelė naudojama, kai lentelėje naudojamas vietos kiekis nekelia problemų. Čia mes manome, kad

  • raktai yra maži sveikieji skaičiai
  • raktų skaičius nėra per didelis ir
  • nėra dviejų duomenų, turinčių tą patį raktą

Sveikų skaičių telkinys vadinamas visata U = (0, 1,… ., n-1).
Kiekviename tiesioginio adreso lentelės lizde T(0… n-1)yra elemento, atitinkančio duomenis, žymeklis.
Masyvo rodyklė Tyra pats raktas, o turinys Tyra rodiklis į rinkinį (key, element). Jei tada nėra rakto elemento, jis paliekamas kaip NULL.

Kartais pats raktas yra duomenys.

Pseudokodas operacijoms

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

Tiesioginio adresų lentelės apribojimai

  • Rakto vertė turėtų būti maža.
  • Raktų skaičius turi būti pakankamai mažas, kad jis neperžengtų masyvo dydžio ribos.

2. Hash lentelė

Maišos lentelėje raktai apdorojami, kad būtų sukurtas naujas indeksas, susietas su reikiamu elementu. Šis procesas vadinamas maišymu.

Leisti h(x)būti maišos funkcija ir kbūti raktas.
h(k)yra apskaičiuojamas ir jis naudojamas kaip elemento indeksas.

Maišos lentelės apribojimai

  • Jei tą patį indeksą sukuria maišos funkcija keliems raktams, kyla konfliktas. Ši situacija vadinama susidūrimu.
    Norėdami to išvengti, pasirenkama tinkama maišos funkcija. Tačiau neįmanoma pagaminti visų unikalių raktų, nes |U|>m. Taigi gera maišos funkcija gali netrukdyti susidūrimams, tačiau gali sumažinti susidūrimų skaičių.

Tačiau mes turime kitų būdų, kaip išspręsti susidūrimą.

Maišos lentelės privalumai, palyginti su tiesioginio adreso lentele:

Pagrindinės tiesioginio adresų lentelės problemos yra masyvo dydis ir galbūt didelė rakto vertė. Maišos funkcija sumažina indekso diapazoną, taigi masyvo dydis taip pat sumažėja.
Pavyzdžiui, jei k = 9845648451321, tada h(k) = 11(naudojant kokią nors maišos funkciją). Tai padeda taupyti iššvaistytą atmintį, kartu pateikiant 9845648451321masyvo indeksą

Susidūrimo sprendimas grandinėmis

Taikant šią techniką, jei maišos funkcija sukuria tą patį indeksą keliems elementams, šie elementai saugomi tame pačiame indekse, naudojant dvigubai susietą sąrašą.

Jei jyra kelių elementų sritis, joje yra rodyklė į elementų sąrašo galvutę. Jei nėra elemento, jyra NIL.

Pseudokodas operacijoms

 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“ ir „C ++“ diegimas

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

Geros maišos funkcijos

Gera maišos funkcija turi šias savybes.

  1. Tai neturėtų generuoti per didelių raktų, o talpa yra maža. Vieta švaistoma.
  2. Sugeneruoti raktai neturėtų būti nei labai arti, nei per toli.
  3. Susidūrimas turi būti kuo labiau sumažintas.

Kai kurie maišos metodai yra šie:

Dalijimo metodas

Jei kyra raktas ir mmaišos lentelės dydis, maišos funkcija h()apskaičiuojama taip:

h(k) = k mod m

Pavyzdžiui, jei maišos lentelės dydis yra 10, k = 112tada h(k) = 112mod 10 = 2. Vertė mneturi būti 2. Taip yra todėl, kad 2dvejetainio formato galios yra 10, 100, 1000,… . Kai rasime k mod m, visada gausime žemesnės eilės 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,

  • c1ir yra teigiamos pagalbinės konstantos,c2
  • i = (0, 1,… .)

Dvigubas maišymas

Jei susidūrus įvyksta pritaikius maišos funkciją h(k), apskaičiuojama kita maišos funkcija kitam lizdui surasti.
h(k, i) = (h1(k) + ih2(k)) mod m

„Hash Table“ programos

Maišos lentelės yra įdiegtos ten, kur

  • reikia nuolatinio laiko paieškos ir įterpimo
  • kriptografijos programos
  • reikia indeksuoti duomenis

Įdomios straipsniai...