La mia comprensione è che le mappe di hash ci permettono di collegare, per esempio, una stringa, in una certa posizione di memoria. Ma se ogni stringa fosse collegata a un posto unico nella memoria, avrebbe bisogno di un enorme blocco di memoria vuota. Non capisco.
Le funzioni di hash vengono utilizzate per convertire l'input (di solito una stringa) in un valore hash di lunghezza fissa (tipicamente) più piccolo "che in genere viene usato in qualche modo come un indice di array per la tabella hash. Idealmente, questo valore dovrebbe essere uniformemente distribuito nell'intero intervallo ed evitare qualsiasi concentrazione evidente / significativa.
A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length.
Sei stato informato per quanto riguarda "la memoria certa posizione". L'uso di tale funzione è di ridurre una grande quantità di dati in un valore molto più piccolo che può essere utilizzato per identificare i dati di grandi dimensioni. Poiché stai riducendo la dimensione dei dati, è probabile che più di un "dato" di input abbia lo stesso valore hash, ovvero ciò che viene chiamato collisione .
Una funzione di hash valida (non molto buona, ma valida ancora) potrebbe essere una che riassume ciascuna delle lettere della stringa con i loro codici ASCII.
Hash e mappa sono due concetti diversi. (E quindi due tag hashing e map :-)).
Il concetto di mappa (in questo contesto) è raccolta di coppie chiave-valore , dove la chiave potrebbe essere qualsiasi cosa e il valore potrebbe essere qualsiasi cosa. Una volta creata una mappa, la mappa dovrebbe essere in grado di recuperare il valore di una determinata chiave. Una semplice mappa potrebbe memorizzare la coppia chiave-valore in un array o in una lista collegata. Una mappa può essere implementata utilizzando qualsiasi tecnica di archiviazione. I più popolari sono gli alberi rosso-nero e Hashing.
L'hashing è conversione di qualcosa in una rappresentazione unica (la maggior parte delle volte il più casuale possibile) che è limitata da un intervallo. L'hashing è unidirezionale, significa che una volta che hai hash A in B non esiste un modo sicuro per ottenere A da B.
Una funzione di hash è una che accetta A come input e restituisce B come output. Due proprietà per le funzioni hash sono importanti.
Ottenere una buona funzione di hash è davvero difficile in quanto mantenere la proprietà 2 è piuttosto difficile. Una funzione hash più semplice è l'operatore modulo. Esistono molti algoritmi e librerie di hash.
Ora cosa ottieni quando combini questi due? Una mappa di hash. La chiave viene convertita in hash e memorizzata rispetto al valore . Quindi, se ho una coppia (A,A' ), convertirò A in hash B e conserverò (B, A') . Ora Se voglio ottenere qual è il valore memorizzato contro la chiave A, prima convertirò A in B e poi vedrò cosa viene memorizzato contro B, e lo restituirò.
Il vantaggio dell'utilizzo della mappa hash è il recupero veloce . È O (1), cioè in tempo costante posso scoprire se una chiave è presente e il valore contro di essa. Confrontalo con l'albero rosso-nero in cui la complessità temporale del recupero è O (logn). (C'è anche tempo di inserimento e cancellazione di cui non sto discutendo qui.)
Quindi ora dimmi qual è la tua domanda?
Leggi altre domande sui tag functions hashing implementations map