Eficiente HashMap Use

Question

Qual é a abordagem mais eficiente para o uso HashMaps?

A) Usar vários HashMaps menores, ou

B) armazenar todos os objetos em um hashmap gigante?

(Suponha que o algoritmo de hash para as chaves é bastante eficiente, resultando em algumas colisões)

ESCLARECIMENTO: Opção B implica a segregação por chave primária - ou seja, nenhuma pesquisa adicional é necessária para determinar qual hashmap real para uso. (Por exemplo, se as chaves de pesquisa são alfanumérico, HashMap 1 lojas, HashMap 2 lojas da A B das, e assim por diante.)

Answer 1

Definitivamente B. A vantagem de tabelas hash é que o número médio de comparações por pesquisa é independente do tamanho.

Se você dividir o seu mapa em N HashMaps menores, você vai ter que procurar a metade deles, em média, para cada pesquisa. Se os HashMaps menores têm o mesmo fator de carga que o mapa maior teria tido, você vai aumentar o número total de comparações por um factor de aproximadamente N / 2.

memória E se os HashMaps menores têm uma taxa de ocupação menor, você está desperdiçando.

Tudo o que é supondo que você distribuir as chaves de forma aleatória entre os HashMaps menores. Se você distribuí-los de acordo com alguns função da tecla (por exemplo, uma cadeia de prefixo), então o que você criou é um trie , que é eficiente para algumas aplicações (por exemplo, auto-completar formulários da web).

Answer 2

São estes mapas usados ??em locais logicamente distintos? Por exemplo, eu não teria um mapa usuários contendo, os resultados da consulta em cache, madeireiros, etc, só porque você acontecer de conhecer as chaves não irá colidir. No entanto, eu também não iria dividir um único mapa em vários mapas.

Mantenha uma hashmap para cada lógica mapeamento de chave para o valor.

Answer 3

Além disso @ resposta de Jon, pode haver razões práticas pelas quais você deseja manter tabelas hash separadas.

Se você tiver tabelas separadas para diferentes mapeamentos que puder 'clear' cada um dos mapeamentos de forma independente; por exemplo. chamando 'claro' ou se livrar da referência à mesa correspondente.

Se as mesas separadas realizar mapeamentos para entradas em cache, você pode usar diferentes estratégias para 'idade' das respectivas entradas.

Se a aplicação é multi-threaded, usando tabelas separadas pode reduzir a contenção de bloqueio e pode (para algumas arquiteturas de processador) cache de memória aumento processador atingiu proporções.