Otimização de desempenho / alternativa do Java HashMap

Eu quero criar um grande HashMap, mas o desempenho put() 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 inputs. Usando o Java HashMap padrão, a taxa de put se torna insuportavelmente lenta após 2-3 milhões de inserções.

Além disso, alguém sabe se usar diferentes distribuições de código hash para as chaves poderia 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; } 

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

EDIT, algumas notas:

  • Algumas pessoas criticaram o uso de um mapa de hash ou outra estrutura de dados para armazenar 26 milhões de inputs. Não vejo 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 poder inseri-los rapidamente e consultá-los a partir de 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 que é definitivamente a opção inteligente. Mas eu estou realmente perguntando uma questão de estruturas de dados e algoritmos, um database completo seria um exagero e muito mais lento do que uma boa solução de estrutura de dados (afinal o database é apenas software mas teria comunicação e possivelmente sobrecarga de disco).

Como muitas pessoas apontaram, o hashCode() era o culpado. Ele estava gerando apenas cerca de 20.000 códigos para 26 milhões de objects distintos. Essa é uma média de 1.300 objects por hash = muito muito ruim. No entanto, se eu transformar as duas matrizes em um número na base 52, tenho a garantia de obter um código hash exclusivo para cada object:

 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; } 

As matrizes são classificadas para garantir que esses methods cumpram o contrato hashCode() que objects iguais tenham o mesmo código hash. Usando o método antigo, o número médio de puts por segundo em blocos de 100.000 puts, de 100.000 a 2.000.000 foi:

 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 

Usando 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 melhor. O método antigo diminuiu muito rapidamente enquanto o novo mantém um bom rendimento.

Uma coisa que noto no seu hashCode() é que a ordem dos elementos nas matrizes a[] b[] não importa. Assim (a[]={1,2,3}, b[]={99,100}) irá hash para o mesmo valor que (a[]={3,1,2}, b[]={100,99}) . Na verdade, todas as chaves k1 e k2 onde sum(k1.a)==sum(k2.a) e sum(k1.b)=sum(k2.b) resultarão em colisões. Eu sugiro atribuir um peso para 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 , c1 e c3 são constantes distintas (você pode usar constantes diferentes para b se necessário). Isso deve equilibrar as coisas um pouco mais.

Para elaborar sobre Pascal: Você entende como funciona um HashMap? Você tem um certo número de slots na sua tabela de hash. O valor de hash para cada chave é encontrado e, em seguida, mapeado para uma input na tabela. Se dois valores de hash mapeiam para a mesma input – uma “colisão de hash” – o HashMap constrói uma linked list.

Colisões de hash podem matar o desempenho de um mapa de hash. No caso extremo, se todas as 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 tornará uma linked list.

Então, se você está vendo problemas de desempenho, a primeira coisa que eu verifico é: Estou recebendo uma distribuição aleatória de códigos hash? Se não, você precisa de uma melhor function de hash. Bem, “melhor” neste caso pode significar “melhor para o meu conjunto particular de dados”. Tipo, suponha que você estivesse trabalhando com strings e tomou o tamanho da string para o valor de hash. (Não é como o String.hashCode do Java funciona, mas eu estou apenas inventando um exemplo simples.) Se suas strings tiverem comprimentos muito variados, de 1 a 10.000, e forem distribuídas de maneira uniforme por esse intervalo, isso pode ser muito bom function hash. Mas se suas strings são todas 1 ou 2 caracteres, isso seria uma function hash muito ruim.

Edit: Eu deveria adicionar: Toda vez que você adicionar uma nova input, HashMap verifica se esta é uma duplicata. Quando há uma colisão de hash, ela precisa comparar a chave de input com todas as chaves mapeadas para esse slot. Assim, no pior caso em que tudo é armazenado em um único slot, a segunda chave é comparada à primeira, a terceira chave é comparada a # 1 e # 2, a quarta chave é comparada a # 1, # 2 e # 3 No momento em que você chega à chave # 1 milhão, você fez mais de um trilhão de comparações.

@ Oscar: Umm, eu não vejo como isso é “não realmente”. É mais como um “deixe-me esclarecer”. Mas sim, é verdade que se você criar uma nova input com a mesma chave de uma input existente, isso substitui a primeira input. Foi isso que eu quis dizer quando falei em procurar duplicatas no último parágrafo: Sempre que uma chave é colocada no mesmo slot, o HashMap deve verificar se é uma duplicata de uma chave existente ou se elas estão no mesmo slot por coincidência function hash. Eu não sei se esse é o “ponto inteiro” de um HashMap: eu diria que o “ponto inteiro” é que você pode recuperar elementos por chave rapidamente.

Mas de qualquer forma, 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 de novo – esse mapa para o mesmo slot na tabela , O HashMap constrói uma linked list. Então, como ele precisa verificar cada nova chave para ver se ela é, na verdade, uma duplicata de uma chave existente, cada tentativa de adicionar uma nova input que mapeia para esse mesmo slot deve perseguir a linked list examinando cada input existente para ver se é uma duplicata de uma chave vista anteriormente ou se é uma nova chave.

Atualize por muito tempo após a postagem original

Acabei de receber uma votação sobre esta resposta 6 anos depois de postar o que me levou a reler a pergunta.

A function hash dada na questão não é um bom hash para 26 milhões de inputs.

Acrescenta um [0] + a [1] eb [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 possíveis valores de hash. Com 26 milhões de inputs, isso significa uma média de cerca de 1639 inputs por valor de hash. Isso é muitas e muitas colisões, exigindo muitas pesquisas sequenciais por meio de listas vinculadas.

O OP diz que ordens diferentes dentro de array a e array b devem ser consideradas iguais, ie [[1,2], [3,4,5]]. Igual ([[2,1], [5,3,4] ]), e assim, para cumprir o contrato, eles devem ter códigos hash iguais. OK. Ainda assim, existem muito mais que 15.000 valores possíveis. Sua segunda function hash proposta é muito melhor, dando um alcance mais amplo.

Embora, como alguém comentou, pareça inadequado para uma function hash alterar outros dados. Seria mais sensato “normalizar” o object quando ele é criado ou fazer com que a function hash funcione a partir de cópias dos arrays. Além disso, usar um loop para calcular constantes toda vez que a function é 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; 

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

Além disso, o primeiro rascunho em uma function hash possui vários cálculos que não fazem nada para adicionar ao intervalo de saídas. Note que ele primeiro define hash = 503 do que multiplica por 5381 antes mesmo de considerar valores da class. Então … na verdade, ele adiciona 503 * 5381 a todos os valores. O que isso faz? Adicionando uma constante a cada valor de hash apenas grava ciclos de cpu sem realizar nada útil. Lição aqui: Adicionar complexidade a uma function hash não é o objective. O objective é obter uma ampla gama de valores diferentes, não apenas para adicionar complexidade em prol da complexidade.

Minha primeira ideia é ter certeza de que você está inicializando seu HashMap apropriadamente. Do JavaDocs para HashMap :

Uma instância do HashMap possui dois parâmetros que afetam seu desempenho: capacidade inicial e fator de carga. A capacidade é o número de depósitos na tabela de hash e a capacidade inicial é simplesmente a capacidade no momento em que a tabela de hash é criada. O fator de carga é uma medida de como a tabela hash é permitida antes que sua capacidade seja aumentada automaticamente. Quando o número de inputs na tabela de hash excede o produto do fator de carga e a capacidade atual, a tabela de hash é reexposta (isto é, as estruturas de dados internas são recriadas) para que a tabela de hash tenha aproximadamente o dobro do número de buckets.

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

Eu sugeriria uma abordagem em três frentes:

  1. Execute Java com mais memory: java -Xmx256M por exemplo, para executar com 256 Megabytes. Use mais se necessário e você tem muita memory RAM.

  2. Armazene em cache seus valores de hash calculados, conforme sugerido por outro pôster, para que cada object 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}, como seria, onde a = {1, 0}, tudo o mais 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 de seus dados.

Entrando na área cinza de “on / off topic”, mas necessário para eliminar a confusão sobre Oscar Reyes, sugestão de que mais colisões hash é uma coisa boa, porque reduz o número de elementos no HashMap. Eu posso entender mal o que Oscar está dizendo, mas não pareço ser o único: kdgregory, delfuego, Nash0 e eu todos parecemos compartilhar o mesmo (mal) entendimento.

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

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

Independentemente de qualquer entendimento ou mal-entendido, o que acontece é que instâncias diferentes da mesma class não são inseridas apenas uma vez no HashMap se elas 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 objects iguais tenham o mesmo hashcode; no entanto, não requer que objects desiguais tenham códigos de hash diferentes (embora isso possa ser desejável por outros motivos) [1].

O exemplo pastebin.com/f20af40b9 (que Oscar refere-se a pelo menos duas vezes) segue, mas modificou um pouco para usar asserções JUnit ao invés de printlines. Este exemplo é usado para suportar a proposta de que os mesmos hashcodes causam colisões e quando as classs são as mesmas, apenas uma input é 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 do pastebin negligencia é o fato de que ambos s e s são iguais: ambos são a string “ese”. Assim, inserir ou obter o conteúdo do mapa usando s ou ese ou "ese" como chave são todos equivalentes porque s.equals(ese) && s.equals("ese") .

Um segundo teste demonstra que é errado concluir que hashcodes idênticos na mesma class é a razão pela qual a chave -> value s -> 1 é sobrescrita por ese -> 2 quando map.put(ese, 2) é chamado no teste um. No teste dois, se ese ainda tem o mesmo hashcode (como verificado por assertEquals(s.hashCode(), ese.hashCode()); ) E eles são da mesma class. No entanto, s e ese são instâncias de MyString neste teste, não instâncias de String Java – com a única diferença relevante para este teste sendo o igual: String s equals String ese no teste um acima, enquanto MyStrings s does not equal MyString ese no 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; } } 

Baseado em um comentário posterior, Oscar parece reverter o que ele disse anteriormente e reconhece a importância de iguais. No entanto, ainda parece que a noção de que equals é o que importa, não a “mesma class”, não é clara (ênfase minha):

“Não realmente. A lista é criada apenas se o hash for o mesmo, mas a chave é diferente. Por exemplo, se uma String fornecer hashcode 2345 e Integer fornecer o mesmo hashcode 2345, o inteiro será inserido na lista porque String. equals (Integer) é false.Mas se você tiver a mesma class (ou pelo menos .equals retorna true) então a mesma input é usada.Por exemplo, new String (“one”) e `new String (” one “) usado como chaves, vai usar a mesma input.Na verdade, este é o ponto inteiro de HashMap em primeiro lugar! Veja por si mesmo: pastebin.com/f20af40b9 – Oscar Reyes “

versus comentários anteriores que abordam explicitamente a importância da class idêntica e do mesmo hashcode, sem menção de iguais:

“@delfuego: Veja por si mesmo: pastebin.com/f20af40b9 Então, nesta questão a mesma class está sendo usada (espere um minuto, a mesma class está sendo usada certo?) O que implica que quando o mesmo hash é usado a mesma input é usado e não há “lista” de inputs – Oscar Reyes “

ou

“Na verdade, isso aumentaria o desempenho. Quanto mais colisões eq menos inputs no hashtable eq. Menos trabalho para fazer. Não é o hash (que parece bem) nem o hashtable (que funciona muito bem) Eu aposto que está no object criação onde o desempenho é degradante – Oscar Reyes “

ou

“@kdgregory: Sim, mas somente se a colisão acontece com classs diferentes, para a mesma class (que é o caso) a mesma input é usada. – Oscar Reyes”

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


[1] – From Effective Java, segunda edição por Joshua Bloch:

  • Sempre que é invocado no mesmo object mais de uma vez durante a execução de um aplicativo, o método hashCode deve retornar consistentemente o mesmo número inteiro, desde que nenhuma informação usada nas comparações de igual no object seja modificada. Esse inteiro não precisa permanecer consistente de uma execução de um aplicativo para outra execução do mesmo aplicativo.

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

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

Se as matrizes no hashCode publicado forem bytes, você provavelmente acabará com várias 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 esses e você terá um limite superior de 400.000 combinações exclusivas, supondo que seus dados estejam perfeitamente distribuídos entre todos os valores possíveis de cada byte. Se os seus dados forem regulares, você provavelmente terá resultados muito menos exclusivos desse método.

HashMap tem capacidade inicial e o desempenho do HashMap depende muito do hashCode que produz objects subjacentes.

Tente ajustar os dois.

Se as chaves tiverem algum 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 índices: 1-1.000.000 -> Mapa1 1.000.000-2.000.000 -> Mapa2

Então você estará fazendo duas pesquisas, mas o conjunto de chaves seria de 1.000.000 contra 28.000.000. Você pode facilmente fazer isso com padrões de picada também.

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

Se os dois arrays de byte que você mencionou forem sua chave inteira, os valores estão no intervalo de 0 a 51, único e a ordem dentro dos arrays a e b é insignificante, minha matemática me diz que há apenas 26 milhões de permutações possíveis e É provável que você esteja tentando preencher o mapa com valores para todas as chaves possíveis.

Nesse caso, tanto o preenchimento quanto a recuperação de valores do seu armazenamento de dados seriam, obviamente, muito mais rápidos 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 grandes mapas:

  1. Como discutido em outras postagens, com um bom hashCode (), inputs de 26M em um mapa não são nada demais.
  2. No entanto, um problema potencialmente oculto aqui é o impacto de mapas gigantes no GC.

Eu estou supondo que esses mapas são de longa duração. ou seja, você os preenche e ficam por toda a duração do aplicativo. Eu também estou supondo que o aplicativo em si é de longa duração – como um servidor de algum tipo.

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

Não conheço uma ótima solução para esse problema. Idéias:

  • Às vezes, é possível ajustar o GC e os tamanhos de heap para “evitar” principalmente os GCs completos.
  • Se o conteúdo do seu mapa for muito churn, você pode tentar o FastMap do Javolution – ele pode agrupar objects Entry, o que poderia diminuir a frequência de collections completas.
  • Você poderia criar seu próprio mapa implícito e fazer gerenciamento explícito de memory em byte [] (isto é, trocar a cpu por uma latência mais previsível, serializando milhões de objects em um único byte [] – ugh!)
  • Não use Java para esta parte – fale com algum tipo de DB na memory previsível em um soquete
  • Espero que o novo colecionador G1 ajude (principalmente se aplica ao caso de alta rotatividade)

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


Você pode tentar usar um database na memory como o HSQLDB .

No meu caso, quero criar um mapa com 26 milhões de inputs. Usando o Java HashMap padrão, a taxa de put se torna 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 não consegui construir o RBTree para 1 milhão de nós (como seus resultados com o HashMap).
  • Usando “Prime Tree”, minha estrutura de dados do algoritmo. Eu poderia construir uma tree / mapa para 10 milhões de nós dentro de 21,29 segundos (RAM: 1,97 Gb). O custo do key-value de pesquisa é O (1).

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


Então, o que é o #PrimeTree? Em suma, é uma estrutura de dados em tree, como Árvore Binária, com números de ramos são números primos (em vez de “2” -binário).

O SQLite permite que você use na memory.

Você já pensou em usar um database embutido para fazer isso? Olhe para Berkeley DB . É de código aberto, pertencente à Oracle agora.

Ele armazena tudo como chave -> par de 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 chaves, capacidade inicial do Map, implementação correta do Map, etc., como muitas outras respostas descrevem.

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

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

Outra opção seria um mecanismo de database mais leve que o SQL RDBMS completo. Algo como Berkeley DB , talvez.

Note que eu pessoalmente não tenho experiência com o desempenho desses produtos, mas eles podem valer a pena.

Você pode tentar armazenar em cache o código hash calculado para o object-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 depois que o hashCode tiver sido calculado pela primeira vez.

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

Outro pôster já apontou que a implementação do hashcode resultará em muitas colisões devido à maneira como você está adicionando valores juntos. Eu estou disposto a ser isso, se você olhar para o object HashMap em um depurador, você verá que você tem talvez 200 valores de hash distintos, com cadeias de bucket extremamente longas.

Se você sempre tiver valores no intervalo 0..51, cada um desses valores levará 6 bits para representar. If you always have 5 values, you can create a 30-bit hashcode with left-shifts and additions:

  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; 

The left-shift is fast, but will leave you with hashcodes that aren't evenly distributed (because 6 bits implies a range 0..63). An alternative is to multiply the hash by 51 and add each value. This still won't be perfectly distributed (eg, {2,0} and {1,52} will collide), and will be slower than the shift.

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

As pointed out, your hashcode implementation has too many collisions, and fixing it should result in decent performance. Moreover, caching hashCodes and implementing equals efficiently will help.

If you need to optimize even further:

By your description, there are only (52 * 51 / 2) * (52 * 51 * 50 / 6) = 29304600 different keys (of which 26000000, ie about 90%, will be present). Therefore, you can design a hash function without any collisions, and use a simple array rather than a hashmap to hold your data, reducing memory consumption and increasing lookup speed:

 T[] array = new T[Key.maxHashCode]; void put(Key k, T value) { array[k.hashCode()] = value; T get(Key k) { return array[k.hashCode()]; } 

(Generally, it is impossible to design an efficient, collision-free hash function that clusters well, which is why a HashMap will tolerate collisions, which incurs some overhead)

Assuming a and b are sorted, you might use the following hash function:

 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; 

I think this is collision-free. Proving this is left as an exercise for the mathematically inclined reader.

In Effective Java: Programming Language Guide (Java Series)

Chapter 3 you can find good rules to follow when computing hashCode().

Specially:

If the field is an array, treat it as if each element were a separate field. That is, compute a hash code for each significant element by applying these rules recursively, and combine these values per step 2.b. If every element in an array field is significant, you can use one of the Arrays.hashCode methods added in release 1.5.

Allocate a large map in the beginning. If you know it will have 26 million entries and you have the memory for it, do a new HashMap(30000000) .

Are you sure, you have enough memory for 26 million entries with 26 million keys and values? This sounds like a lot memory to me. Are you sure that the garbage collection is doing still fine at your 2 to 3 million mark? I could imagine that as a bottleneck.

You could try two things:

  • Make your hashCode method return something simpler and more effective such as a consecutive int

  • Initialize your map as:

     Map map = new HashMap( 30000000, .95f ); 

Those two actions will reduce tremendously the amount of rehashing the structure is doing, and are pretty easy to test I think.

If that doesn’t work, consider using a different storage such a RDBMS.

EDITAR

Is strange that setting the initial capacity reduce the performance in your case.

See from the javadocs :

If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

I made a microbeachmark ( which is not by anymeans definitive but at least proves this point )

 $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 $ 

So, using the initial capacity drops from 21s to 16s because of the rehasing. That leave us with your hashCode method as an "area of opportunity" 😉

EDITAR

Is not the HashMap

As per your last edition.

I think you should really profile your application and see where it the memory/cpu is being consumed.

I have created a class implementing your same hashCode

That hash code give millions of collisions, then the entries in the HashMap is reduced dramatically.

I pass from 21s, 16s in my previous test to 10s and 8s. The reason is because the hashCode provokes a high number of collisions and you are not storing the 26M objects you think but a much significant lower number ( about 20k I would say ) So:

The problems IS NOT THE HASHMAP is somewhere else in your code.

It is about time to get a profiler and find out where. I would think it is on the creation of the item or probably you're writing to disk or receiving data from the network.

Here's my implementation of your class.

note I didn't use a 0-51 range as you did but -126 to 127 for my values and admits repeated, that's because I did this test before you updated your question

The only difference is that your class will have more collisions thus less items stored in the map.

 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 ); } } 

Using this class has Key for the previous program

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

gives me:

 real 0m11.188s user 0m10.784s sys 0m0.261s real 0m9.348s user 0m9.071s sys 0m0.161s 

I did a small test a while back with a list vs a hashmap, funny thing was iterating through the list and finding the object took the same amount of time in milliseconds as using the hashmaps get function… just an fyi. Oh yeah memory is a big issue when working with hashmaps that size.

The popular hashing methods used are not really very good for large sets and, as pointed out above, the hash used is particularly bad. Better is to use a hash algorithm with high mixing and coverage such as BuzHash (sample implementation at http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )