entre - hashmap vs hashtable java

¿Por qué HashMap requiere que la capacidad inicial sea una potencia de dos?

Question

Estaba revisando el código fuente de HashMap de Java cuando vi lo siguiente

//The default initial capacity - MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 16;

Mi pregunta es por qué existe este requisito en primer lugar? También veo que el constructor que permite crear un HashMap con una capacidad personalizada lo convierte en una potencia de dos:

int capacity = 1;
while (capacity < initialCapacity)
  capacity <<= 1;

¿Por qué la capacidad siempre tiene que ser un poder de dos?

Además, cuando se realiza un reajuste automático, ¿qué ocurre exactamente? ¿La función hash también está alterada?

Answer 1

El mapa tiene que determinar qué índice de tabla interno usar para cualquier clave dada, asignando cualquier valor int (podría ser negativo) a un valor en el rango [0, table.length) . Cuando table.length es una potencia de dos, eso se puede hacer realmente a bajo costo, y está en indexFor :

static int indexFor(int h, int length) {
    return h & (length-1);
}

Con una longitud de tabla diferente, necesitaría calcular un resto y asegurarse de que no sea negativo. Esto es definitivamente una micro-optimización, pero probablemente una válida :)

Además, cuando se realiza un reajuste automático, ¿qué ocurre exactamente? ¿La función hash también está alterada?

No me queda claro a qué te refieres. Se usan los mismos códigos hash (porque simplemente se calculan llamando a hashCode en cada clave) pero se distribuirán de forma diferente dentro de la tabla debido a la modificación de la longitud de la tabla. Por ejemplo, cuando la longitud de la tabla es 16, los códigos hash de 5 y 21 terminan almacenados en la entrada 5 de la tabla. Cuando la longitud de la tabla aumenta a 32, estarán en entradas diferentes.

Answer 2

La situación ideal es utilizar tamaños de números primos para la matriz de respaldo de un HashMap . De esa forma, sus claves se distribuirán de forma más natural en toda la matriz. Sin embargo, esto funciona con la división mod y esa operación se volvió más y más lenta con cada versión de Java. En cierto sentido, el enfoque del poder de 2 es el peor tamaño de tabla que puedas imaginar, ya que con implementaciones de código hash pobres es más probable que se produzcan colisiones de clave en el conjunto.

Por lo tanto, encontrará otro método muy importante en la implementación de HashMap de Java, que es el hash(int) , que compensa los hashcodes pobres.