Tabulka hash

V tomto kurzu se dozvíte, co je hash tabulka. Také najdete pracovní příklady operací hash tabulky v C, C ++, Java a Python.

Hash tabulka je datová struktura, která představuje data ve formě párů klíč – hodnota . Každý klíč je namapován na hodnotu v hašovací tabulce. Klíče se používají k indexování hodnot / dat. Podobný přístup uplatňuje asociativní pole.

Data jsou reprezentována v páru klíč-hodnota pomocí kláves, jak je znázorněno na obrázku níže. Ke každému datu je přiřazen klíč. Klíč je celé číslo, které ukazuje na data.

1. Tabulka přímých adres

Tabulka s přímou adresou se používá, když velikost místa, které tabulka využívá, není pro program problémem. Tady to předpokládáme

  • klíče jsou malá celá čísla
  • počet klíčů není příliš velký a
  • žádná dvě data nemají stejný klíč

Skupina celých čísel se nazývá vesmír U = (0, 1,… ., n-1).
Každý slot tabulky přímých adres T(0… n-1)obsahuje ukazatel na prvek, který odpovídá datům.
Index pole Tje samotný klíč a obsah Tje ukazatelem na sadu (key, element). Pokud pro klíč neexistuje žádný prvek, je ponechán jako NULL.

Klíčem jsou někdy data.

Pseudokód pro operace

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

Omezení tabulky přímých adres

  • Hodnota klíče by měla být malá.
  • Počet klíčů musí být dostatečně malý, aby nepřekročil limit velikosti pole.

2. Tabulka hash

V hash tabulce jsou klíče zpracovány tak, aby vytvářely nový index, který se mapuje na požadovaný prvek. Tento proces se nazývá hašování.

Nechť h(x)je hashovací funkce a kje klíčem.
h(k)se vypočítá a použije se jako index prvku.

Omezení tabulky hash

  • Pokud je stejný index vytvořen hashovací funkcí pro více klíčů, dojde ke konfliktu. Tato situace se nazývá kolize.
    Aby se tomu zabránilo, je zvolena vhodná hashovací funkce. Je však nemožné vyrobit všechny jedinečné klíče, protože |U|>m. Dobrá hashovací funkce tedy nemusí kolizím úplně zabránit, ale může snížit počet kolizí.

Máme však jiné techniky, jak vyřešit kolizi.

Výhody hash tabulky oproti tabulce přímých adres:

Hlavní problémy s tabulkou přímých adres jsou velikost pole a možná velká hodnota klíče. Funkce hash zmenšuje rozsah indexu a tím se zmenšuje také velikost pole.
Například If k = 9845648451321, then h(k) = 11(using some hash function). To pomáhá při ukládání zbytečné paměti při poskytování indexu 9845648451321do pole

Řešení kolize řetězením

V této technice, pokud funkce hash produkuje stejný index pro více prvků, jsou tyto prvky uloženy ve stejném indexu pomocí dvojnásobně propojeného seznamu.

Pokud jje slot pro více prvků, obsahuje ukazatel na záhlaví seznamu prvků. Pokud není přítomen žádný prvek, jobsahuje NIL.

Pseudokód pro operace

 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

Implementace Pythonu, Javy, C a 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(); )

Dobré hashovací funkce

Dobrá hashovací funkce má následující vlastnosti.

  1. Nemělo by generovat příliš velké klíče a malý prostor v kbelíku. Prostor je zbytečný.
  2. Vygenerované klíče by neměly být ani příliš blízko, ani příliš daleko v dosahu.
  3. Kolize musí být co nejvíce minimalizována.

Některé z metod používaných k hašování jsou:

Metoda dělení

Pokud kje klíč a mje velikost hash tabulky, hash funkce h()se počítá jako:

h(k) = k mod m

Například pokud je velikost hash tabulky 10a k = 112poté h(k) = 112mod 10 = 2. Hodnota mnesmí být pravomocí 2. Důvodem je, že pravomoci 2v binárním formátu jsou 10, 100, 1000,… . Když zjistíme k mod m, vždy dostaneme p-bity nižšího řádu.

 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,

  • c1a jsou kladné pomocné konstanty,c2
  • i = (0, 1,… .)

Dvojitý hash

Pokud po použití hashovací funkce dojde ke kolizi h(k), pak se pro nalezení dalšího slotu vypočítá další hashovací funkce.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash tabulky aplikací

Hash tabulky jsou implementovány kde

  • je vyžadováno neustálé vyhledávání a vkládání
  • kryptografické aplikace
  • jsou vyžadována indexovací data

Zajímavé články...