Hashing è una struttura dati fondamentale che archivia e recupera in modo efficiente i dati in modo da consentirne un rapido accesso. Implica la mappatura dei dati su un indice specifico in una tabella hash utilizzando a funzione hash che consente il recupero rapido delle informazioni in base alla relativa chiave. Questo metodo è comunemente usato nei database, C sistemi doching e varie applicazioni di programmazione per ottimizzare le operazioni di ricerca e recupero.

Strutture dati – Hashing

Tabella dei contenuti

• Funzione hash
• Cos'è una collisione di hash?
• Tecniche di risoluzione delle collisioni
• Applicazioni dell'hashing
• Problema semplice sull'hashing
• Problema medio sull'hashing
• Problema difficile sull'hashing

funzione hash per mappare gli elementi di dati su un array di dimensioni fisse chiamato a tabella hash .

modelli di programmazione java

Come funziona:

1. Funzione hash: Fornisci i tuoi elementi di dati nella funzione hash.
2. Codice hash: La funzione hash elabora i dati e fornisce un codice hash univoco.
3. Tabella hash: Il codice hash ti indirizza quindi a una posizione specifica all'interno della tabella hash.

Funzione hash

IL funzione hash è una funzione che richiede a chiave e restituisce un indice dentro tabella hash . L'obiettivo di una funzione hash è distribuire le chiavi in ​​modo uniforme nella tabella hash, riducendo al minimo le collisioni (quando due chiavi sono mappate allo stesso indice).

Le funzioni hash comuni includono:

• Metodo di divisione: Dimensione tabella hash % chiave
• Metodo di moltiplicazione: (Chiave * Costante) % dimensione tabella hash
• Hashing universale: Una famiglia di funzioni hash progettate per ridurre al minimo le collisioni

Cos'è una collisione di hash?

Una collisione di hash si verifica quando due chiavi diverse vengono mappate allo stesso indice in una tabella hash. Ciò può accadere anche con una buona funzione hash, soprattutto se la tabella hash è piena o le chiavi sono simili.

Cause delle collisioni hash:

esempi di alberi binari

• Funzione hash scadente: Una funzione hash che non distribuisce le chiavi in ​​modo uniforme nella tabella hash può portare a più collisioni.
• Fattore di carico elevato: Un fattore di carico elevato (rapporto tra chiavi e dimensione della tabella hash) aumenta la probabilità di collisioni.
• Chiavi simili: Le chiavi simili per valore o struttura hanno maggiori probabilità di entrare in collisione.

Tecniche di risoluzione delle collisioni

Esistono due tipi di tecniche di risoluzione delle collisioni:

1. Indirizzamento aperto:
   • Sondaggio lineare: Cerca uno slot vuoto in sequenza
   • Sondaggio quadratico: Cerca uno slot vuoto utilizzando una funzione quadratica
2. Indirizzamento chiuso:
   • Concatenamento: Memorizza le chiavi in ​​​​collisione in un elenco collegato o in un albero di ricerca binario in ciascun indice
   • Hashing del cuculo: Utilizza più funzioni hash per distribuire le chiavi

Applicazioni dell'hashing

Le tabelle hash vengono utilizzate in un'ampia varietà di applicazioni, tra cui:

• Banche dati: Archiviazione e recupero dei dati in base a chiavi univoche
• Memorizzazione nella cache: Memorizzazione dei dati a cui si accede frequentemente per un recupero più rapido
• Tabelle dei simboli: Mappatura degli identificatori sui loro valori nei linguaggi di programmazione
• Instradamento di rete: Determinazione del percorso migliore per i pacchetti di dati

Cos'è l'hashing?

Mappatura dell'indice (o Hashing banale)

Concatenamento separato per la gestione delle collisioni

Indirizzamento aperto per la gestione delle collisioni

Doppio hashing

Fattore di carico e rehashing

Problema semplice sull'hashing

• Scopri se un array è un sottoinsieme di un altro array
• Unione e intersezione di due liste concatenate
• Dato un array A[] e un numero x, controlla la coppia in A[] con somma come x
• Distanza massima tra due occorrenze dello stesso elemento nell'array
• Contare il numero massimo di punti sulla stessa riga
• Elemento più frequente in un array
• Trova l'unico elemento ripetitivo compreso tra 1 e n-1
• Come verificare se due insiemi dati sono disgiunti?
• Somma non sovrapposta di due insiemi
• Controlla se due array sono uguali o meno
• Trova gli elementi mancanti di un intervallo
• Numero minimo di sottoinsiemi con elementi distinti
• Rimuovere il numero minimo di elementi in modo tale che non esista alcun elemento comune in entrambi gli array
• Trova coppie con una data somma tale che gli elementi della coppia si trovino su righe diverse
• Conta le coppie con la somma data
• Contare quadrupli da quattro array ordinati la cui somma è uguale a un dato valore x
• Ordina gli elementi per frequenza
• Trova tutte le coppie (a, b) in un array tale che a % b = k
• Raggruppa parole con lo stesso set di caratteri
• k-esimo elemento distinto (o non ripetitivo) in un array.

Problema medio sull'hashing

• Trova l'itinerario da un determinato elenco di biglietti
• Trova il numero di dipendenti sotto ogni dipendente
• Sottoarray più lungo con somma divisibile per k
• Trova il sottoarray più grande con somma 0
• Sottosequenza consecutiva crescente più lunga
• Contare elementi distinti in ogni finestra di dimensione k
• Trova il sottoarray con la somma data | Set 2 (gestisce i numeri negativi)
• Implementazione della nostra tabella hash con concatenamento separato in Java
• Implementazione della propria tabella hash con sondaggio lineare con indirizzamento aperto in C++
• Inserzioni minime per formare un palindromo con permutazioni consentite
• Differenza massima possibile di due sottoinsiemi di un array
• Ordinamento utilizzando la banale funzione hash
• Sottoarray più piccolo con k numeri distinti

Problema difficile sull'hashing

• Clona un albero binario con puntatori casuali
• Sottoarray più grande con lo stesso numero di 0 e 1
• Tutte triplette uniche che si sommano a un dato valore
• Query sottostringa palindromo
• Intervallo di query per le frequenze degli elementi dell'array
• Elementi da aggiungere in modo che tutti gli elementi di un intervallo siano presenti nell'array
• Cuckoo Hashing – Caso peggiore O(1) Ricerca!
• Contare i sottoarray con elementi distinti totali uguali all'array originale
• Array massimo da due array dati che mantengono lo stesso ordine
• Trova la somma di tutte le somme di sottoarray univoche per un determinato array.
• La sequenza di Recaman
• Lunghezza della sottosequenza bitonica rigorosa più lunga
• Trova tutte le sottostrutture duplicate
• Trova se esiste un rettangolo nella matrice binaria con gli angoli pari a 1

Link veloci :

• “Problemi pratici” sull’hashing
• Le 20 principali domande per interviste basate sulla tecnica di hashing
• 'Video' sull'hashing