Хеш-таблица

В этом руководстве вы узнаете, что такое хеш-таблица. Также вы найдете рабочие примеры операций с хеш-таблицами на 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, мы всегда будем получать 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

Приложения с хеш-таблицами

Хеш-таблицы реализованы там, где

  • требуется постоянный поиск и вставка
  • криптографические приложения
  • данные индексации требуются

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