Хеш таблица

В този урок ще научите какво е хеш таблица. Също така ще намерите работни примери за операции с хеш таблици в C, C ++, Java и Python.

Хеш таблицата е структура от данни, която представлява данни под формата на двойки ключ-стойност . Всеки ключ се преобразува в стойност в хеш таблицата. Ключовете се използват за индексиране на стойностите / данните. Подобен подход се прилага от асоциативен масив.

Данните са представени в двойка стойност ключ с помощта на ключове, както е показано на фигурата по-долу. Всяка информация е свързана с ключ. Ключът е цяло число, което сочи към данните.

1. Таблица с директни адреси

Таблицата с директни адреси се използва, когато количеството пространство, използвано от таблицата, не е проблем за програмата. Тук предполагаме, че

  • ключовете са малки цели числа
  • броят на клавишите не е твърде голям и
  • няма две данни с един и същ ключ

Пул от цели числа се приема, наречен вселена U = (0, 1,… ., n-1).
Всеки слот на таблица с директни адреси T(0… n-1)съдържа указател към елемента, който съответства на данните.
Индексът на масива Tе самият ключ, а съдържанието на Tе указател към набора (key, element). Ако тогава няма елемент за ключ, той се оставя като NULL.

Понякога самият ключ са данните.

Псевдокод за операции

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

Ограничения на таблица с директни адреси

  • Стойността на ключа трябва да е малка.
  • Броят на ключовете трябва да е достатъчно малък, така че да не пресича границата на размера на масив.

2. Хеш таблица

В хеш таблица ключовете се обработват, за да се получи нов индекс, който се съпоставя с необходимия елемент. Този процес се нарича хеширане.

Нека h(x)бъде хеш функция и kда е ключ.
h(k)се изчислява и се използва като индекс за елемента.

Ограничения на хеш таблица

  • Ако един и същ индекс се произвежда от хеш функцията за множество ключове, възниква конфликт. Тази ситуация се нарича сблъсък.
    За да се избегне това, се избира подходяща хеш функция. Но е невъзможно да се произведат всички уникални ключове, защото |U|>m. По този начин добрата хеш функция може да не предотврати напълно сблъсъците, но може да намали броя на сблъсъците.

Имаме обаче и други техники за разрешаване на сблъсъка.

Предимства на хеш таблицата пред таблицата с директни адреси:

Основните проблеми с таблицата с директни адреси са размерът на масива и евентуално голямата стойност на ключ. Хеш функцията намалява обхвата на индекса и по този начин се намалява и размерът на масива.
Например, ако k = 9845648451321, тогава h(k) = 11(с помощта на някаква хеш функция). Това помага да се спести загубената памет, като същевременно се предоставя индексът на 9845648451321масива

Разрешаване на сблъсък чрез вериги

При тази техника, ако хеш функцията генерира един и същ индекс за множество елементи, тези елементи се съхраняват в един и същ индекс чрез използване на двойно свързан списък.

Ако jе слотът за множество елементи, той съдържа указател към главата на списъка с елементи. Ако няма елемент, jсъдържа NIL.

Псевдокод за операции

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

Добри хеш функции

Добрата хеш функция има следните характеристики.

  1. Не трябва да генерира ключове, които са твърде големи и пространството в сегмента е малко. Пространството се губи.
  2. Генерираните ключове не трябва да са нито много близки, нито твърде далеч.
  3. Сблъсъкът трябва да се сведе до минимум, доколкото е възможно.

Някои от методите, използвани за хеширане, са:

Метод на разделяне

Ако kе ключ и mе размерът на хеш таблицата, хеш функцията h()се изчислява като:

h(k) = k mod m

Например, ако размерът на хеш таблица е 10и k = 112след това h(k) = 112мод 10 = 2. Стойността на mне трябва да бъде правомощията на 2. Това е така, защото правомощията на 2в двоичен формат са 10, 100, 1000,… . Когато намерим k mod m, винаги ще получим p-бита от по-нисък ред.

 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,

  • c1и са положителни помощни константи,c2
  • i = (0, 1,… .)

Двойно хеширане

Ако възникне сблъсък след прилагане на хеш функция h(k), тогава се изчислява друга хеш функция за намиране на следващия слот.
h(k, i) = (h1(k) + ih2(k)) mod m

Приложения за хеш таблици

Хеш таблиците се прилагат където

  • изисква се постоянно търсене и вмъкване на време
  • криптографски приложения
  • необходими са данни за индексиране

Интересни статии...