[Algoritmi] Correttezza funzioni hash.
Salve a tutti, vorrei porvi un genere di esercizio che mi sta mettendo in difficoltà:
Si consideri l'universo U delle date di nascita. Si supponga che una data di nascita sia data dalla terna (i,j,k), con i appartenente a {1...31}, j a {1...12} e k a {30...95}. Determinare se le seguenti funzioni di hashing h: U->{0...999} sono buone.
1) \(\displaystyle h_1(i,j,k)= (i+j+k)mod(1000) \);
2) \(\displaystyle h_2(i,j,k)= (i*10^4+j*10^2+k)mod(1000) \);
3) suggerire una buona funziona diversa dalle prime due.
Cioè sostanzialmente si chiede se un tale funzione vada a coprire uniformemente la tabella che in questo caso ha 1000 posizioni.
La mia risoluzione è questa ma non sono sicuro della correttezza:
1) la prima non è buona perchè la somma massima che si può ottenere è 31+12+95 che è <1000 quindi la gran parte delle posizioni in tabella non si utilizzano;
2) la seconda mi sembra che non si vada mai ad occupare la posizione in tabella numero 0. Infatti (i*10^4+j*10^2)mod(1000) sarà sempre 0, ma se sommato a k darà sempre una posizione diversa da 0 perchè k non è mai 0;
3)in che modo posso creare una funzione buona?
Si consideri l'universo U delle date di nascita. Si supponga che una data di nascita sia data dalla terna (i,j,k), con i appartenente a {1...31}, j a {1...12} e k a {30...95}. Determinare se le seguenti funzioni di hashing h: U->{0...999} sono buone.
1) \(\displaystyle h_1(i,j,k)= (i+j+k)mod(1000) \);
2) \(\displaystyle h_2(i,j,k)= (i*10^4+j*10^2+k)mod(1000) \);
3) suggerire una buona funziona diversa dalle prime due.
Cioè sostanzialmente si chiede se un tale funzione vada a coprire uniformemente la tabella che in questo caso ha 1000 posizioni.
La mia risoluzione è questa ma non sono sicuro della correttezza:
1) la prima non è buona perchè la somma massima che si può ottenere è 31+12+95 che è <1000 quindi la gran parte delle posizioni in tabella non si utilizzano;
2) la seconda mi sembra che non si vada mai ad occupare la posizione in tabella numero 0. Infatti (i*10^4+j*10^2)mod(1000) sarà sempre 0, ma se sommato a k darà sempre una posizione diversa da 0 perchè k non è mai 0;
3)in che modo posso creare una funzione buona?
Risposte
Ci sono parecchi numeri nel secondo caso che non sono ottenibili dalla funzione di hash. Di fatto abbiamo che il risultato non dipende da \(i\) e che quindi i valori ottenibili sono nella forma: \( J \times 100 + k \) dove \( 0 \leq J \leq 9 \) e \(30 \leq k \leq 95 \). Inoltre i valori sono scelti in modo non uniforme (i valori con \(J = 1\) appaiono \(62\) volte mentre gli altri solo \(31\).
Non è in generale possibile ottenere una funzione uniforme tra i tuoi valori e le 1000 posizioni, ma
\[ h_3(i, j, k) = (j-1) + 13 \times \bigl((k-30) + 67 \times (i - 1)\bigr) \mod 1000 \]
è già molto meglio. Dipende comunque sempre da quello che intendiamo con "buona funzione" ovviamente.
Non è in generale possibile ottenere una funzione uniforme tra i tuoi valori e le 1000 posizioni, ma
\[ h_3(i, j, k) = (j-1) + 13 \times \bigl((k-30) + 67 \times (i - 1)\bigr) \mod 1000 \]
è già molto meglio. Dipende comunque sempre da quello che intendiamo con "buona funzione" ovviamente.
"apatriarca":
Ci sono parecchi numeri nel secondo caso che non sono ottenibili dalla funzione di hash. Di fatto abbiamo che il risultato non dipende da \(i\) e che quindi i valori ottenibili sono nella forma: \( J \times 100 + k \) dove \( 0 \leq J \leq 9 \) e \(30 \leq k \leq 95 \). Inoltre i valori sono scelti in modo non uniforme (i valori con \(J = 1\) appaiono \(62\) volte mentre gli altri solo \(31\).
Non è in generale possibile ottenere una funzione uniforme tra i tuoi valori e le 1000 posizioni, ma
\[ h_3(i, j, k) = (j-1) + 13 \times \bigl((k-30) + 67 \times (i - 1)\bigr) \mod 1000 \]
è già molto meglio. Dipende comunque sempre da quello che intendiamo con "buona funzione" ovviamente.
Intanto grazie per la celerità.
Negli esercizi tendiamo a definire "buona funzione" se la tabella viene coperta completamente, trascurando il calcolo delle diverse probabilità delle varie posizioni.
Ma come sei riuscito ad arrivare a quella funzione? Cioè c'è un ragionamento che si può applicare nel momento dell creazione?
Proverei a mettere un altro esercizio per un ultimo confronto:
"Sia U l'insieme di tutti i vettori k di bit di 100 elementi, cioè ogni k è un vettore di dimensione 100 a valori in {0,1}.
Si vuole memorizzare un sottoinsieme di U in una tabella hash T. Si proponga una ragionevole funzione di hash h: U->{0...1023}. Si enuncino le caratteristiche che devono essere soddisfatte dalle funzioni di hash e si dimostri che la funzione proposta le soddisfa."
Ho pensato a una funzione tipo: $(\sum_{k=0}^99 v*11)mod1024$
Ho semplicemente preso i 3 numeri, ho sottratto per il valore minimo e poi fatto in modo che i 3 numeri si comportassero come indici di una matrice multidimensionale. Il principio è abbastanza simile alle cifre di un numero. È generalizzabile a qualsiasi situazione in cui ogni valore è limitato ad un insieme fissato.
Nel secondo caso non mi è chiara la scelta di moltiplicare per 11. Facendo così puoi ottenere solo 100 dei 1024 valori. Il risultato sarà infatti uguale a \(S(v) \times 11 \mod 1024\) dove \(S(v)\) è il numero di bit non nulli nella somma. Un semplice gruppo di funzioni suriettive è dato da mappe che restituiscono il numero la cui rappresentazione binaria è formata da un sottoinsieme di 10 bit del vettore. Anche loro combinazioni potrebbero funzionare abbastanza bene. Dipende molto dal tipo di proprietà a cui si è interessati.
Nel secondo caso non mi è chiara la scelta di moltiplicare per 11. Facendo così puoi ottenere solo 100 dei 1024 valori. Il risultato sarà infatti uguale a \(S(v) \times 11 \mod 1024\) dove \(S(v)\) è il numero di bit non nulli nella somma. Un semplice gruppo di funzioni suriettive è dato da mappe che restituiscono il numero la cui rappresentazione binaria è formata da un sottoinsieme di 10 bit del vettore. Anche loro combinazioni potrebbero funzionare abbastanza bene. Dipende molto dal tipo di proprietà a cui si è interessati.
"apatriarca":
Ho semplicemente preso i 3 numeri, ho sottratto per il valore minimo e poi fatto in modo che i 3 numeri si comportassero come indici di una matrice multidimensionale. Il principio è abbastanza simile alle cifre di un numero. È generalizzabile a qualsiasi situazione in cui ogni valore è limitato ad un insieme fissato.
Nel secondo caso non mi è chiara la scelta di moltiplicare per 11. Facendo così puoi ottenere solo 100 dei 1024 valori. Il risultato sarà infatti uguale a \(S(v) \times 11 \mod 1024\) dove \(S(v)\) è il numero di bit non nulli nella somma. Un semplice gruppo di funzioni suriettive è dato da mappe che restituiscono il numero la cui rappresentazione binaria è formata da un sottoinsieme di 10 bit del vettore. Anche loro combinazioni potrebbero funzionare abbastanza bene. Dipende molto dal tipo di proprietà a cui si è interessati.
In realtà il *11 doveva stare dentro la sommatoria, mi sono dimenticato le parentesi. Ho pensato di moltiplicare per 11 perchè in questo modo tutte le possibili combinazioni avranno somma >1024 e saranno messe in tutte le posizioni della tabella.
Ti ho già spiegato che non è così. Avessi moltiplicato per \(11^i\) sarebbe stato diverso, ma così hai solo 100 valori distinti nell'immagine.
"apatriarca":
Ti ho già spiegato che non è così. Avessi moltiplicato per \(11^i\) sarebbe stato diverso, ma così hai solo 100 valori distinti nell'immagine.
Giusto. In questo caso i quanto dovrebbe valere? Per esempio un numero scelto a random fra 1 e 5 per ogni somma? Perchè elevare 11^k non avrebbe senso.
Capisco di non fare domande intelligenti, ma su questo argomento non ho trovato materiale, quindi sto imparando un po' alla cieca
Perché non dovrebbe avere senso \(11^k\)?
"apatriarca":
Perché non dovrebbe avere senso \(11^k\)?
Perchè la somma del primo elemento farà sempre 0 (k=0) e perchè gli ultimi elementi della sommatoria moltiplicheranno 11^99 o 11^98 quindi numeri troppo grandi per essere elaborati in un tempo costante. Diciamo che magari è corretta, ma è poco efficiente. Poi forse mi sbaglio...
Sbagli perché vale la seguente
\[ a \times b \mod c = (a \mod c) \times (b \mod c) \mod c \]
Hai quindi in particolare che puoi calcolare 11^k in modulo e sarà quindi un numero basso. Quello che mi viene più difficile senza fare calcoli è dire se tale funzione è suriettiva. Nota comunque che le potenze di 11 modulo 1024 sono tutte distinte.
\[ a \times b \mod c = (a \mod c) \times (b \mod c) \mod c \]
Hai quindi in particolare che puoi calcolare 11^k in modulo e sarà quindi un numero basso. Quello che mi viene più difficile senza fare calcoli è dire se tale funzione è suriettiva. Nota comunque che le potenze di 11 modulo 1024 sono tutte distinte.
Quindi per avere un'idea, come la faresti una funzione del genere? Una semplice, che rispetti solo l'uniformità sulla tabella.
Ti ho già fornito diversi esempi. Ci sono diverse proprietà che si possono desiderare da una funzione di hash a seconda dell'utilizzo. Selezionare 10 bit a caso dei 100 è ad esempio suriettiva e ogni valore dell'immagine ha la stessa probabilità di essere scelto. Tuttavia dipende da solo 10 bit dei valori e non è adatta a situazioni in cui i valori di input sono scelti in modo da variare poco tra di loro. Un'altra possibilità è ad esempio di calcolare \( \bigoplus_{i=0}^{10} v[10\,i .. (10\,(i-1)-1)] \) dove \(\oplus\) è l'operazione XOR e \(v[a..b]\) è il numero intero la cui rappresentazione binaria è data da i bit da \(a\) a \(b\) inclusi di \(v\). Anche questa è suriettiva e l'immagine è uniforme, ma dipende da tutti i valori. Un'alternativa simile è quella di usare la somma in modulo invece dello XOR.
Esistono tantissime funzioni possibili e quale è meglio usare dipende molto da quali proprietà si desiderano dalla funzione di hash.
Esistono tantissime funzioni possibili e quale è meglio usare dipende molto da quali proprietà si desiderano dalla funzione di hash.
Ok, grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo