¿Por qué es eso, cuantos más '1' bits tengo en mi clave, más tiempo me toma colocar en el HashMap?

Question

Estoy haciendo un proyecto para una clase que se enfoca en almacenar una enorme matriz con la mayoría de los 0 valores en la memoria y realizar algunos cálculos matriciales en ella. Mi primer pensamiento fue utilizar un HashMap para almacenar los elementos de la matriz, y solo almacenar los elementos que no son cero, para evitar el uso de grandes cantidades de memoria.

Quería hacer una clave para el HashMap que representara tanto la fila como el número de columna del elemento de manera que, cuando accedí a esa entrada en el mapa, pude volver a extraer ambos valores. No sé Java tan bien como C# - en C# Haría un struct con y Column miembros, pero en Java me di cuenta rápidamente de que no hay tipos de valores de usuario. Con una fecha límite inminente, hice una apuesta segura e hice que el Key fuera largo. Guardé los datos de la fila (int de 32 bits) en los primeros 32 bits y los datos de la columna en los últimos 32 usando algunos cambios de bit muy simples. [EDITAR: También me gustaría señalar que mi HashMap se inicializó con un tamaño inicial específico que representa exactamente el número de valores que almaceno en él, que nunca se excede.]

[Nota al margen: el motivo que quiero para poder extraer los datos de fila/columna de nuevo es aumentar considerablemente la eficiencia de la multiplicación de matrices, desde O(n^2) a O(n), y una más pequeña n para arrancar]

lo que noté después de la implementación de esta estructura es que se necesita un enorme 7 segundos para leer una matriz de 23426 x 23426 de un archivo de texto en el que solo se dan elementos distintos de cero, ¡pero solo lleva 2 segundos calcular los valores propios que debemos dar! Después de comentar de forma selectiva los métodos, he llegado a la conclusión de que la mayor parte de este lapso de tiempo de 7 segundos se usa para almacenar mis valores en el HashMap.

public void Set(double value, int row, int column) { 
    //assemble the long key, placing row and column in adjacent sets of bits 
    long key = (long)row << SIZE_BIT_MAX; //(SIZE_BIT_MAX is 32) 
    key += column; 
    elements.put(key, value); 
} 

Ese es el código para establecer un valor. Si utilizo este método en su lugar:

public void Set(double value, int row, int column) { 
    //create a distinct but smaller key (around 32 bits max) 
    long key = (long)(row * matrixSize) + column; 
    elements.put(key, value); 
} 

La lectura solo toma 2 segundos. Ambas versiones de la clave son distintas para cada elemento, ambas son de tipo largo, y el código real para crear cualquiera de ellas es de complejidad mínima. Es el elements.put(key, value) que marca la diferencia entre 7 segundos y 2.

Mi pregunta es, ¿por qué? La diferencia que veo entre estas versiones clave es que la primera tiene bits establecidos en 1 en todo y con más frecuencia, mientras que la segunda tiene todos sus 32 bits más altos establecidos en 0. ¿Estoy persiguiendo a una arenga roja, o es esta diferencia bastante dramática en el rendimiento el resultado de algo interno en el método HashMap.put?

Answer 1

Tome un vistazo a cómo Long implementa el método hashCode() (al menos en OpenJDK 7):

public int hashCode() { 
    return (int)(value^(value >>> 32)); 
} 

Esto significa que la llave se rellena de nuevo en 32 bits; todos los bits inferiores se cancelan entre sí con bastante frecuencia, lo que resulta en una gran cantidad de colisiones que requieren el HashMap para pasar más tiempo buscando una ranura libre en un cubo. Su segundo método evita ese problema porque el código hash generado por cada tecla es un valor único (porque solo tiene 23426 x 23426 = 548777476 elementos que se ajusta bien a 32 bits).

Por lo tanto, la selección es la clave, pero no la cantidad de bits configurados.

Sin embargo, lo que quiere usted decir exactamente con “tipos de valores de usuario?”

public class MatrixKey { 
    private final int row; 
    private final int column; 
    public MatrixKey(int row, int column) { 
     this.row = row; 
     this.column = column; 
    } 
    public int getRow() { return row; } 
    public int getColumn() { return column; } 
} 

Esta clase puede hacer una perfectamente buena clave para una Map en Java una vez que se implemente hashCode() y equals(). Solo asegúrese de no implementar su método hashCode del modo en que lo hace Long. :)

Answer 2

Dependiendo de la implementación, podría estar golpeando colisiones hash.

Si todos sus valores hash terminan en el mismo "cubo", la implementación normalmente los arrojará a una lista de algún tipo. Si este es el caso, sus tiempos de acceso sufrirán significativamente.

Answer 3

Desde el JDK 6 documentation for Long.hashCode() (tenga en cuenta que su long primitiva es autoboxed en un objeto Long - mientras que en C# primitivas en realidad son objetos):

devuelve un código hash de esta larga. El resultado es el OR exclusivo de las dos mitades del valor largo primitivo que posee este objeto Largo.Es decir, el código hash es el valor de la expresión:

(int)(this.longValue()^(this.longValue()>>>32)) 

Creo Dada esta definición, esto explica por qué:

la tasa de colisiones se reduce cuando se introduce más entropía y por lo tanto dispersarla más a través de la mitad superior del valor long. (edición: He leído el orden equivocado, así que aquí está el contra-argumento más adelante)

Las colisiones podrían ser más probable cuando se extiende dentro del rango long - después de todo, en Java hashcodes sólo son int tamaño, por lo solo puedes tener una cantidad limitada de distribución equitativa. Si sabe que está distribuido "uniformemente" en un rango int, entonces sus colisiones se reducen. Si lo extiende en el rango long, entonces aumenta enormemente la posibilidad de colisión.

Aquí es from the HashMap Java documentation (el énfasis es mío):

Esta aplicación proporciona un rendimiento constante en el tiempo de las operaciones básicas (get y put), asumir la función de dispersión dispersa los elementos adecuadamente entre los cubos

Nota al margen: encontrará ganancias de rendimiento aún mayores al sintonizar initial capacity y load factor - consulte la documentación de HashMap para obtener más información.