Uso efficiente di Hashmap

Question

Qual è l'approccio più efficiente per l'utilizzo di hashmap?

A) Usa più hashmap più piccole o

B) memorizzare tutti gli oggetti in una hashmap gigante?

(Supponiamo che l'algoritmo di hashing per le chiavi sia abbastanza efficiente, causando poche collisioni)

CHIARIMENTO: L'opzione B implica la separazione per chiave primaria, ovvero non è necessaria alcuna ricerca aggiuntiva per determinare quale hashmap reale utilizzare. (Ad esempio, se i tasti di ricerca sono alfanumerici, Hashmap 1 memorizza le A, Hashmap 2 memorizza le B e così via.)

Answer 1

Sicuramente B. Il vantaggio delle tabelle hash è che il numero medio di confronti per ricerca è indipendente dalla dimensione.

Se dividi la tua mappa in N hashaps più piccoli, dovrai cercarne la metà in media per ogni ricerca. Se gli hashaps più piccoli hanno lo stesso fattore di carico che avrebbe avuto la mappa più grande, aumenterai il numero totale di confronti di un fattore di circa N / 2.

E se gli hashap più piccoli hanno un fattore di carico più piccolo, stai sprecando memoria.

Tutto ciò presuppone che tu distribuisca le chiavi in ??modo casuale tra gli hashaps più piccoli. Se li distribuisci in base a una funzione del tasto (ad esempio un prefisso stringa), ciò che hai creato è un trie , che è efficace per alcune applicazioni (ad esempio il completamento automatico nei moduli Web.)

Answer 2

Queste mappe sono utilizzate in luoghi logicamente distinti? Ad esempio, non avrei una mappa contenente utenti, risultati di query memorizzati nella cache, logger ecc., Solo perché ti capita di sapere che le chiavi non si scontreranno. Tuttavia, allo stesso modo non dividerei una singola mappa in più mappe.

Mantieni un hashmap per ogni logico dalla chiave al valore.

Answer 3

In aggiunta alla risposta di Jon, possono esserci motivi pratici per cui si desidera mantenere tabelle hash separate.

Se si dispone di tabelle separate per diversi mapping, è possibile "cancellare" ciascuno dei mapping in modo indipendente; per esempio. chiamando "clear" o eliminando il riferimento alla tabella corrispondente.

Se le tabelle separate contengono mapping alle voci memorizzate nella cache, è possibile utilizzare strategie diverse per "invecchiare" le rispettive voci.

Se l'applicazione è multi-thread, l'utilizzo di tabelle separate può ridurre la contesa tra i blocchi e può (per alcune architetture di processori) aumentare i rapporti di hit della cache della memoria del processore.