Introducere în hashing

Hashing-ul este conceput pentru a rezolva problema necesității de a găsi sau stoca eficient un articol într-o colecție.

De exemplu, dacă avem o listă de 10.000 de cuvinte în limba engleză și dorim să verificăm dacă un anumit cuvânt este în listă, ar fi ineficient să comparăm succesiv cuvântul cu toate cele 10.000 de articole până găsim o potrivire. Chiar dacă lista de cuvinte este sortată lexicografic, ca într-un dicționar, veți avea nevoie de ceva timp pentru a găsi cuvântul pe care îl căutați.

Hashing este o tehnică pentru a face lucrurile mai eficiente prin restrângerea eficientă a căutării de la început.

Ce este hashing?

Hashing înseamnă utilizarea unei funcții sau a unui algoritm pentru a mapa datele obiectelor la o valoare întreagă reprezentativă.

Acest așa-numit cod hash (sau pur și simplu hash) poate fi apoi folosit ca o modalitate de a restrânge căutarea atunci când căutăm elementul pe hartă.

În general, aceste coduri hash sunt utilizate pentru a genera un index, la care este stocată valoarea.

Cum funcționează hashing

În tabelele hash, stocați date în forme de perechi de chei și valori. Cheia, care este utilizată pentru a identifica datele, este dată ca intrare în funcția de hash. Codul hash, care este un număr întreg, este apoi mapat la dimensiunea fixă ​​pe care o avem.

Tabelele Hash trebuie să accepte 3 funcții.

  • inserare (cheie, valoare)
  • obține (cheie)
  • șterge (cheie)

Numai ca un exemplu care să ne ajute să înțelegem conceptul, să presupunem că dorim să mapăm o listă de chei de șiruri cu valori de șiruri (de exemplu, să mapăm o listă de țări la capitalele lor).

Deci, să presupunem că vrem să stocăm datele în tabel pe hartă.

Ce este Hashing Cum functioneaza codurile Hash cu

Și să presupunem că funcția noastră hash este de a lua pur și simplu lungimea șirului.

Pentru simplitate, vom avea două tablouri: una pentru cheile noastre și una pentru valori.
Deci, pentru a pune un element în tabelul hash, îi calculăm codul hash (în acest caz, numără pur și simplu numărul de caractere), apoi punem cheia și valoarea în matrice la indexul corespunzător.

De exemplu, Cuba are un cod hash (lungime) de 4. Deci, stocăm Cuba în poziția a 4-a în matricea de taste, iar Havana în al patrulea indice al matricei de valori etc. Și ajungem cu următoarele:

1611883205 102 Ce este Hashing Cum functioneaza codurile Hash cu

Acum, în acest exemplu specific lucrurile funcționează destul de bine. Matricea noastră trebuie să fie suficient de mare pentru a se potrivi cu cel mai lung șir, dar în acest caz sunt doar 11 sloturi.
Pierdem puțin spațiu deoarece, de exemplu, nu există chei cu o literă în datele noastre și nici chei între 8 și 10 litere.

Dar nici în acest caz spațiul irosit nu este atât de rău. Luarea lungimii unui șir este drăguță și rapidă, la fel și procesul de găsire a valorii asociate cu o cheie dată (cu siguranță mai rapidă decât a face până la cinci comparații de șiruri).

Dar, ce facem dacă setul nostru de date are un șir care are mai mult de 11 caractere?
Ce se întâmplă dacă avem un alt cuvânt cu 5 caractere, „India” și încercăm să-l alocăm unui index folosind funcția noastră hash. Deoarece indexul 5 este deja ocupat, trebuie să apelăm la ce să facem cu el. Aceasta se numește coliziune.

Dacă setul nostru de date ar avea un șir cu mii de caractere și veți face o serie de mii de indici pentru a stoca datele, ar rezulta o irosire de spațiu. Dacă tastele noastre ar fi cuvinte aleatorii din limba engleză, unde există atât de multe cuvinte cu aceeași lungime, utilizarea lungimii ca funcție de hash ar fi destul de inutilă.

Manipularea coliziunilor

Două metode de bază sunt utilizate pentru a gestiona coliziunile.

  1. Înlănțuire separată
  2. Deschideți adresarea

Înlănțuire separată

Gestionarea coliziunilor Hash prin înlănțuire separată, folosește o structură de date suplimentară, listă preferabil legată pentru alocare dinamică, în cupe. În exemplul nostru, când adăugăm India la setul de date, acesta este atașat la lista legată stocată la indexul 5, atunci tabelul nostru ar arăta astfel.

1611883205 936 Ce este Hashing Cum functioneaza codurile Hash cu

Pentru a găsi un articol, mergem mai întâi la cupă și apoi comparăm tastele. Aceasta este o metodă populară și, dacă se utilizează o listă de linkuri, hash-ul nu se umple niciodată. Costul pentru get(k) este în medie O(n) unde n este numărul de taste din cupă, numărul total de taste este N.

Problema legării separate este că structura datelor poate crește fără limite.

Deschideți adresarea

Adresarea deschisă nu introduce nicio nouă structură de date. Dacă apare o coliziune, atunci căutăm disponibilitatea în următorul loc generat de un algoritm. Adresarea deschisă este în general utilizată acolo unde spațiul de stocare este restricționat, adică procesoare încorporate. Adresarea deschisă nu este neapărat mai rapidă decât înlănțuirea separată.

Metode pentru adresarea deschisă

Cum să utilizați hashing în codul dvs.

Piton

   # Few languages like Python, Ruby come with an in-built hashing support.
   # Declaration
    my_hash_table = {}
    my_hash_table = dict()

   # Insertion
    my_hash_table[key] = value

   # Look up
    value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2
    value = my_hash_table[key] # throws a ValueError exception if the key is not present

    # Deletion
    del my_hash_table[key] # throws a ValueError exception if the key is not present

    # Getting all keys and values stored in the dictionary
    keys = my_hash_table.keys()
    values = my_hash_table.values()
: rachetă:

Rulați Codul

Java

    // Java doesn't include hashing by default, you have to import it from java.util library
    // Importing hashmaps
    import java.util.HashMap;

   // Declaration
    HashMap<Integer, Integer> myHashTable = new HashMap<Integer, Integer>(); // declares an empty map.

   // Insertion
    myHashTable.put(key, value);

   // Deletion
    myHashtable.remove(key);

    // Look up
    myHashTable.get(key); // returns null if the key K is not present
    myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key

    // Number of key, value pairs in the hash table
    myHashTable.size();
: rachetă:

Rulați Codul

Mai multe informații despre hashing

  • Ghidul fără cod pentru tabelele de hash și hash
  • Cum se implementează un tabel hash simplu în JavaScript
  • Tabelele Hash explicate