Spiegazione sull'hash e sul suo utilizzo per la compressione dei dati

Question

Sto affrontando un'applicazione che utilizza l'hashing, ma non riesco ancora a capire come funziona. Ecco il mio problema, l'hashing è usato per generare un certo indice, e con quegli indici accedo a diverse tabelle, e dopo aggiungo il valore di ogni tabella che ottengo usando gli indici e con ciò ottengo il mio valore finale. Questo viene fatto per ridurre i requisiti di memoria. L'input per la funzione di hashing sta eseguendo l'XOR tra un numero costante casuale e alcuni parametri dell'applicazione.

È una tipica applicazione di hashing ?. La cosa che non capisco è come l'utilizzo dell'hash sia in grado di ridurre i requisiti di memoria? Qualcuno può chiarire questo ?.

Grazie

Answer 1

L'hashing da solo non ha nulla a che fare con la memoria.

A cosa serve spesso è una tabella hash. Gli hashtable funzionano calcolando l ' hash di ciò di cui stai digitando, che viene quindi utilizzato come indice in una struttura di dati.

L'hash consente di ridurre la chiave (stringa, ecc.) in un valore più compatto come un numero intero o un insieme di bit.

Potrebbe essere il risparmio di memoria a cui ti riferisci, riducendo una chiave grande a un intero semplice.

Nota, tuttavia, che gli hash non sono unici! Un buon algoritmo di hashing minimizza le collisioni ma non è destinato a ridurlo a un valore univoco - non è possibile farlo (ad esempio, se l'hash genera un numero intero a 32 bit, l'hash avrebbe solo 2 ^ 32 valori unici).

Answer 2

È un filtro di fioritura di cui stai parlando? Questo utilizza le funzioni hash per ottenere un modo efficiente in termini di spazio per testare l'appartenenza a un set. In tal caso, consulta il link per una spiegazione.

Answer 3

La maggior parte delle buone implementazioni di hash sono inefficienti di memoria, altrimenti ci sarebbero più computer coinvolti - e questo perderebbe esattamente il punto di hashing.

Le implementazioni di hash sono utilizzate per l'efficienza di elaborazione, in quanto forniscono un tempo di esecuzione costante per operazioni come l'inserimento, la rimozione e il recupero.

Puoi pensare alla qualità dell'hash in modo tale che tutti i tuoi dati, indipendentemente dal tipo e dalle dimensioni, siano sempre rappresentati in un unico modulo a lunghezza fissa.

Answer 4

Questo potrebbe essere spiegato se l'hashing non è fatto per costruire una vera tabella hash, ma è solo per creare un indice in una tabella di blocchi stringa / memoria. Se avessi la stessa stringa (o sequenza di memoria) 20 volte nei tuoi dati e poi hai sostituito tutte le 20 istanze di quella stringa con solo il suo indice hash / table, potresti ottenere la compressione dei dati in quel modo. Se esiste una catena di collisioni effettiva contenuta in quella tabella per ciascun valore di hash, tuttavia, ciò che ho appena descritto non è quello che sta succedendo; in tal caso, il motivo dell'hash sarebbe molto probabilmente quello di accelerare l'esecuzione (fornendo un rapido accesso ai valori memorizzati), piuttosto che la compressione.