Mappa hash senza controllo collisione

Sì, è possibile farlo. Cerca i dettagli di ZFS per un sistema distribuito di qualità di produzione che utilizza questa idea. In ZFS, qualsiasi dato che deve essere memorizzato viene sottoposto a hash con un hash crittografico a 256 bit e, se corrisponde a qualsiasi dato esistente noto nel sistema , si presume che siano gli stessi dati e due blocchi su disco sono considerati candidati alla fusione . Ciò significa che, se si dispone di RAM sufficiente (o, più realisticamente, di spazio SSD veloce) per mantenere una tabella di gran parte dei blocchi a cui si accede recentemente, è possibile memorizzare copie duplicate di file senza richiedere ulteriore spazio per i duplicati. La stessa funzione viene anche utilizzata per fornire istantanee per il sistema.

Sebbene sia utile per i file system, probabilmente non è così utile per l'archiviazione in memoria, tuttavia, poiché è davvero un buon approccio per oggetti molto grandi che sono costosi da accedere (ad esempio a causa della latenza di accesso al disco) ). Per oggetti più piccoli con accesso rapido, è più facile calcolare un piccolo hash e controllarli in dettaglio quando si verifica una collisione hash, perché le funzioni hash per tale operazione eseguono molto più velocemente e i risultati richiedono meno memoria per memorizza gli hash crittografici di grandi dimensioni necessari per rendere affidabile ZFS.

Hai ragione, una funzione di hash che un così grande spazio di hash vedrà poche collisioni. Ma una tabella hash utilizza una funzione hash per uno scopo specifico: mappare le voci della tabella hash in un contenitore specifico. Questo di solito viene fatto usando un'operazione di modulo, cioè bucket = hash(key) % n_buckets . Per una tabella power-of-two, questo può essere fatto in modo molto efficiente mascherando i bit più alti dell'hash.

Quindi una tabella hash non si preoccupa tanto delle collisioni hash quanto delle collisioni con benna. O visto in modo diverso, non utilizza direttamente alcune funzioni di hash ma quella funzione di hash modulo il numero di bucket.

Per questo motivo, una funzione di hash con un grande spazio di hash è inutile, quasi tutti i bit verranno mascherati. Per una tabella hash con 256 bucket ho solo bisogno di 8 bit, più sarebbe uno spreco.

Come possono le tabelle hash essere sicure se hanno solo pochi bit? Soprattutto per le funzioni di hash veloci (non crittografiche), è possibile precalcolare le collisioni. Se un utente malintenzionato trasmette questi elementi in collisione in una tabella hash (ad esempio, i parametri della stringa di query in un'applicazione Web) verranno mappati allo stesso segmento, degradando così la ricerca O (1) di una tabella hash a quella di un elenco collegato: O (n). Questo di solito viene impedito parametrizzando la funzione di hash con un sale per processo o anche per tabella. Poiché il sale è sconosciuto all'attaccante, non possono precompilare alcuna collusione.

Con l'algoritmo di hashing giusto, la tua idea potrebbe funzionare, almeno in alcuni scenari. Per applicazioni specializzate, potrebbe avere un prezioso vantaggio in termini di prestazioni. Ma la qualità dell'algoritmo di hash è cruciale. Altre risposte e commenti hanno menzionato software come Git e ZFS che assumono uguale hash implicano oggetti uguali. Possono farla franca perché fanno il loro hashing con un algoritmo noto.

Questo non è il caso di una collezione per scopi generici. In Java, ad esempio, ogni classe fornisce il proprio metodo di hashing e HashMap delega l'hashing agli oggetti che memorizza. È perfettamente legale per una classe utilizzare un algoritmo di hashing errato che potrebbe produrre collisioni. In effetti, è perfettamente legale restituire lo stesso codice hash per l'oggetto ogni . Le prestazioni delle raccolte basate su hash ne risentiranno, ma produrranno comunque risultati corretti. La tua mappa non lo farebbe.

L'immagine che fai riferimento è un esempio del perché credo fermamente che la maggior parte degli appassionati di criptovaluta non capiscano davvero la tecnologia sottostante. Un grosso difetto nella sua affermazione è che se un computer quantistico a 256 bit è stato costruito (cosa che molte persone pensano che possano essere fatte nel prossimo futuro), una macchina del genere potrebbe crack il bitcoin 'protezione' crittografico in pochi secondi. In altre parole, la rivendicazione principale nell'immagine è fasulla.

L'altro fattore che questo fattoide non riesce a menzionare è che non è semplicemente lo spazio intero (2 ^ 256) che è rilevante qui, ma è anche la distribuzione degli hash attraverso lo spazio. Ecco un esempio di una funzione hash a 256 bit:

byte[] hash(Object... data){
   byte[] hash = new byte[32];

   for (int i = 0; i < 32; i++) hash[i] = (byte)0xFF;

   return hash;
}

Ora, chiediti, è davvero 'impossibile' che un hash a 256 bit entri in collisione con un altro? Ovviamente, questa funzione hash fa schifo. Ma la storia ci ha dimostrato che nel tempo l'hash funziona sono stati pensati per essere sicuri risultano non essere così . È importante capire che non è solo che gli spazi di queste funzioni di hash non erano abbastanza grandi, è che gli algoritmi erano deboli.

In teoria, questo schema è possibile ma può essere garantito che funzioni solo se stai utilizzando una funzione di hash perfetta e i tuoi input su quella funzione non superano mai i 256 bit.