Quando una tabella hash di uso generale presuppone che l'uguaglianza hash implichi l'uguaglianza logica?

Question

Quando una tabella hash di uso generale presuppone che l'uguaglianza hash implichi l'uguaglianza logica?

#1 da (6 voti)

3

Per una tabella hash generica che mira sia alle alte prestazioni sia alla correttezza, quando, se mai, ha senso presumere che l'uguaglianza hash implichi l'uguaglianza logica?

Per stabilire alcune regole di base per la domanda, supponiamo che tutti gli input siano non dannosi o che venga utilizzata una funzione hash di qualità crittografica. In altre parole, le collisioni di hash si verificano solo per caso o non possono essere generate intenzionalmente intenzionalmente (come meglio è noto pubblicamente). Tuttavia, non fare alcuna ipotesi sul numero di input di bit o sul numero di output di bit. Supponiamo anche che tutte le entità logicamente uguali abbiano uguali hash (cioè ignori la possibilità di un operatore di uguaglianza con un comportamento insolito).

In base a diverse fonti Internet tra cui la rete stack, la possibilità di una collisione hash a 256 bit è così piccola che può essere considerata impossibile . In particolare, per la famiglia SHA, non esiste una singola collisione nota . Tuttavia, le principali implementazioni di hash table che ho familiarità con do controllano l'uguaglianza logica. Si tratta di una scelta progettuale ragionevole o si rivolge a una paura irrazionale? Se la risposta è più sottile, quali fattori influenzano la risposta? (ad esempio numero di bit di input, funzione di hash utilizzata, contesto del programma?)

Le implementazioni a me più familiari e interessate sono il C ++ (libstdc ++ di GNU e libc ++ di LLVM) e Python. Se gli hash a 64 bit imposti nella libreria standard C ++ influenzano la risposta, ti preghiamo di spiegarci.

c++ c++11 hashing hashtable

posta Praxeolitic 08.10.2016 - 10:15

fonte

1 risposta

Leggi altre domande sui tag c++ c++11 hashing hashtable

Quanti tipi di polimorfismo esistono nel linguaggio Python? Usando il modello attore, come si può programmare una parte concomitante (sezione critica) del codice come pepite autonome?

score 6 · Accepted Answer

Nelle tabelle hash (assumendo un singolo tipo di chiave fissa per semplicità), distinguiamo "la funzione hash", che rimane invariata per tutta la durata della tabella e spesso anche attraverso le tabelle, dalla funzione che mappa l'hash (cioè , l'output di "la funzione di hash") in una posizione / bucket nella tabella. Quest'ultima funzione dipende dall'esatta capacità della tabella hash, che cambia nel tempo. È praticamente sempre semplice come hash mod table_capacity , ma questo non ha importanza per i nostri scopi.

Ora, anche se nella tua tabella hash usi una funzione di hash a 256 bit (che sarebbe abbastanza dispendiosa), non ti aiuta con le collisioni, perché le collisioni che contano su una tabella hash sono due chiavi mappate a lo stesso bucket , non due chiavi con lo stesso hash pre-bucket-mapping. Ovviamente, una collisione hash implica una collisione con una benna, ma quando c'è un grande divario tra la dimensione della tabella e la dimensione dell'hash, le probabilità di due hash diversi mappare sullo stesso bucket sono abbastanza buone.

Quindi, per avere la resistenza di collisione di una funzione di hash a 256 bit riportata su una tabella hash, la tabella hash avrebbe bisogno di 2 bucket ²⁵⁶. Definirlo completamente impraticabile sarebbe un contendente per l'understatement dell'anno.

Quindi non sarai in grado di sfiorare la risoluzione delle collisioni, una delle principali fonti di complessità e lentezza delle tabelle hash (sia perché troppo complesse per essere efficienti o troppo semplicistiche per essere efficaci). È ancora possibile memorizzare l'intero hash e confrontarlo invece del confronto logico delle chiavi. Ma questo ha diversi aspetti negativi:

In molti casi d'uso, le chiavi sono piccole, significativamente più piccole di 256 bit = 32 byte. Quindi anche il confronto stesso potrebbe non essere più veloce (supponendo che il confronto logico si riduca a qualcosa di altrettanto efficace del confronto di hash, che è vero in molti casi importanti).
Indipendentemente dalla dimensione della chiave, 32 byte di hash per bucket sono molti da memorizzare. Nelle architetture dei computer di oggi, più piccolo è più veloce (e in modo molto significativo) a causa dell'elevata latenza della memoria e del conseguente utilizzo di cache veloci ma molto piccole.
Non dimentichiamo il costo del calcolo dell'hash. Mentre i moderni hash crittografici sono abbastanza veloci in termini assoluti, gli hash insicuri possono essere anche più veloci e c'è una corsa agli armamenti continua per scrivere funzioni hash sempre più veloci che sono ancora adeguate in termini di probabilità di collisione. E devi eseguire l'hash almeno una volta alla ogni ricerca.

In breve, mi aspetto che questa decisione di progettazione sia più lenta in molti casi d'uso comuni di un hash più breve e insicuro, e inoltre non rimuoverà alcuna delle complessità e altre decisioni di progettazione in un implementazione della tabella hash. È un'idea interessante ma non sembra fattibile per una tabella hash generica.