Una guida alla tecnica di piegatura in Java

1. Introduzione

In questo tutorial, consideriamo le tecniche di hashing utilizzate in varie strutture di dati che forniscono un accesso costante nel tempo ai loro elementi.

Discutiamo più in dettaglio la cosiddetta tecnica di piegatura e diamo una breve introduzione alle tecniche di metà quadrato e binning.

2. Panoramica

Quando scegliamo strutture di dati per l'archiviazione di oggetti, una delle considerazioni è se dobbiamo accedervi rapidamente.

Il pacchetto di utilità Java ci offre molte strutture di dati per memorizzare i nostri oggetti. Per ulteriori informazioni sulle strutture dei dati, fare riferimento alla nostra pagina di compilazione delle raccolte Java che contiene guide su molte di esse.

Come sappiamo, alcune di queste strutture dati ci consentono di recuperare i loro elementi in tempo costante, indipendentemente dal numero di elementi che contengono.

Probabilmente, il più semplice è l'array. In effetti, accediamo agli elementi dell'array in base al loro indice. Il tempo di accesso, naturalmente, non dipende dalle dimensioni dell'array. In effetti, dietro le quinte, molte strutture dati utilizzano pesantemente gli array.

Il problema è che gli indici degli array devono essere numerici, mentre spesso preferiamo manipolare queste strutture di dati con oggetti.

Per risolvere questo problema, molte strutture di dati tentano di assegnare un valore numerico che può fungere da indice di matrice agli oggetti. Chiamiamo questo valore un valore hash o semplicemente un hash .

3. Hashing

L'hashing è una trasformazione di un oggetto in un valore numerico . Le funzioni che eseguono queste trasformazioni sono chiamate funzioni hash .

Per semplicità, consideriamo le funzioni hash che trasformano le stringhe in indici di array, cioè in interi dall'intervallo [0, N] con un N finito .

Naturalmente, una funzione hash viene applicata a un'ampia varietà di stringhe . Pertanto le sue proprietà "globali" diventano importanti.

Sfortunatamente, non è possibile che una funzione hash trasformi sempre stringhe diverse in numeri diversi .

Possiamo convincerci abbastanza facilmente che il numero di stringhe è molto più grande del numero di interi in qualsiasi intervallo [0, N] . Pertanto, è inevitabile che ci sia una coppia di stringhe non uguali per le quali una funzione hash produce valori uguali. Questo fenomeno è chiamato collisione .

Non ci immergeremo nei dettagli ingegneristici dietro le funzioni hash, ma è chiaro che una buona funzione hash dovrebbe cercare di mappare in modo uniforme le stringhe su cui è definita in numeri.

Un altro ovvio requisito è che una buona funzione hash sia veloce. Se è necessario troppo tempo per calcolare un valore hash, non possiamo accedere rapidamente agli elementi.

In questo tutorial, consideriamo una delle tecniche che cercano di rendere uniforme la mappatura mantenendola veloce.

4. Tecnica di piegatura

Il nostro obiettivo è trovare una funzione che trasformi le stringhe in indici di array. Solo per illustrare l'idea, supponiamo di volere che questo array abbia la capacità di 105 elementi e usiamo il linguaggio Java per stringhe come esempio.

4.1. Descrizione

Cominciamo convertendo i caratteri della stringa in numeri. ASCII è un buon candidato per questa operazione:

Ora, disponiamo i numeri che abbiamo appena ottenuto in gruppi di una certa dimensione. Generalmente, scegliamo il valore della dimensione del gruppo in base alla dimensione del nostro array che è 105. Poiché i numeri, in cui abbiamo trasformato i caratteri, contengono da due a tre cifre, senza perdita di generalità, possiamo impostare la dimensione del gruppo su Due:

Il passaggio successivo consiste nel concatenare i numeri in ciascun gruppo come se fossero stringhe e trovare la loro somma:

Ora dobbiamo fare il passaggio finale. Controlliamo se il numero 348933 può servire come indice del nostro array di dimensione 105. Naturalmente, supera il valore massimo consentito 99999. Possiamo facilmente superare questo problema applicando l'operatore modulo per trovare il risultato finale:

348933 % 10000 = 48933

4.2. Osservazioni finali

Vediamo che l'algoritmo non include operazioni che richiedono tempo e quindi è abbastanza veloce. Ogni carattere della stringa di input contribuisce al risultato finale. Questo fatto aiuta sicuramente a ridurre le collisioni, ma non a evitarle completamente.

Ad esempio, se volessimo saltare la piegatura e applicare l'operatore modulo direttamente alla stringa di input trasformata in ASCII (ignorando il problema di overflow)

749711897321089711010311797103101 % 100000 = 3101

allora tale funzione hash produrrebbe lo stesso valore per tutte le stringhe che hanno gli stessi ultimi due caratteri della nostra stringa di input: a ge , p age , lar ge e così via.

Dalla descrizione dell'algoritmo, possiamo facilmente vedere che non è esente da collisioni. Ad esempio, l'algoritmo produce lo stesso valore hash per il linguaggio Java e le stringhe del linguaggio vaJa .

5. Altre tecniche

La tecnica di piegatura è abbastanza comune, ma non l'unica. A volte, possono essere utili anche le tecniche di binning o mid-square .

Illustriamo la loro idea non usando stringhe, ma numeri (supponiamo di aver già in qualche modo trasformato le stringhe in numeri). Non discuteremo dei loro vantaggi e punti deboli, ma potresti farti un'opinione dopo aver visto gli algoritmi.

5.1. Tecnica di binning

Supponiamo di avere 100 numeri interi e vogliamo che la nostra funzione hash li associ a un array di 10 elementi. Quindi possiamo semplicemente organizzare quei 100 numeri interi in dieci gruppi in modo tale che i primi dieci interi finiscano nel primo bin, i secondi dieci interi finiscano nel secondo bin, ecc .:

5.2. Tecnica del quadrato medio

Questo algoritmo è stato proposto da John von Neumann e ci permette di generare numeri pseudo-casuali a partire da un dato numero.

Illustriamolo con un esempio concreto. Supponiamo di avere un numero di quattro cifre 1111 . Secondo l'algoritmo, lo quadriamo ottenendo 1234321 . Ora estraiamo quattro cifre dal centro, ad esempio 2343 . L'algoritmo ci consente di ripetere questo processo fino a quando non siamo soddisfatti del risultato.

6. Conclusione

In questo tutorial, abbiamo considerato diverse tecniche di hashing. Abbiamo descritto in dettaglio la tecnica di piegatura e fornito una descrizione rapida di come è possibile ottenere binning e mid-square.

Come sempre, possiamo trovare gli snippet di codice corrispondenti nel nostro repository GitHub.