optimizar optimizacion listas intermedio codigo aplicacion java performance optimization map hashmap

optimizacion - Optimización del rendimiento de Java HashMap/alternativa



optimizacion en java (25)

Quiero crear un HashMap grande pero el rendimiento de put() no es lo suficientemente bueno. ¿Algunas ideas?

Otras sugerencias de estructura de datos son bienvenidas, pero necesito la función de búsqueda de un mapa de Java:

map.get(key)

En mi caso, quiero crear un mapa con 26 millones de entradas. Al utilizar Java HashMap estándar, la velocidad de publicación se vuelve insoportablemente lenta después de 2-3 millones de inserciones.

Además, ¿alguien sabe si el uso de diferentes distribuciones de código hash para las claves podría ayudar?

Mi método de código hash:

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

Estoy usando la propiedad asociativa de adición para asegurar que objetos iguales tengan el mismo código hash. Las matrices son bytes con valores en el rango de 0 a 51. Los valores solo se usan una vez en cualquiera de las matrices. Los objetos son iguales si las matrices a contienen los mismos valores (en cualquier orden) y lo mismo ocurre con la matriz b. Entonces a = {0,1} b = {45,12,33} y a = {1,0} b = {33,45,12} son iguales.

EDITAR, algunas notas:

  • Algunas personas han criticado el uso de un mapa hash u otra estructura de datos para almacenar 26 millones de entradas. No puedo ver por qué esto parece extraño. Parece un problema clásico de estructuras de datos y algoritmos para mí. Tengo 26 millones de elementos y quiero poder insertarlos y buscarlos rápidamente desde una estructura de datos: dame la estructura de datos y los algoritmos.

  • Establecer la capacidad inicial del Java HashMap predeterminado en 26 millones disminuye el rendimiento.

  • Algunas personas han sugerido usar bases de datos, en algunas otras situaciones que definitivamente es la opción inteligente. Pero realmente estoy preguntando sobre estructuras de datos y algoritmos, una base de datos completa sería excesiva y mucho más lenta que una buena solución de estructura de datos (después de todo, la base de datos es solo software pero tendría comunicación y posiblemente sobrecarga de disco).

En mi caso, quiero crear un mapa con 26 millones de entradas. Al utilizar Java HashMap estándar, la velocidad de publicación se vuelve insoportablemente lenta después de 2-3 millones de inserciones.

De mi experimento (proyecto de estudiante en 2009):

  • Construí un Red Black Tree para 100.000 nodos de 1 a 100.000. Tardó 785,68 segundos (13 minutos). Y no pude crear RBTree para 1 millón de nodos (como sus resultados con HashMap).
  • Usando "Prime Tree", mi estructura de datos de algoritmo. Podría construir un árbol / mapa para 10 millones de nodos en 21.29 segundos (RAM: 1.97Gb). El valor de clave-valor de búsqueda es O (1).

Nota: "Prime Tree" funciona mejor en "teclas continuas" de 1 a 10 millones. Para trabajar con claves como HashMap, necesitamos algunos ajustes menores.

Entonces, ¿qué es #PrimeTree? En resumen, es una estructura de datos de árbol como Binary Tree, con números de ramas que son números primos (en lugar de "2" -binary).

¿Ha considerado usar una base de datos incrustada para hacer esto? Mira Berkeley DB . Es de código abierto, propiedad de Oracle ahora.

Almacena todo como par Key-> Value, NO es un RDBMS. y pretende ser rápido.

Como mucha gente señaló que el método hashCode() era el culpable. Solo generó alrededor de 20,000 códigos para 26 millones de objetos distintos. Eso es un promedio de 1.300 objetos por cubo de hash = muy, muy malo. Sin embargo, si convierto las dos matrices en un número en la base 52, tengo la garantía de obtener un código hash único 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; }

Las matrices se ordenan para garantizar que este método cumpla con el contrato hashCode() que los objetos iguales tienen el mismo código hash. Usando el método anterior, la cantidad promedio de puts por segundo sobre bloques de 100,000 puts, 100,000 a 2,000,000 fue:

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 el nuevo método da:

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

Mucho mejor. El viejo método se detuvo rápidamente, mientras que el nuevo mantiene un buen rendimiento.

Entrar en el área gris del "tema de encendido / apagado", pero necesario para eliminar la confusión con respecto a la sugerencia de Oscar Reyes de que más colisiones hash es algo bueno porque reduce la cantidad de elementos en el HashMap. Puedo malinterpretar lo que dice Óscar, pero no parezco ser el único: kdgregory, delfuego, Nash0, y todos parezco compartir el mismo (mal) entendimiento.

Si entiendo lo que Oscar dice sobre la misma clase con el mismo código hash, él propone que solo una instancia de una clase con un código hash determinado se insertará en el HashMap. Por ejemplo, si tengo una instancia de SomeClass con un hashcode de 1 y una segunda instancia de SomeClass con un hashcode de 1, solo se inserta una instancia de SomeClass.

El ejemplo de Java pastebin en pastebin.com/f20af40b9 parece indicar que lo anterior resume correctamente lo que Oscar propone.

Independientemente de cualquier entendimiento o malentendido, lo que ocurre es que las diferentes instancias de la misma clase no se insertan una sola vez en el HashMap si tienen el mismo código hash, no hasta que se determine si las claves son iguales o no. El contrato de código hash requiere que objetos iguales tengan el mismo código hash; sin embargo, no requiere que objetos desiguales tengan códigos hash diferentes (aunque esto puede ser deseable por otras razones) [1].

El ejemplo pastebin.com/f20af40b9 (al que Oscar se refiere al menos dos veces) se muestra a continuación, pero modificado ligeramente para usar aserciones JUnit en lugar de líneas impresas. Este ejemplo se utiliza para respaldar la propuesta de que los mismos códigos hash causan colisiones y cuando las clases son las mismas, solo se crea una entrada (por ejemplo, solo una cadena en este 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; } }

Sin embargo, el hashcode no es la historia completa. Lo que el ejemplo de pastebin descuida es el hecho de que tanto s como ese son iguales: ambos son la cadena "ese". Por lo tanto, insertar u obtener el contenido del mapa usando s o ese o "ese" como clave son todos equivalentes porque s.equals(ese) && s.equals("ese") .

Una segunda prueba demuestra que es erróneo concluir que códigos hash idénticos en la misma clase es la razón por la cual la clave -> valor s -> 1 es sobrescrita por ese -> 2 cuando se map.put(ese, 2) en la prueba uno. En la prueba dos, s y ese todavía tienen el mismo assertEquals(s.hashCode(), ese.hashCode()); (como verificado por assertEquals(s.hashCode(), ese.hashCode()); ) AND son de la misma clase. Sin embargo, s y ese son instancias de MyString en esta prueba, no instancias de Java String , con la única diferencia relevante para esta prueba siendo las iguales: String s equals String ese en la prueba uno anterior, mientras que MyStrings s does not equal MyString ese en la prueba dos :

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

Basado en un comentario posterior, Oscar parece revertir lo que dijo antes y reconoce la importancia de los iguales. Sin embargo, todavía parece que la noción de que lo que importa es la igualdad, no la "misma clase", no está claro (el énfasis es mío):

"No realmente. La lista se crea solo si el hash es el mismo, pero la clave es diferente. Por ejemplo, si un String da un código hash 2345 e Integer da el mismo código hash 2345, entonces el entero se inserta en la lista porque String. equals (Integer) es falso. Pero si tiene la misma clase (o al menos .equals devuelve true), entonces se utiliza la misma entrada. Por ejemplo, new String ("one") y "new String (" one ") utilizados como claves, usará la misma entrada. ¡En realidad, este es el punto principal de HashMap en primer lugar! Compruébelo usted mismo: pastebin.com/f20af40b9 - Oscar Reyes "

versus comentarios anteriores que abordan explícitamente la importancia de la clase idéntica y el mismo código hash, sin mencionar a iguales:

"@delfuego: compruébalo tú mismo: pastebin.com/f20af40b9 Entonces, en esta pregunta, se está utilizando la misma clase (espere un minuto, se usa la misma clase, ¿verdad?) Lo cual implica que cuando se usa el mismo hash, se usa la misma entrada se usa y no hay "lista" de entradas. - Oscar Reyes "

o

"En realidad, esto aumentaría el rendimiento. Cuantas más colisiones eq menos entradas en la tabla hash menos trabajo por hacer. ¿No es el hash (que se ve bien) ni la tabla hash (que funciona bien) Apuesto a que está en el objeto creación donde el rendimiento es degradante. - Oscar Reyes "

o

"@kdgregory: Sí, pero solo si la colisión ocurre con diferentes clases, para la misma clase (que es el caso) se usa la misma entrada. - Oscar Reyes"

De nuevo, puedo malinterpretar lo que Oscar realmente estaba tratando de decir. Sin embargo, sus comentarios originales han causado suficiente confusión que parece prudente aclarar todo con algunas pruebas explícitas para que no haya dudas persistentes.

[1] - De Effective Java, segunda edición de Joshua Bloch:

  • Cada vez que se invoca en el mismo objeto más de una vez durante una ejecución de una aplicación, el método hashCode debe devolver consistentemente el mismo entero, siempre que no se modifique la información utilizada en las comparaciones de igual en el objeto. Este entero no necesita ser consistente desde una ejecución de una aplicación hasta otra ejecución de la misma aplicación.

  • Si dos objetos son iguales de acuerdo con el método igual s (Obj ect), entonces llamar al método hashCode en cada uno de los dos objetos debe producir el mismo resultado entero.

  • No es necesario que si dos objetos son desiguales de acuerdo con el método igual de s (Objeto), al llamar al método hashCode en cada uno de los dos objetos se produzcan resultados enteros distintos. Sin embargo, el programador debe tener en cuenta que la producción de resultados enteros distintos para objetos desiguales puede mejorar el rendimiento de las tablas hash.

HashMap tiene capacidad inicial y el rendimiento de HashMap depende mucho de hashCode que produzca objetos subyacentes.

Intenta ajustar ambos.

Llegué tarde aquí, pero un par de comentarios sobre mapas grandes:

  1. Como se discutió extensamente en otras publicaciones, con un buen hashCode (), 26M entradas en un Mapa no es gran cosa.
  2. Sin embargo, un problema potencialmente oculto aquí es el impacto de GC de los mapas gigantes.

Estoy asumiendo que estos mapas son de larga vida. es decir, las rellena y se quedan durante la aplicación. También estoy asumiendo que la aplicación en sí es de larga duración, como un servidor de algún tipo.

Cada entrada en un HashMap de Java requiere tres objetos: la clave, el valor y la Entrada que los une. Así que 26M entradas en el mapa significa 26M * 3 == 78M objetos. Esto está bien hasta que golpees un GC completo. Entonces tienes un problema de pausa mundial. El GC observará cada uno de los objetos de 78M y determinará que están todos vivos. 78M + objetos son solo muchos objetos para mirar. Si su aplicación puede tolerar ocasionalmente pausas largas (quizás muchos segundos), no hay problema. Si está tratando de lograr cualquier garantía de latencia, podría tener un problema importante (por supuesto, si desea garantías de latencia, Java no es la plataforma para elegir :)) Si los valores en sus mapas se agitan rápidamente, puede terminar con recopilaciones completas frecuentes que agrava el problema en gran medida.

No sé de una gran solución a este problema. Ideas:

  • A veces es posible ajustar el GC y los tamaños de pila para "evitar" la mayoría de los GC.
  • Si el contenido de su mapa se agita mucho, puede probar la FastMap de Javolution : puede agrupar objetos de entrada, lo que podría reducir la frecuencia de la recopilación completa.
  • Podrías crear tu propia impl de mapa y hacer una gestión explícita de la memoria en byte [] (es decir, cambiar la CPU por una latencia más predecible al serializar millones de objetos en un solo byte [] - ugh!)
  • No use Java para esta parte, hable con un tipo de DB predecible en memoria en un socket
  • Espero que el nuevo coleccionista G1 ayude (principalmente se aplica al caso de alta rotación)

Solo algunos pensamientos de alguien que ha pasado mucho tiempo con mapas gigantes en Java.

Mi primera idea es asegurarme de que esté inicializando su HashMap de manera apropiada. De los JavaDocs para HashMap :

Una instancia de HashMap tiene dos parámetros que afectan su rendimiento: capacidad inicial y factor de carga. La capacidad es el número de segmentos en la tabla hash, y la capacidad inicial es simplemente la capacidad en el momento en que se crea la tabla hash. El factor de carga es una medida de cuán completa está permitida la tabla hash antes de que su capacidad aumente automáticamente. Cuando el número de entradas en la tabla hash excede el producto del factor de carga y la capacidad actual, la tabla hash se vuelve a generar (es decir, se reconstruyen las estructuras internas de datos) para que la tabla hash tenga aproximadamente el doble de cubetas.

Entonces, si comienzas con un HashMap demasiado pequeño, entonces cada vez que necesite cambiar el tamaño, todos los hashes se vuelven a calcular ... lo que podría ser lo que sientes cuando llegues al punto de inserción de 2-3 millones.

Para profundizar en Pascal: ¿Entiendes cómo funciona un HashMap? Tienes un cierto número de ranuras en tu tabla hash. Se encuentra el valor de hash para cada clave, y luego se asigna a una entrada en la tabla. Si dos valores hash se asignan a la misma entrada, una "colisión hash", HashMap crea una lista vinculada.

Las colisiones hash pueden matar el rendimiento de un mapa hash. En el caso extremo, si todas sus claves tienen el mismo código hash, o si tienen diferentes códigos hash pero todas se asignan a la misma ranura, su mapa hash se convierte en una lista vinculada.

Entonces, si está viendo problemas de rendimiento, lo primero que comprobaré es: ¿estoy obteniendo una distribución de códigos hash de aspecto aleatorio? Si no, necesitas una mejor función hash. Bueno, "mejor" en este caso puede significar "mejor para mi conjunto particular de datos". Como, supongamos que estaba trabajando con cadenas, y tomó la longitud de la cadena para el valor hash. (No cómo funciona String.hashCode de Java, pero solo estoy inventando un ejemplo simple.) Si sus cadenas tienen longitudes muy variables, de 1 a 10.000, y están distribuidas de manera bastante uniforme en ese rango, esto podría ser una muy buena función hash. Pero si tus cadenas tienen 1 o 2 caracteres, esta sería una función hash muy mala.

Editar: Debo añadir: cada vez que agrega una nueva entrada, HashMap comprueba si se trata de un duplicado. Cuando hay una colisión hash, tiene que comparar la clave entrante con cada clave asignada a esa ranura. Entonces, en el peor de los casos donde todo se reduce a una sola ranura, la segunda se compara con la primera, la tercera se compara con el n.º 1 y el n.º 2, la cuarta se compara con el n.º 1, el n.º 2 y el número 3 , etc. Cuando llegas a la clave # 1 millón, has hecho más de un billón de copias.

@Oscar: Umm, no veo cómo eso es un "no realmente". Es más como un "déjame aclarar". Pero sí, es cierto que si realiza una nueva entrada con la misma clave que una entrada existente, esto sobrescribe la primera entrada. Eso es lo que quise decir cuando hablé sobre buscar duplicados en el último párrafo: cada vez que una clave se acumula en el mismo espacio, HashMap debe verificar si es un duplicado de una clave existente, o si están justo en el mismo espacio por coincidencia de la función hash. No sé si ese es el "punto" de un HashMap: diría que el "punto principal" es que puedes recuperar elementos por clave rápidamente.

Pero de todos modos, eso no afecta el "punto completo" que estaba tratando de hacer: cuando tienes dos teclas, sí, claves diferentes, no se vuelve a mostrar la misma clave, ese mapa está en la misma ranura de la tabla , HashMap crea una lista vinculada. Luego, como tiene que verificar cada nueva clave para ver si de hecho es un duplicado de una clave existente, cada intento de agregar una nueva entrada que se asocie a este mismo intervalo debe buscar en la lista vinculada examinar cada entrada existente para ver si esto es un duplicado de una clave vista anteriormente, o si se trata de una nueva clave.

Actualizar mucho después de la publicación original

Acabo de recibir una votación positiva sobre esta respuesta 6 años después de la publicación, lo que me llevó a volver a leer la pregunta.

La función hash dada en la pregunta no es un buen hash para 26 millones de entradas.

Agrega juntos [0] + a [1] y b [0] + b [1] + b [2]. Él dice que los valores de cada byte varían de 0 a 51, por lo que solo da (51 * 2 + 1) * (51 * 3 + 1) = 15,862 posibles valores hash. Con 26 millones de entradas, esto significa un promedio de alrededor de 1639 entradas por valor de hash. Son muchas las colisiones que requieren muchas búsquedas secuenciales a través de listas vinculadas.

El OP dice que los diferentes órdenes dentro de la matriz a y la matriz b deben considerarse iguales, es decir [[1,2], [3,4,5]] iguales ([[2,1], [5,3,4] ]), y para cumplir el contrato deben tener códigos hash iguales. Bueno. Aún así, hay mucho más de 15,000 valores posibles. Su segunda función hash propuesta es mucho mejor, dando un rango más amplio.

Aunque, como comentó otra persona, parece inapropiado que una función hash cambie otros datos. Tendría más sentido "normalizar" el objeto cuando se crea, o hacer que la función de almohadilla funcione a partir de copias de las matrices. Además, el uso de un bucle para calcular constantes cada vez a través de la función es ineficiente. Como solo hay cuatro valores aquí, habría escrito

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

lo que haría que el compilador realice el cálculo una vez en el tiempo de compilación; o tiene 4 constantes estáticas definidas en la clase.

Además, el primer borrador en una función hash tiene varios cálculos que no hacen nada para agregar al rango de salidas. Tenga en cuenta que primero establece hash = 503 que multiplica por 5381 incluso antes de considerar los valores de la clase. Entonces ... en efecto, agrega 503 * 5381 a cada valor. ¿Qué logra esto? Agregar una constante a cada valor hash simplemente quema ciclos de CPU sin lograr nada útil. Lección aquí: Agregar complejidad a una función hash no es el objetivo. El objetivo es obtener una amplia gama de valores diferentes, no solo para agregar complejidad en aras de la complejidad.

Primero, debe verificar que esté utilizando correctamente el mapa, buen método hashCode () para las claves, capacidad inicial para el mapa, implementación correcta del mapa, etc., como describen muchas otras respuestas.

Luego sugeriría usar un generador de perfiles para ver qué está sucediendo realmente y dónde se gasta el tiempo de ejecución. Es, por ejemplo, el método hashCode () ejecutado por miles de millones de veces?

Si eso no ayuda, ¿qué hay de usar algo como EHCache o memcached ? Sí, son productos para el almacenamiento en caché pero puede configurarlos para que tengan suficiente capacidad y nunca desalojarán ningún valor del almacenamiento en caché.

Another option would be some database engine that is lighter weight than full SQL RDBMS. Something like Berkeley DB , maybe.

Note, that I have personally no experience of these products'' performance, but they could be worth the try.

Puede intentar usar una base de datos en memoria como HSQLDB .

Si las matrices en su hashCode publicado son bytes, es probable que termine con muchos duplicados.

a [0] + a [1] siempre estará entre 0 y 512. al agregar las b siempre se obtendrá un número entre 0 y 768. multiplíquelas y obtendrá un límite superior de 400,000 combinaciones únicas, suponiendo que sus datos estén perfectamente distribuidos entre cada valor posible de cada byte. Si sus datos son regulares, es probable que tenga resultados mucho menos únicos de este método.

Si las teclas tienen algún patrón, puedes dividir el mapa en mapas más pequeños y tener un mapa de índice.

Ejemplo: Llaves: 1,2,3, .... n 28 mapas de 1 millón cada uno. Mapa de índice: 1-1,000,000 -> Mapa1 1,000,000-2,000,000 -> Map2

Así que harás dos búsquedas, pero la clave establecida sería de 1,000,000 vs 28,000,000. También puedes hacer esto fácilmente con patrones de picadura.

Si las teclas son completamente aleatorias, esto no funcionará

Si los dos arreglos de bytes que mencionas son tu clave completa, los valores están en el rango 0-51, únicos y el orden dentro de las matrices a y b es insignificante, mis cálculos me dicen que solo hay unos 26 millones de posibles permutaciones y que probablemente estés tratando de llenar el mapa con valores para todas las claves posibles.

En este caso, tanto los valores de llenado como de recuperación de su almacén de datos serían, por supuesto, mucho más rápidos si utiliza un conjunto en lugar de un HashMap e indexa de 0 a 25989599.

Sugeriría un enfoque triple:

  1. Ejecute Java con más memoria: java -Xmx256M por ejemplo, para ejecutar con 256 megabytes. Usa más si es necesario y tienes mucha RAM.

  2. Guarde en caché los valores de hash calculados según lo sugerido por otro póster, de modo que cada objeto solo calcule su valor de hash una vez.

  3. Use un mejor algoritmo hash. El que publicaste devolvería el mismo hash donde a = {0, 1} como lo haría a = {1, 0}, siendo igual todo lo demás.

Utiliza lo que Java te da gratis.

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

Estoy bastante seguro de que tiene muchas menos posibilidades de chocar que su método hashCode existente, aunque depende de la naturaleza exacta de sus datos.

Una cosa que noto en su método hashCode() es que el orden de los elementos en las matrices a[] y b[] no importa. Por lo tanto, (a[]={1,2,3}, b[]={99,100}) hará hash al mismo valor que (a[]={3,1,2}, b[]={100,99}) . En realidad, todas las teclas k1 y k2 donde sum(k1.a)==sum(k2.a) y sum(k1.b)=sum(k2.b) provocarán colisiones. Sugiero asignar un peso a cada posición de la matriz:

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

donde, c0 , c1 y c3 son constantes distintas (puede usar constantes diferentes para b si es necesario). Eso debería igualar las cosas un poco más.

SQLite te permite usarlo en la memoria.

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

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.

Another poster already pointed out that your hashcode implementation will result in a lot of collisions due to the way that you''re adding values together. I''m willing to be that, if you look at the HashMap object in a debugger, you''ll find that you have maybe 200 distinct hash values, with extremely long bucket chains.

If you always have values in the range 0..51, each of those values will take 6 bits to represent. 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.

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.

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.

You could try to cache computed hash code to the key object.

Algo como esto:

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

Of course you have to be careful not to change contents of the key after the hashCode has been calculated for the first time.

Edit: It seems that caching has code values is not worthwhile when you are adding each key only once to a map. In some other situation this could be useful.