Perché una tabella hash? Perché non solo un array associativo non hash?

Naviga le tue risposte
2

Ho imparato a utilizzare un hashtable per controllare in modo efficiente gli elementi di un elenco senza doverli scorrere per intero, ma c'è una cosa che non riesco a ottenere:

Perché le chiavi hash?

Sembra: 

var wordList = {
   'aa'    : ['aa'],
   'aah'   : ['aah'],
   'ahhed' : ['aahed']
};

Funzionerebbe altrettanto bene: 

var wordList = {
   '/* hashed value of aa*/'    : ['aa'],
   '/* hashed value of aah*/'   : ['aah'],
   '/* hashed value of aahed*/' : ['aahed']
};

Qual è la differenza di prestazioni tra la ricerca di una chiave con hash e una semplice chiave di nome?

    
posta CuriousWebDeveloper 22.07.2014 - 23:26
fonte

2 risposte

8

Perché hai ancora bisogno di un modo per cercare l'array associativo. La tabella hash è il tuo meccanismo di ricerca; fornisce prestazioni O (1) per una determinata ricerca di chiavi, calcolando un indice nel bucket che contiene il tuo oggetto.

Qual è il meccanismo di ricerca sottostante, se non è una tabella hash? Un albero di ricerca binario? Ciò è positivo per le tabelle molto grandi, ma non è O(1) ; è O(log n) . Se non hai affatto un meccanismo di ricerca (ovvero stai cercando nell'intero array dall'alto verso il basso per trovare la tua chiave), il rendimento è O(n) .

Se le tue chiavi sono già ordinate, puoi usare una ricerca binaria senza mantenere un albero; anche questo è O(log n) performance.

    
risposta data 22.07.2014 - 23:33
fonte
0

Bene, se hai bisogno di trovare qualcosa nel tuo array associativo, devi scorrere tutte le chiavi e trovare l'uguaglianza. Ciò significa che, nel peggiore dei casi, dovrai scorrere l'intera raccolta per trovare la chiave giusta.

L'accesso a un array con un indice (myArray [0] ad esempio) è istantaneo; non richiede alcuna ricerca, perché il runtime delle lingue sa esattamente dove trovare questo valore.

Quando si utilizza una tabella hash, si calcola il codice hash di una determinata chiave per trovare il valore associato. L'hashcode è un indice nell'array sottostante della tabella hash. Ciò significa che trovare una chiave in una tabella hash è veloce quanto l'accesso a una matrice per indice.

Il codice di una tabella hash è un po 'più complesso, ma questa è l'idea generale.

    
risposta data 22.07.2014 - 23:52
fonte

Leggi altre domande sui tag

Design verificabile per una classe che può essere istanziata solo attraverso un metodo statico Il metodo manipola le variabili globali, contrassegna const?