Quero criar um HashMap grande, mas o put()desempenho não é bom o suficiente. Alguma ideia?

Outras sugestões de estrutura de dados são bem-vindas, mas preciso do recurso de pesquisa de um mapa Java:

map.get(key)

No meu caso, quero criar um mapa com 26 milhões de entradas. Usando o Java HashMap padrão, a taxa de colocação torna-se insuportavelmente lenta após 2-3 milhões de inserções.

Além disso, alguém sabe se o uso de diferentes distribuições de código hash para as chaves pode ajudar?

Meu método de hashcode:

byte[] a = new byte[2];
byte[] b = new byte[3];
...

public int hashCode() {
    int hash = 503;
    hash = hash * 5381 + (a[0] + a[1]);
    hash = hash * 5381 + (b[0] + b[1] + b[2]);
    return hash;
}

Estou usando a propriedade associativa de adição para garantir que objetos iguais tenham o mesmo código hash. As matrizes são bytes com valores no intervalo de 0 a 51. Os valores são usados ​​apenas uma vez em qualquer uma das matrizes. Os objetos são iguais se os arrays a contiverem os mesmos valores (em qualquer ordem) e o mesmo vale para o array b. Portanto, a = {0,1} b = {45,12,33} e a = {1,0} b = {33,45,12} são iguais.

EDITAR, algumas notas:

• Algumas pessoas criticaram o uso de um mapa hash ou outra estrutura de dados para armazenar 26 milhões de entradas. Não consigo ver por que isso parece estranho. Parece um problema clássico de estruturas de dados e algoritmos para mim. Tenho 26 milhões de itens e quero ser capaz de inseri-los rapidamente e consultá-los em uma estrutura de dados: forneça a estrutura de dados e os algoritmos.

• Definir a capacidade inicial do Java HashMap padrão para 26 milhões diminui o desempenho.

• Algumas pessoas sugeriram o uso de bancos de dados, em algumas outras situações esta é definitivamente a opção inteligente. Mas estou realmente fazendo uma pergunta sobre estruturas de dados e algoritmos, um banco de dados completo seria um exagero e muito mais lento do que uma boa solução de estrutura de dados (afinal, o banco de dados é apenas software, mas teria comunicação e possivelmente sobrecarga de disco).

Como muitas pessoas apontaram, o hashCode()método era o culpado. Ele estava gerando apenas cerca de 20.000 códigos para 26 milhões de objetos distintos. Isso é uma média de 1.300 objetos por hash bucket = very very bad. No entanto, se eu transformar os dois arrays em um número na base 52, tenho a garantia de obter um código hash exclusivo para cada objeto:

public int hashCode() {       
    // assume that both a and b are sorted       
    return a[0] + powerOf52(a[1], 1) + powerOf52(b[0], 2) + powerOf52(b[1], 3) + powerOf52(b[2], 4);
}

public static int powerOf52(byte b, int power) {
    int result = b;
    for (int i = 0; i < power; i++) {
        result *= 52;
    }
    return result;
}

Os arrays são classificados para garantir que esses métodos cumpram o hashCode()contrato de que objetos iguais tenham o mesmo código hash. Usando o método antigo, o número médio de opções de venda por segundo em blocos de 100.000 opções de venda, 100.000 a 2.000.000 era:

168350.17
109409.195
81344.91
64319.023
53780.79
45931.258
39680.29
34972.676
31354.514
28343.062
25562.371
23850.695
22299.22
20998.006
19797.799
18702.951
17702.434
16832.182
16084.52
15353.083

Usar o novo método dá:

337837.84
337268.12
337078.66
336983.97
313873.2
317460.3
317748.5
320000.0
309704.06
310752.03
312944.5
265780.75
275540.5
264350.44
273522.97
270910.94
279008.7
276285.5
283455.16
289603.25

Muito, muito melhor. O método antigo decaiu muito rapidamente, enquanto o novo manteve um bom rendimento.

Uma coisa que noto em seu hashCode()método é que a ordem dos elementos nas matrizes a[]e b[]não importam. Assim (a[]={1,2,3}, b[]={99,100}), o hash terá o mesmo valor que (a[]={3,1,2}, b[]={100,99}). Na verdade, todas as chaves k1e k2onde sum(k1.a)==sum(k2.a)e sum(k1.b)=sum(k2.b)resultarão em colisões. Sugiro atribuir um peso a cada posição da matriz:

hash = hash * 5381 + (c0*a[0] + c1*a[1]);
hash = hash * 5381 + (c0*b[0] + c1*b[1] + c3*b[2]);

onde, c0, c1e c3são distintas constantes (você pode usar diferentes constantes para bse necessário). Isso deve equilibrar um pouco mais as coisas.

Para elaborar em Pascal: Você entende como funciona um HashMap? Você tem algum número de slots em sua tabela de hash. O valor hash para cada chave é encontrado e, em seguida, mapeado para uma entrada na tabela. Se dois valores de hash forem mapeados para a mesma entrada - uma "colisão de hash" - o HashMap cria uma lista vinculada.

As colisões de hash podem prejudicar o desempenho de um mapa de hash. No caso extremo, se todas as suas chaves tiverem o mesmo código hash, ou se tiverem códigos hash diferentes, mas todos mapearem para o mesmo slot, seu mapa hash se transforma em uma lista vinculada.

Portanto, se você estiver tendo problemas de desempenho, a primeira coisa que devo verificar é: Estou recebendo uma distribuição de aparência aleatória de códigos hash? Caso contrário, você precisa de uma função hash melhor. Bem, "melhor" neste caso pode significar "melhor para meu conjunto específico de dados". Por exemplo, suponha que você esteja trabalhando com strings e tenha obtido o comprimento da string como valor hash. (Não é como o String.hashCode do Java funciona, mas estou apenas inventando um exemplo simples.) Se suas strings têm comprimentos amplamente variados, de 1 a 10.000, e são razoavelmente distribuídas por esse intervalo, isso pode ser muito bom função hash. Mas se todas as suas strings tiverem 1 ou 2 caracteres, isso seria uma função hash muito ruim.

Edit: Devo acrescentar: Cada vez que você adiciona uma nova entrada, o HashMap verifica se esta é uma duplicata. Quando há uma colisão de hash, ele tem que comparar a chave recebida com cada chave mapeada para aquele slot. Portanto, no pior caso em que tudo faz hash em um único slot, a segunda chave é comparada com a primeira chave, a terceira chave é comparada com # 1 e # 2, a quarta chave é comparada com # 1, # 2 e # 3 , etc. Quando você chega à chave # 1 milhão, você já fez mais de um trilhão de comparações.

@Oscar: Umm, não vejo como isso é um "não realmente". É mais como um "deixe-me esclarecer". Mas sim, é verdade que se você fizer uma nova entrada com a mesma chave de uma entrada existente, isso sobrescreverá a primeira entrada. Isso é o que eu quis dizer quando falei sobre a procura de duplicatas no último parágrafo: Sempre que uma chave hash para o mesmo slot, o HashMap deve verificar se é uma duplicata de uma chave existente, ou se eles estão apenas no mesmo slot por coincidência do função hash. Não sei se esse é o "ponto principal" de um HashMap: eu diria que o "ponto principal" é que você pode recuperar elementos por chave rapidamente.

Mas de qualquer maneira, isso não afeta o "ponto inteiro" que eu estava tentando fazer: quando você tem duas chaves - sim, chaves diferentes, não a mesma chave aparecendo novamente - que mapeiam para o mesmo slot na mesa , O HashMap constrói uma lista vinculada. Então, como tem que verificar cada nova chave para ver se é de fato uma duplicata de uma chave existente, cada tentativa de adicionar uma nova entrada que mapeia para este mesmo slot deve seguir a lista vinculada examinando cada entrada existente para ver se isso é uma duplicata de uma chave vista anteriormente ou se é uma nova chave.

Atualizar muito depois da postagem original

Acabei de receber um voto favorável nesta resposta 6 anos após postar, o que me levou a reler a pergunta.

A função hash fornecida na pergunta não é um bom hash para 26 milhões de entradas.

Ele soma a [0] + a [1] e b [0] + b [1] + b [2]. Ele diz que os valores de cada byte variam de 0 a 51, de modo que dá apenas (51 * 2 + 1) * (51 * 3 + 1) = 15.862 valores de hash possíveis. Com 26 milhões de entradas, isso significa uma média de cerca de 1639 entradas por valor de hash. São muitas e muitas colisões, exigindo muitas e muitas pesquisas sequenciais por meio de listas vinculadas.

O OP diz que ordens diferentes dentro da matriz a e da matriz b devem ser consideradas iguais, ou seja, [[1,2], [3,4,5]]. Iguais ([[2,1], [5,3,4] ]) e, portanto, para cumprir o contrato, eles devem ter códigos hash iguais. OK. Ainda assim, existem muito mais de 15.000 valores possíveis. Sua segunda função hash proposta é muito melhor, oferecendo uma gama mais ampla.

Embora, como alguém comentou, parece impróprio para uma função hash alterar outros dados. Faria mais sentido "normalizar" o objeto quando ele for criado ou fazer com que a função hash funcionasse a partir de cópias dos arrays. Além disso, usar um loop para calcular constantes toda vez que por meio da função é ineficiente. Como existem apenas quatro valores aqui, eu teria escrito

return a[0]+a[1]*52+b[0]*52*52+b[1]*52*52*52+b[2]*52*52*52*52;

que faria com que o compilador executasse o cálculo uma vez em tempo de compilação; ou tem 4 constantes estáticas definidas na classe.

Além disso, o primeiro rascunho em uma função hash tem vários cálculos que não fazem nada para adicionar ao intervalo de saídas. Observe que ele primeiro define hash = 503 e depois multiplica por 5381 antes mesmo de considerar valores da classe. Então ... com efeito, ele adiciona 503 * 5381 a cada valor. O que isso significa? Adicionar uma constante a cada valor de hash apenas queima os ciclos da CPU sem realizar nada de útil. Lição aqui: Adicionar complexidade a uma função hash não é o objetivo. O objetivo é obter uma ampla gama de valores diferentes, não apenas para adicionar complexidade por causa da complexidade.

Minha primeira ideia é ter certeza de que você está inicializando seu HashMap de maneira apropriada. De JavaDocs para HashMap :

Uma instância de HashMap tem dois parâmetros que afetam seu desempenho: capacidade inicial e fator de carga. A capacidade é o número de baldes na tabela hash, e a capacidade inicial é simplesmente a capacidade no momento em que a tabela hash é criada. O fator de carga é uma medida de quão cheia a tabela hash pode ficar antes que sua capacidade seja aumentada automaticamente. Quando o número de entradas na tabela hash excede o produto do fator de carga e a capacidade atual, a tabela hash é refeita (ou seja, as estruturas de dados internas são reconstruídas) para que a tabela hash tenha aproximadamente o dobro do número de depósitos.

Então, se você está começando com um HashMap muito pequeno, toda vez que ele precisa ser redimensionado, todos os hashes são recalculados ... o que pode ser o que você está sentindo quando chega ao ponto de inserção de 2-3 milhões.

Eu sugeriria uma abordagem em três frentes:

1. Execute Java com mais memória: java -Xmx256Mpor exemplo, para executar com 256 Megabytes. Use mais, se necessário, e você terá muita RAM.

2. Armazene seus valores de hash calculados conforme sugerido por outro usuário, para que cada objeto calcule seu valor de hash apenas uma vez.

3. Use um algoritmo de hash melhor. O que você postou retornaria o mesmo hash onde a = {0, 1} e onde a = {1, 0}, todo o resto sendo igual.

Utilize o que o Java oferece gratuitamente.

public int hashCode() {
    return 31 * Arrays.hashCode(a) + Arrays.hashCode(b);
}

Tenho certeza de que isso tem muito menos chance de conflito do que o método hashCode existente, embora dependa da natureza exata dos seus dados.

Entrar na área cinzenta de "tópico ligado / desligado", mas necessário para eliminar a confusão sobre a sugestão de Oscar Reyes de que mais colisões de hash é uma coisa boa porque reduz o número de elementos no HashMap. Posso entender mal o que Oscar está dizendo, mas não pareço ser o único: kdgregory, delfuego, Nash0, e todos parecem compartilhar o mesmo (mal) entendimento.

Se eu entendi o que Oscar está dizendo sobre a mesma classe com o mesmo hashcode, ele está propondo que apenas uma instância de uma classe com um determinado hashcode será inserida no HashMap. Por exemplo, se eu tiver uma instância de SomeClass com hashcode 1 e uma segunda instância de SomeClass com hashcode 1, apenas uma instância de SomeClass será inserida.

O exemplo de pastebin Java em http://pastebin.com/f20af40b9 parece indicar que o acima resume corretamente o que Oscar está propondo.

Independentemente de qualquer entendimento ou mal-entendido, o que acontece é que diferentes instâncias da mesma classe não são inseridas apenas uma vez no HashMap se tiverem o mesmo hashcode - não até que seja determinado se as chaves são iguais ou não. O contrato de hashcode requer que objetos iguais tenham o mesmo hashcode; no entanto, não requer que objetos desiguais tenham hashcodes diferentes (embora isso possa ser desejável por outros motivos) [1].

O exemplo pastebin.com/f20af40b9 (ao qual Oscar se refere pelo menos duas vezes) segue, mas foi ligeiramente modificado para usar asserções JUnit em vez de linhas de impressão. Este exemplo é usado para apoiar a proposta de que os mesmos hashcodes causam colisões e quando as classes são as mesmas, apenas uma entrada é criada (por exemplo, apenas uma String neste caso específico):

@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
    String s = new String("ese");
    String ese = new String("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // AND equal
    assertTrue(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(2, map.size());

    assertEquals(2, map.get("ese"));
    assertEquals(3, map.get(some));

    assertTrue(s.equals(ese) && s.equals("ese"));
}

class SomeClass {
    public int hashCode() {
        return 100727;
    }
}

No entanto, o hashcode não é a história completa. O que o exemplo pastebin negligencia é o fato de que se esesão iguais: ambos são a string "ese". Assim, inserir ou obter o conteúdo do mapa usando sou eseou "ese"como a chave são todos equivalentes porques.equals(ese) && s.equals("ese") .

Um segundo teste demonstra que é errôneo concluir que hashcodes idênticos na mesma classe é o motivo pelo qual a chave -> valor s -> 1é substituída por ese -> 2quando map.put(ese, 2)é chamada no teste um. No teste dois, se eseainda têm o mesmo hashcode (conforme verificado por assertEquals(s.hashCode(), ese.hashCode());) E são da mesma classe. No entanto, se esesão MyStringinstâncias neste teste, não Stringinstâncias Java - com a única diferença relevante para este teste sendo os iguais: String s equals String eseno teste um acima, enquanto MyStrings s does not equal MyString eseno teste dois:

@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
    MyString s = new MyString("ese");
    MyString ese = new MyString("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // BUT not equal
    assertFalse(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(3, map.size());

    assertEquals(1, map.get(s));
    assertEquals(2, map.get(ese));
    assertEquals(3, map.get(some));
}

/**
 * NOTE: equals is not overridden so the default implementation is used
 * which means objects are only equal if they're the same instance, whereas
 * the actual Java String class compares the value of its contents.
 */
class MyString {
    String i;

    MyString(String i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return 100727;
    }
}

Com base em um comentário posterior, Oscar parece inverter o que disse anteriormente e reconhece a importância dos iguais. No entanto, ainda parece que a noção de que igual é o que importa, não a "mesma classe", não está clara (grifo meu):

"Na verdade, não. A lista é criada apenas se o hash for o mesmo, mas a chave for diferente. Por exemplo, se uma String fornece o hashcode 2345 e o Integer fornece o mesmo hashcode 2345, o inteiro é inserido na lista porque String. equals (Integer) é false. Mas se você tem a mesma classe (ou pelo menos .equals retorna true), então a mesma entrada é usada. Por exemplo, new String ("um") e `new String (" one ") usados ​​como , usará a mesma entrada. Na verdade, este é o ponto INTEIRO do HashMap em primeiro lugar! Veja você mesmo: pastebin.com/f20af40b9 - Oscar Reyes "

versus comentários anteriores que abordam explicitamente a importância de uma classe idêntica e do mesmo código hash, sem menção de iguais:

"@delfuego: Veja você mesmo: pastebin.com/f20af40b9 Então, nesta questão, a mesma classe está sendo usada (espere um minuto, a mesma classe está sendo usada certo?) O que implica que quando o mesmo hash é usado, a mesma entrada é usado e não há "lista" de entradas. - Oscar Reyes "

ou

"Na verdade, isso aumentaria o desempenho. Quanto mais colisões eq menos entradas na eq. Hashtable menos trabalho a fazer. Não é o hash (que parece bom) nem a hashtable (que funciona muito bem), aposto que é no objeto criação onde o desempenho é degradante. - Oscar Reyes "

ou

"@kdgregory: Sim, mas apenas se a colisão acontecer com classes diferentes, para a mesma classe (que é o caso) a mesma entrada é usada. - Oscar Reyes"

Mais uma vez, posso interpretar mal o que Oscar estava realmente tentando dizer. No entanto, seus comentários originais causaram confusão suficiente que parece prudente esclarecer tudo com alguns testes explícitos para que não haja dúvidas persistentes.

[1] - From Effective Java, Second Edition por Joshua Bloch:

• Sempre que ele é chamado no mesmo objeto mais de uma vez durante a execução de um aplicativo, o método hashCode deve retornar consistentemente o mesmo inteiro, desde que nenhuma informação usada em comparações de igualdade no objeto seja modificada. Este inteiro não precisa permanecer consistente de uma execução de um aplicativo para outra execução do mesmo aplicativo.

• Se dois objetos são iguais de acordo com o método equal s (Obj ect), chamar o método hashCode em cada um dos dois objetos deve produzir o mesmo resultado inteiro.

• Não é necessário que, se dois objetos forem desiguais de acordo com o método equal s (Object), chamar o método hashCode em cada um dos dois objetos deve produzir resultados inteiros distintos. No entanto, o programador deve estar ciente de que produzir resultados inteiros distintos para objetos desiguais pode melhorar o desempenho das tabelas hash.

Se os arrays em seu hashCode postado forem bytes, você provavelmente terá muitas duplicatas.

a [0] + a [1] estará sempre entre 0 e 512. adicionar os b sempre resultará em um número entre 0 e 768. multiplique-os e obterá um limite superior de 400.000 combinações únicas, assumindo que seus dados estão perfeitamente distribuídos entre todos os valores possíveis de cada byte. Se seus dados forem regulares, você provavelmente terá muito menos resultados exclusivos desse método.

O HashMap tem capacidade inicial e o desempenho do HashMap depende muito do hashCode que produz os objetos subjacentes.

Tente ajustar ambos.

Se as chaves tiverem qualquer padrão, você poderá dividir o mapa em mapas menores e ter um mapa de índice.

Exemplo: Chaves: 1,2,3, .... n 28 mapas de 1 milhão cada. Mapa de índice: 1-1.000.000 -> Mapa1 1.000.000-2.000.000 -> Mapa2

Portanto, você fará duas pesquisas, mas o conjunto de chaves seria 1.000.000 contra 28.000.000. Você também pode fazer isso facilmente com padrões de picadas.

Se as chaves forem completamente aleatórias, isso não funcionará

Se as matrizes de dois bytes que você menciona são a sua chave inteira, os valores estão no intervalo de 0-51, únicos e a ordem dentro das matrizes a e b é insignificante, minha matemática me diz que há apenas cerca de 26 milhões de permutações possíveis e que você provavelmente está tentando preencher o mapa com valores para todas as chaves possíveis.

Nesse caso, preencher e recuperar valores de seu armazenamento de dados seria obviamente muito mais rápido se você usar uma matriz em vez de um HashMap e indexá-lo de 0 a 25989599.

Estou atrasado aqui, mas alguns comentários sobre mapas grandes:

1. Conforme discutido longamente em outros posts, com um bom hashCode (), 26 milhões de entradas em um mapa não é grande coisa.
2. No entanto, um problema potencialmente oculto aqui é o impacto GC de mapas gigantes.

Estou supondo que esses mapas têm vida longa. ou seja, você os preenche e eles permanecem durante o aplicativo. Também estou assumindo que o próprio aplicativo tem longa duração - como um servidor de algum tipo.

Cada entrada em um HashMap Java requer três objetos: a chave, o valor e a Entrada que os une. Portanto, 26 milhões de entradas no mapa significam 26 milhões * 3 == 78 milhões de objetos. Isso é bom até você atingir um GC completo. Então você tem um problema de pausa no mundo. O GC examinará cada um dos objetos 78M e determinará que estão todos vivos. 78M + objetos são apenas muitos objetos para se olhar. Se seu aplicativo pode tolerar longas pausas ocasionais (talvez muitos segundos), não há problema. Se você está tentando obter qualquer garantia de latência, pode ter um grande problema (é claro, se você quiser garantias de latência, Java não é a plataforma a escolher :)) Se os valores em seus mapas mudam rapidamente, você pode acabar com coletas completas frequentes o que agrava muito o problema.

Não conheço uma ótima solução para esse problema. Ideias:

• Às vezes, é possível ajustar o GC e os tamanhos de heap para evitar "principalmente" GCs completos.
• Se o conteúdo do seu mapa se agita muito, você pode tentar FastMap do Javolution - ele pode agrupar objetos de entrada, o que pode diminuir a frequência de coletas completas
• Você pode criar seu próprio map impl e fazer gerenciamento de memória explícito no byte [] (isto é, trocar cpu por latência mais previsível serializando milhões de objetos em um único byte [] - ugh!)
• Não use Java para esta parte - converse com algum tipo de banco de dados previsível na memória por meio de um soquete
• Espero que o novo coletor G1 ajude (aplica-se principalmente ao caso de alta rotatividade)

Apenas alguns pensamentos de alguém que passou muito tempo com mapas gigantes em Java.

No meu caso, quero criar um mapa com 26 milhões de entradas. Usando o Java HashMap padrão, a taxa de colocação torna-se insuportavelmente lenta após 2-3 milhões de inserções.

Do meu experimento (projeto do aluno em 2009):

• Eu construí uma Red Black Tree para 100.000 nós de 1 a 100.000. Demorou 785,68 segundos (13 minutos). E eu falhei em construir RBTree para 1 milhão de nós (como seus resultados com HashMap).
• Usando "Prime Tree", minha estrutura de dados de algoritmo. Eu poderia construir uma árvore / mapa para 10 milhões de nós em 21,29 segundos (RAM: 1,97 Gb). O custo do valor-chave da pesquisa é O (1).

Nota: "Prime Tree" funciona melhor em "chaves contínuas" de 1 a 10 milhões. Para trabalhar com chaves como HashMap, precisamos de alguns ajustes menores.

Então, o que é #PrimeTree? Resumindo, é uma estrutura de dados em árvore como a Árvore Binária, com os números dos ramos sendo números primos (em vez de "2" -binários).

Você pode tentar usar um banco de dados na memória como HSQLDB .

SQLite permite que você o use na memória.

Você já pensou em usar um banco de dados embutido para fazer isso? Veja Berkeley DB . É open-source, propriedade da Oracle agora.

Ele armazena tudo como par Chave-> Valor, NÃO é um RDBMS. e pretende ser rápido.

Primeiro você deve verificar se está usando o Map corretamente, bom método hashCode () para as chaves, capacidade inicial do Map, implementação correta do Map, etc., como muitas outras respostas descrevem.

Então, eu sugeriria usar um criador de perfil para ver o que está realmente acontecendo e onde o tempo de execução é gasto. O método hashCode () é, por exemplo, executado bilhões de vezes?

Se isso não ajudar, que tal usar algo como EHCache ou memcached ? Sim, eles são produtos para armazenamento em cache, mas você pode configurá-los de forma que tenham capacidade suficiente e nunca despejem nenhum valor do armazenamento em cache.

Outra opção seria algum mecanismo de banco de dados mais leve do que o SQL RDBMS completo. Algo como Berkeley DB , talvez.

Observe que, pessoalmente, não tenho experiência com o desempenho desses produtos, mas vale a pena tentar.

Você pode tentar armazenar em cache o código hash computado para o objeto chave.

Algo assim:

public int hashCode() {
  if(this.hashCode == null) {
     this.hashCode = computeHashCode();
  }
  return this.hashCode;
}

private int computeHashCode() {
   int hash = 503;
   hash = hash * 5381 + (a[0] + a[1]);
   hash = hash * 5381 + (b[0] + b[1] + b[2]);
   return hash;
}

É claro que você deve ter cuidado para não alterar o conteúdo da chave após o hashCode ter sido calculado pela primeira vez.

Editar: parece que o armazenamento em cache tem valores de código não vale a pena quando você adiciona cada chave apenas uma vez em um mapa. Em alguma outra situação, isso pode ser útil.

Outro autor já apontou que sua implementação de hashcode resultará em muitas colisões devido à maneira como você está adicionando valores. Estou disposto a ser isso, se você olhar para o objeto HashMap em um depurador, você descobrirá que tem talvez 200 valores de hash distintos, com cadeias de bucket extremamente longas.

Se você sempre tiver valores no intervalo de 0 a 51, cada um desses valores terá 6 bits para representar. Se você sempre tem 5 valores, pode criar um hashcode de 30 bits com deslocamentos para a esquerda e adições:

    int code = a[0];
    code = (code << 6) + a[1];
    code = (code << 6) + b[0];
    code = (code << 6) + b[1];
    code = (code << 6) + b[2];
    return code;

O deslocamento para a esquerda é rápido, mas deixará você com códigos de hash que não estão uniformemente distribuídos (porque 6 bits implicam em um intervalo de 0 a 63). Uma alternativa é multiplicar o hash por 51 e adicionar cada valor. Isso ainda não será perfeitamente distribuído (por exemplo, {2,0} e {1,52} irão colidir), e será mais lento do que o deslocamento.

    int code = a[0];
    code *= 51 + a[1];
    code *= 51 + b[0];
    code *= 51 + b[1];
    code *= 51 + b[2];
    return code;

Como apontado, sua implementação de hashcode tem muitas colisões e consertá-la deve resultar em um desempenho decente. Além disso, armazenar hashCodes em cache e implementar equals com eficiência ajudará.

Se você precisa otimizar ainda mais:

Pela sua descrição, existem apenas (52 * 51/2) * (52 * 51 * 50/6) = 29304600 chaves diferentes (das quais 26000000, ou seja, cerca de 90%, estarão presentes). Portanto, você pode projetar uma função hash sem nenhuma colisão e usar uma matriz simples em vez de um hashmap para armazenar seus dados, reduzindo o consumo de memória e aumentando a velocidade de pesquisa:

T[] array = new T[Key.maxHashCode];

void put(Key k, T value) {
    array[k.hashCode()] = value;

T get(Key k) {
    return array[k.hashCode()];
}

(Geralmente, é impossível projetar uma função hash eficiente e livre de colisões que agrupe bem, e é por isso que um HashMap tolera colisões, o que incorre em alguma sobrecarga)

Supondo que ae bestejam classificados, você pode usar a seguinte função hash:

public int hashCode() {
    assert a[0] < a[1]; 
    int ahash = a[1] * a[1] / 2 
              + a[0];

    assert b[0] < b[1] && b[1] < b[2];

    int bhash = b[2] * b[2] * b[2] / 6
              + b[1] * b[1] / 2
              + b[0];
    return bhash * 52 * 52 / 2 + ahash;
}

static final int maxHashCode = 52 * 52 / 2 * 52 * 52 * 52 / 6;  

Acho que está livre de colisões. Provar isso é deixado como um exercício para o leitor com inclinação pela matemática.

Em Effective Java: Guia de linguagem de programação (série Java)

No Capítulo 3, você pode encontrar boas regras a seguir ao calcular hashCode ().

Especialmente:

Se o campo for uma matriz, trate-o como se cada elemento fosse um campo separado. Ou seja, calcule um código hash para cada elemento significativo aplicando essas regras recursivamente e combine esses valores por etapa 2.b. Se cada elemento em um campo de array for significativo, você pode usar um dos métodos Arrays.hashCode adicionados na versão 1.5.

Aloque um grande mapa no início. Se você sabe que terá 26 milhões de entradas e tem memória para isso, faça a new HashMap(30000000).

Tem certeza de que tem memória suficiente para 26 milhões de entradas com 26 milhões de chaves e valores? Isso soa como muita memória para mim. Tem certeza de que a coleta de lixo ainda está indo bem na sua marca de 2 a 3 milhões? Eu poderia imaginar isso como um gargalo.

Você pode tentar duas coisas:

Essas duas ações irão reduzir tremendamente a quantidade de reformulação da estrutura e são muito fáceis de testar, eu acho.

Se isso não funcionar, considere usar um armazenamento diferente, como RDBMS.

EDITAR

É estranho que configurar a capacidade inicial reduza o desempenho no seu caso.

Veja nos javadocs :

Se a capacidade inicial for maior que o número máximo de entradas dividido pelo fator de carga, nenhuma operação de rehash ocorrerá.

Fiz uma microbiana marca (que não é de forma alguma definitiva, mas pelo menos prova este ponto)

$cat Huge*java
import java.util.*;
public class Huge {
    public static void main( String [] args ) {
        Map map = new HashMap( 30000000 , 0.95f );
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
import java.util.*;
public class Huge2 {
    public static void main( String [] args ) {
        Map map = new HashMap();
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
$time java -Xms2g -Xmx2g Huge

real    0m16.207s
user    0m14.761s
sys 0m1.377s
$time java -Xms2g -Xmx2g Huge2

real    0m21.781s
user    0m20.045s
sys 0m1.656s
$

Portanto, o uso da capacidade inicial cai de 21s para 16s por causa do rehasing. Isso nos deixa com seu hashCodemétodo como uma "área de oportunidade";)

EDITAR

Não é o HashMap

De acordo com sua última edição.

Eu acho que você realmente deveria criar o perfil de seu aplicativo e ver onde a memória / cpu está sendo consumida.

Eu criei uma classe implementando o seu mesmo hashCode

Esse código hash dá milhões de colisões, então as entradas no HashMap são reduzidas drasticamente.

Eu passo de 21s, 16s em meu teste anterior para 10s e 8s. A razão é porque o hashCode provoca um grande número de colisões e você não está armazenando os 26 milhões de objetos que você pensa, mas um número muito inferior (cerca de 20k eu diria). Então:

O problema NÃO É O HASHMAP está em outro lugar no seu código.

É hora de obter um profiler e descobrir onde. Acho que é na criação do item ou provavelmente você está gravando no disco ou recebendo dados da rede.

Aqui está minha implementação de sua classe.

note que eu não usei um intervalo de 0-51 como você fez, mas -126 a 127 para meus valores e admite repetido, isso é porque eu fiz este teste antes de você atualizar sua pergunta

A única diferença é que sua classe terá mais colisões, portanto, menos itens armazenados no mapa.

import java.util.*;
public class Item {

    private static byte w = Byte.MIN_VALUE;
    private static byte x = Byte.MIN_VALUE;
    private static byte y = Byte.MIN_VALUE;
    private static byte z = Byte.MIN_VALUE;

    // Just to avoid typing :) 
    private static final byte M = Byte.MAX_VALUE;
    private static final byte m = Byte.MIN_VALUE;


    private byte [] a = new byte[2];
    private byte [] b = new byte[3];

    public Item () {
        // make a different value for the bytes
        increment();
        a[0] = z;        a[1] = y;    
        b[0] = x;        b[1] = w;   b[2] = z;
    }

    private static void increment() {
        z++;
        if( z == M ) {
            z = m;
            y++;
        }
        if( y == M ) {
            y = m;
            x++;
        }
        if( x == M ) {
            x = m;
            w++;
        }
    }
    public String toString() {
        return "" + this.hashCode();
    }



    public int hashCode() {
        int hash = 503;
        hash = hash * 5381 + (a[0] + a[1]);
        hash = hash * 5381 + (b[0] + b[1] + b[2]);
        return hash;
    }
    // I don't realy care about this right now. 
    public boolean equals( Object other ) {
        return this.hashCode() == other.hashCode();
    }

    // print how many collisions do we have in 26M items.
    public static void main( String [] args ) {
        Set set = new HashSet();
        int collisions = 0;
        for ( int i = 0 ; i < 26000000 ; i++ ) {
            if( ! set.add( new Item() ) ) {
                collisions++;
            }
        }
        System.out.println( collisions );
    }
}

Usar esta classe tem a chave para o programa anterior

 map.put( new Item() , i );

me dá:

real     0m11.188s
user     0m10.784s
sys 0m0.261s


real     0m9.348s
user     0m9.071s
sys  0m0.161s

Talvez tente usar se precisar que seja sincronizado

http://commons.apache.org/collections/api/org/apache/commons/collections/FastHashMap.html

Fiz um pequeno teste um tempo atrás com uma lista vs um hashmap, o engraçado foi iterar pela lista e encontrar o objeto demorou o mesmo tempo em milissegundos que usar a função get hashmaps ... apenas um fyi. Ah, sim, a memória é um grande problema ao trabalhar com hashmaps desse tamanho.

Os métodos de hash populares usados ​​não são realmente muito bons para grandes conjuntos e, como apontado acima, o hash usado é particularmente ruim. Melhor é usar um algoritmo de hash com alta combinação e cobertura, como BuzHash (exemplo de implementação em http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )