funciona - java map

¿Por qué initialCapacity of Hashtable es 11 mientras que DEFAULT_INITIAL_CAPACITY en HashMap es 16 y requiere una potencia de 2

Question

Comparación del código fuente de HashMap y Hashtable en jdk 1.6, vi los siguientes códigos dentro de HashMap

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

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

Sin embargo, en Hashtable, vi los códigos de abajo?

table = new Entry[initialCapacity];

public Hashtable() {
    this(11, 0.75f);
}

así que mi pregunta es: ¿por qué hashMap requiere una potencia de 2 como capacidad inicial? y mientras hashtable elige 11 como la capacidad inicial por defecto? Supongo que esto no tiene nada que ver con lo que la tabla hash es segura para subprocesos y no permite valores o claves nulas.

Gracias.

Answer 1

El requisito para que el tamaño de la tabla sea una potencia de dos es un detalle de implementación, que los usuarios de la clase desconocen, por eso el controlador ajusta silenciosamente el valor a la siguiente potencia mayor de dos en lugar de marcar un error .

La implementación Hashtable asume que el hash puede no estar distribuido uniformemente, por lo que trata de usar un número de bins que es primo con la esperanza de evitar picos en la distribución de frecuencia del hash.

La combinación de estos dos detalles de implementación conduce a un mal desempeño.

(Por ejemplo, una función hash primitiva sería

int hash(String s, int nBins) {
    return s[0] % nBins;
}

Si nBins es 32, e y E terminan en el mismo bin, por lo que la distribución de valores hash se correlaciona con la distribución de la aparición de letras, que tiene picos distintos, por lo que la distribución de frecuencia tendría un pico en 32.)

Answer 2

El siguiente artículo aborda esta pregunta con cierto detalle: HashMap requiere un mejor código de hash () - JDK 1.4 Parte II .

De acuerdo con ese artículo, la razón principal para pasar al tamaño de potencia de dos es que el enmascaramiento de bits es más rápido que la división de enteros. Esto no está exento de consecuencias adversas, que se explican por uno de los autores originales:

Joshua Bloch : La desventaja de usar una potencia de dos es que la tabla hash resultante es muy sensible a la calidad de la función hash (hashCode). Es imperativo que cualquier cambio en la entrada debe afectar los bits de orden inferior del valor hash. (Idealmente, debería afectar a todos los bits del valor hash con la misma probabilidad). Como no tenemos ninguna garantía de que esto sea cierto, aplicamos una función hash secundaria (o "defensiva") cuando cambiamos a la potencia de dos tabla de picadillo. Esta función hash se aplica a los resultados de hashCode antes de enmascarar los bits de orden inferior. Su trabajo es dispersar la información sobre todos los bits, y en particular, en los bits de orden inferior. Por supuesto, tiene que ejecutarse muy rápido, o perderá el beneficio de cambiar a la mesa de potencia de dos tamaños. La función hash secundaria original en 1.4 resultó ser insuficiente. Sabíamos que esto era una posibilidad teórica, pero pensábamos que no afectaba a ningún conjunto de datos prácticos. Estuvimos equivocados. La función hash secundaria de reemplazo (que desarrollé con la ayuda de una computadora) tiene propiedades estadísticas sólidas que prácticamente garantizan una buena distribución del cazo.

Answer 3

Esto podría ayudar:

http://www.concentric.net/~Ttwang/tech/primehash.htm

Básicamente, si recuerdo correctamente, cuando tienes una tabla hash con un tamaño de potencia de 2, es fácil obtener una función hash basada en los bits menos relevantes de la clave.

El uso de un número primo (como en 11) como el tamaño de la tabla, hace que la colisión en las filas de la tabla sea menos probable, por lo que la inserción es "más barata".

Answer 4

Hashtable utiliza tamaños de tablas de números pseudo-primarios y hace que el tamaño de la tabla sea relativamente más lento. HashMap usa una potencia de 2 como bitio y es más rápido que usar módulo.

Irónicamente, un módulo de una potencia de 2 significa que se necesita un buen hashCode () ya que los bits superiores se ignorarían, por lo que HashMap tiene un método para reorganizar el hashCode para evitar este problema, lo que significa que puede ser más lento. : Z