Хасх Табле

У овом упутству ћете научити шта је хеш табела. Такође ћете наћи радне примере операција хеш табела на Ц, Ц ++, Јава и Питхон.

Табела хеширања је структура података која представља податке у облику парова кључ / вредност . Сваки кључ се пресликава на вредност у хеш табели. Тастери се користе за индексирање вредности / података. Сличан приступ примењује асоцијативни низ.

Подаци су представљени у пару вредности кључева уз помоћ кључева, као што је приказано на доњој слици. Сваки податак је повезан са кључем. Кључ је цео број који упућује на податке.

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 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, увек ћемо добити п-битове нижег реда.

 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

Апликације хеш табела

Хасх табеле се примењују тамо где

  • потребно је стално тражење и уметање времена
  • криптографске апликације
  • подаци о индексирању су потребни

Занимљиви Чланци...