Хеш-таблиця

У цьому підручнику ви дізнаєтеся, що таке хеш-таблиця. Крім того, ви знайдете робочі приклади операцій хеш-таблиць на мовах 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) = 112mod 10 = 2. Значення mне повинно бути повноваженнями 2. Це тому, що повноваження 2в двійковому форматі є 10, 100, 1000,… . Коли ми знайдемо k mod m, ми завжди отримаємо р-біти нижчого порядку.

 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

Додатки хеш-таблиць

Хеш-таблиці реалізовані де

  • необхідний постійний пошук і вставка часу
  • криптографічні додатки
  • необхідні дані індексації

Цікаві статті...

Рекомендуємо