Quiero crear un HashMap grande pero el put()rendimiento 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. Usando el Java HashMap estándar, la tasa de colocació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 la suma para asegurar que los 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 veo por qué esto parecería extraño. Me parece un problema clásico de estructuras de datos y algoritmos. Tengo 26 millones de elementos y quiero poder insertarlos rápidamente y buscarlos en una estructura de datos: dame la estructura de datos y los algoritmos.

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

• Algunas personas han sugerido el uso de bases de datos, en algunas otras situaciones esa es definitivamente la opción inteligente. Pero realmente estoy haciendo una pregunta 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).

Como muchas personas señalaron, el hashCode()método fue el culpable. Solo generaba alrededor de 20.000 códigos para 26 millones de objetos distintos. Eso es un promedio de 1300 objetos por cubo de hash = muy, muy malo. Sin embargo, si convierto las dos matrices en un número en 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 estos métodos cumplan con el hashCode()contrato de que los objetos iguales tienen el mismo código hash. Usando el método antiguo, el número promedio de put por segundo sobre bloques de 100,000 put, 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

El uso del 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 método antiguo se redujo muy rápidamente mientras que el nuevo mantiene un buen rendimiento.

Una cosa que noto en su hashCode()método es que el orden de los elementos en las matrices a[]y b[]no importa. Por (a[]={1,2,3}, b[]={99,100})lo tanto , el hash tendrá el mismo valor que (a[]={3,1,2}, b[]={100,99}). En realidad, todas las llaves k1y k2dónde sum(k1.a)==sum(k2.a)y sum(k1.b)=sum(k2.b)resultarán en 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, c1y c3son distintas constantes (se pueden utilizar diferentes constantes de bsi es necesario). Eso debería igualar un poco más las cosas.

Para desarrollar Pascal: ¿Entiendes cómo funciona un HashMap? Tienes cierto número de espacios en tu tabla hash. Se encuentra el valor 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 acabar con 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 todos se asignan a la misma ranura, entonces su mapa hash se convierte en una lista vinculada.

Entonces, si observa problemas de rendimiento, lo primero que verificaría es: ¿obtengo una distribución de códigos hash de aspecto aleatorio? Si no es así, necesita una mejor función hash. Bueno, "mejor" en este caso puede significar "mejor para mi conjunto particular de datos". Supongamos que está trabajando con cadenas y tomó la longitud de la cadena para el valor hash. (No es 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, entonces esto podría ser muy bueno función hash. Pero si sus cadenas son todas de 1 o 2 caracteres, esta sería una función hash muy mala.

Editar: Debo agregar: Cada vez que agrega una nueva entrada, HashMap verifica si se trata de un duplicado. Cuando hay una colisión de hash, tiene que comparar la clave entrante con cada clave asignada a esa ranura. Entonces, en el peor de los casos, donde todo tiene un hash en una sola ranura, la segunda clave se compara con la primera clave, la tercera clave se compara con la # 1 y la # 2, la cuarta clave se compara con la # 1, # 2 y # 3 , etc. Para cuando llegue al número clave 1 millón, habrá realizado más de un billón de comparaciones.

@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é de buscar duplicados en el último párrafo: cada vez que una clave tiene un hash en la misma ranura, HashMap debe verificar si es un duplicado de una clave existente, o si están simplemente en la misma ranura por coincidencia de la función hash. No sé si ese es el "punto" de un HashMap: yo diría que el "punto" 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 claves, sí, claves diferentes, no aparece la misma clave nuevamente, ese mapa en el mismo espacio en la tabla , HashMap crea una lista vinculada. Luego, debido a que 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 asigne a esta misma ranura debe perseguir la lista vinculada examinando cada entrada existente para ver si esto es un duplicado de una clave vista anteriormente, o si es una clave nueva.

Actualizar mucho después de la publicación original

Acabo de recibir una votación a favor de 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.

Suma a [0] + a [1] yb [0] + b [1] + b [2]. Él dice que los valores de cada byte van 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 aproximadamente 1639 entradas por valor hash. Eso es montones, montones de colisiones, que requieren montones y montones de búsquedas secuenciales a través de listas enlazadas.

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]]. Es igual a ([[2,1], [5,3,4] ]), por lo que para cumplir con el contrato deben tener códigos hash iguales. Bueno. Aún así, hay muchos 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 hash funcione a partir de copias de las matrices. Además, usar un bucle para calcular constantes cada vez que pasa la función es ineficaz. 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 realizara el cálculo una vez durante la compilación; o tener 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 resultados. Tenga en cuenta que primero establece hash = 503 que multiplica por 5381 antes incluso 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 los ciclos de la 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 agregar complejidad por el bien de la complejidad.

Mi primera idea es asegurarme de que está inicializando su HashMap correctamente. Desde JavaDocs para HashMap :

Una instancia de HashMap tiene dos parámetros que afectan su rendimiento: capacidad inicial y factor de carga. La capacidad es la cantidad de cubos 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 llena se permite que se llene 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 procesar (es decir, las estructuras de datos internas se reconstruyen) de modo que la tabla hash tenga aproximadamente el doble de la cantidad de depósitos.

Entonces, si está comenzando con un HashMap demasiado pequeño, cada vez que necesita cambiar el tamaño, todos los hash se vuelven a calcular ... que podría ser lo que siente cuando llega al punto de inserción de 2-3 millones.

Sugeriría un enfoque de tres puntos:

1. Ejecute Java con más memoria: java -Xmx256Mpor ejemplo, para ejecutar con 256 Megabytes. Use más si es necesario y tiene mucha RAM.

2. Guarde en caché sus valores hash calculados como lo sugiere otro cartel, de modo que cada objeto solo calcule su valor hash una vez.

3. Utilice un algoritmo de hash mejor. El que publicaste devolvería el mismo hash donde a = {0, 1} como si fuera a = {1, 0}, todo lo demás es igual.

Utilice lo que Java le ofrece de forma gratuita.

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

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

Entrar en el área gris de "tema encendido / apagado", pero necesario para eliminar la confusión con respecto a la sugerencia de Oscar Reyes de que más colisiones de hash es algo bueno porque reduce la cantidad de elementos en el HashMap. Puede que no entienda lo que dice Oscar, pero no parece que sea el único: kdgregory, delfuego, Nash0, y parece que todos compartimos la misma (mala) comprensión.

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

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

Independientemente de cualquier comprensión o malentendido, lo que sucede es que diferentes instancias de la misma clase no se insertan solo una 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 los objetos iguales tengan el mismo código hash; sin embargo, no requiere que los objetos desiguales tengan diferentes códigos hash (aunque esto puede ser deseable por otras razones) [1].

A continuación se muestra el ejemplo pastebin.com/f20af40b9 (al que Oscar se refiere al menos dos veces), pero modificado ligeramente para usar aserciones JUnit en lugar de líneas de impresión. 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 código hash no es la historia completa. Lo que el ejemplo de pastebin ignora es el hecho de que ambos sy eseson iguales: ambos son la cadena "ese". Por lo tanto, insertar u obtener el contenido del mapa usando so eseo "ese"como clave son todos equivalentes porques.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 que la clave -> valor s -> 1se sobrescribe ese -> 2cuando map.put(ese, 2)se llama en la prueba uno. En la prueba dos, sy esetodavía tienen el mismo código hash (verificado por assertEquals(s.hashCode(), ese.hashCode());) Y son de la misma clase. Sin embargo, sy eseson MyStringinstancias en esta prueba, no Stringinstancias de Java , con la única diferencia relevante para esta prueba siendo los iguales: String s equals String eseen la prueba uno anterior, mientras que MyStrings s does not equal MyString eseen 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;
    }
}

Según 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 es igual es lo que importa, no la "misma clase", no está clara (énfasis mío):

"En realidad no. La lista se crea solo si el hash es el mismo, pero la clave es diferente. Por ejemplo, si un String da el código hash 2345 y Integer da el mismo código hash 2345, entonces el número entero se inserta en la lista como String. equals (Integer) es falso. Pero si tienes la misma clase (o al menos .equals devuelve verdadero), entonces se usa la misma entrada. Por ejemplo, new String ("uno") y `new String (" uno ") usado como claves, utilizará la misma entrada. En realidad, este es el punto COMPLETO de HashMap en primer lugar. Compruébelo usted mismo: pastebin.com/f20af40b9 - Oscar Reyes "

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

"@delfuego: Compruébalo tú mismo: pastebin.com/f20af40b9 Entonces, en esta pregunta se está usando la misma clase (espera un minuto, se está usando la misma clase ¿verdad?) Lo que implica que cuando se usa el mismo hash se usa la misma entrada se utiliza 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 muy bien)? Apuesto a que está en el objeto creación donde la actuación 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"

Una vez más, puedo malinterpretar lo que Oscar realmente estaba tratando de decir. Sin embargo, sus comentarios originales han causado tanta confusión que parece prudente aclarar todo con algunas pruebas explícitas para que no queden dudas.

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

• Siempre que se invoca en el mismo objeto más de una vez durante la ejecución de una aplicación, el método hashCode debe devolver constantemente el mismo número entero, siempre que no se modifique la información utilizada en comparaciones iguales en el objeto. Este número entero no necesita permanecer consistente de una ejecución de una aplicación a otra ejecución de la misma aplicación.

• Si dos objetos son iguales según 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 no son iguales según el método igual s (Object), entonces llamar al método hashCode en cada uno de los dos objetos debe producir resultados enteros distintos. Sin embargo, el programador debe ser consciente de que producir resultados enteros distintos para objetos desiguales puede mejorar el rendimiento de las tablas hash.

Si las matrices en su hashCode publicado son bytes, entonces probablemente terminará con muchos duplicados.

a [0] + a [1] siempre estará entre 0 y 512. La suma de las b siempre dará como resultado un número entre 0 y 768. multiplique esos y obtendrá un límite superior de 400,000 combinaciones únicas, asumiendo que sus datos están perfectamente distribuidos entre todos los valores posibles de cada byte. Si sus datos son regulares, es probable que tenga resultados mucho menos únicos de este método.

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

Intenta modificar ambos.

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

Ejemplo: Teclas: 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 -> Mapa2

Por lo tanto, realizará dos búsquedas, pero el conjunto de claves sería 1,000,000 frente a 28,000,000. También puede hacer esto fácilmente con patrones de picadura.

Si las claves son completamente aleatorias, esto no funcionará

Si las matrices de dos bytes que menciona son su clave completa, los valores están en el rango 0-51, únicos y el orden dentro de las matrices ayb es insignificante, mis matemáticas me dicen que solo hay alrededor de 26 millones de permutaciones posibles y que probablemente esté intentando llenar el mapa con valores para todas las claves posibles.

En este caso, tanto el llenado como la recuperación de valores de su almacén de datos serían, por supuesto, mucho más rápidos si usa una matriz en lugar de un HashMap y la indexa de 0 a 25989599.

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

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

Supongo que estos mapas son de larga duración. es decir, los rellena y se quedan durante la duración de la aplicación. También supongo 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. Entonces, 26 millones de entradas en el mapa significan 26 millones * 3 == 78 millones de objetos. Esto está bien hasta que alcance un GC completo. Entonces tienes un problema de pausar el mundo. El GC observará cada uno de los 78M objetos y determinará que todos están vivos. Más de 78 millones de objetos son solo muchos objetos para mirar. Si su aplicación puede tolerar pausas largas ocasionales (quizás muchos segundos), no hay problema. Si está tratando de lograr garantías 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 lo que agrava enormemente el problema.

No conozco una gran solución para este problema. Ideas:

• A veces es posible ajustar los tamaños de montón y GC para evitar "principalmente" GC completos.
• Si el contenido de su mapa se agita mucho, puede probar FastMap de Javolution : puede agrupar objetos de entrada, lo que podría reducir la frecuencia de recopilaciones completas
• Puede crear su propio mapa implícito y hacer una gestión de memoria explícita en el byte [] (es decir, cambiar la CPU por una latencia más predecible serializando millones de objetos en un solo byte [] - ¡uf!)
• No use Java para esta parte: hable con algún tipo de base de datos en memoria predecible a través de un socket
• Espero que el nuevo colector G1 ayude (se aplica principalmente al caso de alta rotación)

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

En mi caso quiero crear un mapa con 26 millones de entradas. Usando el Java HashMap estándar, la tasa de colocació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. Tomó 785,68 segundos (13 minutos). Y no pude construir 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 costo de la clave-valor de búsqueda es O (1).

Nota: "Prime Tree" funciona mejor en "claves 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 ramas que los números son números primos (en lugar de "2" -binarios).

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

SQLite te permite usarlo en memoria.

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

Almacena todo como par Clave-> Valor, NO es un RDBMS. y apunta a ser rápido.

Primero debe verificar que está usando Map correctamente, un buen método hashCode () para claves, capacidad inicial para Map, implementación correcta de Map, 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. ¿Se ejecuta, por ejemplo, el método hashCode () miles de millones de veces?

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

Otra opción sería algún motor de base de datos que sea más ligero que el RDBMS SQL completo. Algo como Berkeley DB , tal vez.

Tenga en cuenta que personalmente no tengo experiencia sobre el rendimiento de estos productos, pero podría valer la pena intentarlo.

Puede intentar almacenar en caché el código hash calculado en el objeto clave.

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

Por supuesto, debe tener cuidado de no cambiar el contenido de la clave después de que se haya calculado el hashCode por primera vez.

Editar: Parece que el almacenamiento en caché tiene valores de código no vale la pena cuando agrega cada clave solo una vez a un mapa. En alguna otra situación, esto podría resultar útil.

Otro cartel ya señaló que la implementación de su código hash resultará en muchas colisiones debido a la forma en que está agregando valores. Estoy dispuesto a serlo, si miras el objeto HashMap en un depurador, encontrarás que tienes quizás 200 valores hash distintos, con cadenas de cubos extremadamente largas.

Si siempre tiene valores en el rango 0..51, cada uno de esos valores tomará 6 bits para representar. Si siempre tiene 5 valores, puede crear un código hash de 30 bits con cambios a la izquierda y adiciones:

    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;

El desplazamiento a la izquierda es rápido, pero lo dejará con códigos hash que no están distribuidos uniformemente (porque 6 bits implican un rango 0..63). Una alternativa es multiplicar el hash por 51 y sumar cada valor. Esto todavía no estará perfectamente distribuido (por ejemplo, {2,0} y {1,52} colisionarán), y será más lento que el cambio.

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

Como se señaló, la implementación de su código hash tiene demasiadas colisiones, y arreglarlo debería resultar en un rendimiento decente. Además, el almacenamiento en caché de hashCodes y la implementación de iguales de manera eficiente ayudarán.

Si necesita optimizar aún más:

Según su descripción, solo hay (52 * 51/2) * (52 * 51 * 50/6) = 29304600 claves diferentes (de las cuales 26000000, es decir, aproximadamente el 90%, estarán presentes). Por lo tanto, puede diseñar una función hash sin colisiones y usar una matriz simple en lugar de un mapa hash para almacenar sus datos, lo que reduce el consumo de memoria y aumenta la velocidad de búsqueda:

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

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

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

(Generalmente, es imposible diseñar una función hash eficiente y libre de colisiones que se agrupe bien, por lo que un HashMap tolerará colisiones, lo que genera algunos gastos generales)

Suponiendo que ay bestán ordenados, puede usar la siguiente función 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;  

Creo que está libre de colisiones. Demostrar esto se deja como ejercicio para el lector inclinado a las matemáticas.

En Effective Java: Programming Language Guide (Serie Java)

En el capítulo 3 puede encontrar buenas reglas a seguir al calcular hashCode ().

Especialmente:

Si el campo es una matriz, trátelo como si cada elemento fuera un campo separado. Es decir, calcule un código hash para cada elemento significativo aplicando estas reglas de forma recursiva y combine estos valores en el paso 2.b. Si cada elemento de un campo de matriz es significativo, puede usar uno de los métodos Arrays.hashCode agregados en la versión 1.5.

Asigne un mapa grande al principio. Si sabe que tendrá 26 millones de entradas y tiene memoria para ello, haga a new HashMap(30000000).

¿Está seguro de que tiene suficiente memoria para 26 millones de entradas con 26 millones de claves y valores? Esto me suena a mucha memoria. ¿Está seguro de que la recolección de basura sigue funcionando bien en su marca de 2 a 3 millones? Podría imaginarme eso como un cuello de botella.

Puedes probar dos cosas:

Esas dos acciones reducirán enormemente la cantidad de refrito que está haciendo la estructura, y creo que son bastante fáciles de probar.

Si eso no funciona, considere usar un almacenamiento diferente como RDBMS.

EDITAR

Es extraño que configurar la capacidad inicial reduzca el rendimiento en tu caso.

Ver desde los javadocs :

Si la capacidad inicial es mayor que el número máximo de entradas dividido por el factor de carga, nunca se realizarán operaciones de refrito.

Hice una marca de microplaya (que de ninguna manera es definitiva, pero al menos prueba este punto)

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

Por lo tanto, el uso de la capacidad inicial cae de 21 a 16 segundos debido a la repetición. Eso nos deja con tu hashCodemétodo como un "área de oportunidad";)

EDITAR

No es el HashMap

Según su última edición.

Creo que realmente debería perfilar su aplicación y ver dónde se consume la memoria / cpu.

He creado una clase implementando tu mismo hashCode

Ese código hash da millones de colisiones, luego las entradas en el HashMap se reducen drásticamente.

Paso de 21, 16 en mi prueba anterior a 10 y 8. La razón es porque el hashCode provoca una gran cantidad de colisiones y no estás almacenando los 26M de objetos que crees, sino un número mucho menor (alrededor de 20k diría).

El problema NO ES EL HASHMAP está en otro lugar de su código.

Ya es hora de conseguir un generador de perfiles y averiguar dónde. Creo que está en la creación del elemento o probablemente está escribiendo en el disco o recibiendo datos de la red.

Aquí está mi implementación de tu clase.

tenga en cuenta que no usé un rango de 0-51 como lo hizo, pero -126 a 127 para mis valores y admite que se repitieron, eso es porque hice esta prueba antes de que actualizara su pregunta

La única diferencia es que su clase tendrá más colisiones, por lo tanto, menos elementos almacenados en el 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 );
    }
}

El uso de esta clase tiene clave para el programa anterior

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

me da:

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


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

Tal vez intente usarlo si necesita sincronizarlo

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

Hice una pequeña prueba hace un tiempo con una lista frente a un mapa de hash, lo gracioso fue recorrer la lista y encontrar el objeto tomó la misma cantidad de tiempo en milisegundos que usar la función de obtención de mapas de hash ... solo un fyi. Oh, sí, la memoria es un gran problema cuando se trabaja con hashmaps de ese tamaño.

Los métodos populares de hash utilizados no son realmente muy buenos para conjuntos grandes y, como se señaló anteriormente, el hash utilizado es particularmente malo. Es mejor usar un algoritmo hash con alta mezcla y cobertura como BuzHash (implementación de muestra en http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )