example - Implementación de HashMap Java 8

map list to hashmap java 8

Question

Según el siguiente documento de enlace: Implementación de Java HashMap

Estoy confundido con la implementación de HashMap (o más bien, una mejora en HashMap ). Mis consultas son:

en primer lugar

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

¿Por qué y cómo se usan estas constantes? Quiero algunos ejemplos claros para esto. ¿Cómo están logrando un aumento de rendimiento con esto?

En segundo lugar

Si ve el código fuente de HashMap en JDK, encontrará la siguiente clase interna estática:

static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
    HashMap.TreeNode<K, V> parent;
    HashMap.TreeNode<K, V> left;
    HashMap.TreeNode<K, V> right;
    HashMap.TreeNode<K, V> prev;
    boolean red;

    TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
        super(arg0, arg1, arg2, arg3);
    }

    final HashMap.TreeNode<K, V> root() {
        HashMap.TreeNode arg0 = this;

        while (true) {
            HashMap.TreeNode arg1 = arg0.parent;
            if (arg0.parent == null) {
                return arg0;
            }

            arg0 = arg1;
        }
    }
    //...
}

¿Cómo se usa? Solo quiero una explicación del algoritmo .

Answer 1

Debería visualizarlo: digamos que hay una clave de clase con solo la función hashCode () anulada para devolver siempre el mismo valor

public class Key implements Comparable<Key>{

  private String name;

  public Key (String name){
    this.name = name;
  }

  @Override
  public int hashCode(){
    return 1;
  }

  public String keyName(){
    return this.name;
  }

  public int compareTo(Key key){
    //returns a +ve or -ve integer 
  }

}

y luego en otro lugar, estoy insertando 9 entradas en un HashMap con todas las claves como instancias de esta clase. p.ej

Map<Key, String> map = new HashMap<>();

    Key key1 = new Key("key1");
    map.put(key1, "one");

    Key key2 = new Key("key2");
    map.put(key2, "two");
    Key key3 = new Key("key3");
    map.put(key3, "three");
    Key key4 = new Key("key4");
    map.put(key4, "four");
    Key key5 = new Key("key5");
    map.put(key5, "five");
    Key key6 = new Key("key6");
    map.put(key6, "six");
    Key key7 = new Key("key7");
    map.put(key7, "seven");
    Key key8 = new Key("key8");
    map.put(key8, "eight");

//Since hascode is same, all entries will land into same bucket, lets call it bucket 1. upto here all entries in bucket 1 will be arranged in LinkedList structure e.g. key1 -> key2-> key3 -> ...so on. but when I insert one more entry 

    Key key9 = new Key("key9");
    map.put(key9, "nine");

  threshold value of 8 will be reached and it will rearrange bucket1 entires into Tree (red-black) structure, replacing old linked list. e.g.

                  key1
                 /    /
               key2   key3
              /   /   /  /

El recorrido del árbol es más rápido {O (log n)} que LinkedList {O (n)} y a medida que n crece, la diferencia se vuelve más significativa.

Answer 2

El cambio en la implementación de HashMap se agregó con JEP-180 . El propósito era:

Mejore el rendimiento de java.util.HashMap en condiciones de alta colisión de hash mediante el uso de árboles equilibrados en lugar de listas vinculadas para almacenar entradas de mapas. Implemente la misma mejora en la clase LinkedHashMap

Sin embargo, el rendimiento puro no es la única ganancia. También evitará el ataque de HashDoS , en caso de que se use un mapa hash para almacenar la entrada del usuario, porque el árbol rojo-negro que se usa para almacenar datos en el depósito tiene la peor complejidad de inserción en el caso O (log n). El árbol se usa después de que se cumpla un cierto criterio; vea la respuesta de Eugene .

Answer 3

Para comprender la implementación interna de hashmap, debe comprender el hash. El hash en su forma más simple es una forma de asignar un código único para cualquier variable / objeto después de aplicar cualquier fórmula / algoritmo en sus propiedades.

Una verdadera función hash debe seguir esta regla:

“La función hash debería devolver el mismo código hash cada vez que la función se aplica en objetos iguales o iguales. En otras palabras, dos objetos iguales deben producir el mismo código hash de forma coherente ".

Answer 4

Para decirlo más simple (tanto como yo podría simplificar) + algunos detalles más.

Estas propiedades dependen de muchas cosas internas que sería genial entender, antes de pasar directamente a ellas.

TREEIFY_THRESHOLD -> cuando un único depósito alcanza esto (y el número total excede MIN_TREEIFY_CAPACITY ), se transforma en un nodo de árbol rojo / negro perfectamente equilibrado . ¿Por qué? Debido a la velocidad de búsqueda. Piénselo de una manera diferente:

tomaría como máximo 32 pasos para buscar una Entrada dentro de un cubo / bin con entradas Integer.MAX_VALUE .

Alguna introducción para el siguiente tema. ¿Por qué el número de contenedores / cubos siempre es una potencia de dos ? Al menos dos razones: más rápido que la operación del módulo y el módulo en números negativos será negativo. Y no puede poner una entrada en un cubo "negativo":

 int arrayIndex = hashCode % buckets; // will be negative

 buckets[arrayIndex] = Entry; // obviously will fail

En cambio, hay un buen truco utilizado en lugar de módulo:

 (n - 1) & hash // n is the number of bins, hash - is the hash function of the key

Eso es semánticamente lo mismo que la operación de módulo. Mantendrá los bits más bajos. Esto tiene una consecuencia interesante cuando haces:

Map<String, String> map = new HashMap<>();

En el caso anterior, la decisión de a dónde va una entrada se toma en función de los últimos 4 bits de su código hash.

Aquí es donde entra en juego la multiplicación de los cubos. Bajo ciertas condiciones (tomaría mucho tiempo explicarlo en detalles exactos ), los cubos se duplican en tamaño. ¿Por qué? Cuando los cubos se duplican, hay un poco más en juego .

Entonces tiene 16 cubos: los últimos 4 bits del código hash deciden a dónde va una entrada. Duplica los cubos: 32 cubos - 5 últimos bits deciden a dónde irá la entrada.

Como tal, este proceso se llama re-hashing. Esto puede ser lento. Eso es (para las personas que se preocupan) ya que HashMap es "bromeado" como: rápido, rápido, rápido, lento . Hay otras implementaciones: busque hashmap sin pausa ...

Ahora UNTREEIFY_THRESHOLD entra en juego después de volver a hacer hash. En ese momento, algunas entradas pueden moverse de estos contenedores a otros (agregan un bit más al cálculo (n-1)&hash , y como tal podrían moverse a otros depósitos) y pueden alcanzar este UNTREEIFY_THRESHOLD . En este punto, no vale la pena mantener el bin como red-black tree node , sino como LinkedList , como

 entry.next.next....

MIN_TREEIFY_CAPACITY es el número mínimo de depósitos antes de que un depósito determinado se transforme en un árbol.

Answer 5

HashMap contiene una cierta cantidad de cubos. Utiliza hashCode para determinar en qué cubo colocarlos. Por simplicidad, imagínelo como un módulo.

Si nuestro código hash es 123456 y tenemos 4 cubos, 123456 % 4 = 0 entonces el artículo va en el primer cubo, Cubo 1.

Si nuestra función de código hash es buena, debería proporcionar una distribución uniforme para que todos los depósitos se usen de manera equitativa. En este caso, el depósito utiliza una lista vinculada para almacenar los valores.

Pero no puede confiar en que las personas implementen buenas funciones hash. Las personas a menudo escriben funciones hash pobres que darán como resultado una distribución no uniforme. También es posible que tengamos mala suerte con nuestras entradas.

Cuanto menos uniforme sea esta distribución, más nos moveremos de las operaciones O (1) y más nos acercaremos a las operaciones O (n).

La implementación de Hashmap intenta mitigar esto organizando algunos cubos en árboles en lugar de listas vinculadas si los cubos se vuelven demasiado grandes. Para eso está TREEIFY_THRESHOLD = 8 . Si un cubo contiene más de ocho elementos, debería convertirse en un árbol.

Este árbol es un árbol rojo-negro. Primero se ordena por código hash. Si los códigos hash son los mismos, utiliza el método compareTo de Comparable si los objetos implementan esa interfaz, de lo contrario, el código hash de identidad.

Si las entradas se eliminan del mapa, el número de entradas en el depósito podría reducirse de modo que esta estructura de árbol ya no sea necesaria. Para eso está el UNTREEIFY_THRESHOLD = 6 . Si el número de elementos en un cubo cae por debajo de seis, también podríamos volver a usar una lista vinculada.

Finalmente, hay MIN_TREEIFY_CAPACITY = 64 .

Cuando un mapa hash crece en tamaño, se redimensiona automáticamente para tener más depósitos. Si tenemos un pequeño mapa de hash, la probabilidad de que obtengamos cubos muy completos es bastante alta, porque no tenemos muchos cubos diferentes en los que poner cosas. Es mucho mejor tener un mapa hash más grande, con más cubos que estén menos llenos. Esta constante básicamente dice que no comencemos a hacer cubos en los árboles si nuestro mapa de hash es muy pequeño; en su lugar, debe cambiar el tamaño para que sea más grande.

Para responder a su pregunta sobre el aumento de rendimiento, se agregaron estas optimizaciones para mejorar el peor de los casos. Solo estoy especulando, pero probablemente solo verás una mejora notable en el rendimiento debido a estas optimizaciones si tu función hashCode no fue muy buena.

Answer 6

TreeNode es una forma alternativa de almacenar las entradas que pertenecen a un único contenedor de HashMap . En implementaciones anteriores, las entradas de un contenedor se almacenaban en una lista vinculada. En Java 8, si el número de entradas en un bin superó un umbral ( TREEIFY_THRESHOLD ), se almacenan en una estructura de árbol en lugar de la lista vinculada original. Esta es una optimización.

De la implementación:

/*
 * Implementation notes.
 *
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.