Implementação de HashMap Java 8

De acordo com o seguinte documento de link: Java HashMap Implementation

Estou confuso com a implementação de HashMap(ou melhor, um aprimoramento em HashMap). Minhas dúvidas são:

primeiramente

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

Por que e como essas constantes são usadas? Eu quero alguns exemplos claros para isso. Como eles estão conseguindo um ganho de desempenho com isso?

Em segundo lugar

Se você HashMapvir o código-fonte de no JDK, encontrará a seguinte classe 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;
        }
    }
    //...
}

Como isso é usado? Eu só quero uma explicação do algoritmo .

HashMapcontém um certo número de baldes. UsahashCode para determinar em qual balde colocá-los. Para simplificar, imagine-o como um módulo.

Se nosso código hash for 123456 e tivermos 4 baldes, 123456 % 4 = 0o item vai para o primeiro balde, Balde 1.

Se nossa função hashcode for boa, ela deve fornecer uma distribuição uniforme para que todos os baldes sejam usados ​​igualmente. Nesse caso, o balde usa uma lista vinculada para armazenar os valores.

Mas você não pode confiar nas pessoas para implementar boas funções de hash. Muitas vezes, as pessoas escreverão funções hash ruins que resultarão em uma distribuição não uniforme. Também é possível que tenhamos azar com nossas entradas.

Quanto menos uniforme for essa distribuição, mais nos afastamos das operações O (1) e nos aproximamos das operações O (n).

A implementação do Hashmap tenta mitigar isso organizando alguns baldes em árvores em vez de listas vinculadas se os baldes se tornarem muito grandes. É para isso que TREEIFY_THRESHOLD = 8serve. Se um balde contém mais de oito itens, deve se tornar uma árvore.

Esta árvore é uma árvore Vermelho-Preto. Ele é classificado primeiro por código hash. Se os códigos hash forem iguais, ele usa o compareTométodo deComparable se os objetos implementam essa interface, caso contrário, o código hash de identidade.

Se as entradas forem removidas do mapa, o número de entradas no depósito pode ser reduzido de forma que essa estrutura em árvore não seja mais necessária. É isso queUNTREEIFY_THRESHOLD = 6 serve. Se o número de elementos em um balde cair para menos de seis, podemos também voltar a usar uma lista vinculada.

Finalmente, existe o MIN_TREEIFY_CAPACITY = 64.

Quando um mapa hash aumenta de tamanho, ele se redimensiona automaticamente para ter mais baldes. Se tivermos um pequeno mapa hash, a probabilidade de obtermos baldes muito cheios é bastante alta, porque não temos tantos baldes diferentes para colocar as coisas. É muito melhor ter um mapa de hash maior, com mais baldes que estão menos cheios. Essa constante basicamente diz para não começar a transformar baldes em árvores se nosso mapa hash for muito pequeno - ele deve ser redimensionado para ficar maior primeiro.

Para responder à sua pergunta sobre o ganho de desempenho, essas otimizações foram adicionadas para melhorar o pior caso. Estou apenas especulando, mas você provavelmente só veria uma melhora perceptível no desempenho por causa dessas otimizações se sua hashCodefunção não fosse muito boa.

Para ser mais simples (tanto quanto eu poderia mais simples) + mais alguns detalhes.

Essas propriedades dependem de muitas coisas internas que seriam muito interessantes de entender - antes de passar para elas diretamente.

TREEIFY_THRESHOLD -> quando um único balde atinge isso (e o número total excede MIN_TREEIFY_CAPACITY), ele é transformado em um nó de árvore vermelho / preto perfeitamente equilibrado . Por quê? Por causa da velocidade de pesquisa. Pense nisso de uma maneira diferente:

seriam necessárias no máximo 32 etapas para pesquisar uma entrada em um balde / compartimento com entradas Integer.MAX_VALUE .

Alguma introdução para o próximo tópico. Por que o número de caixas / baldes é sempre uma potência de dois ? Pelo menos dois motivos: mais rápido do que a operação do módulo e o módulo em números negativos será negativo. E você não pode colocar uma entrada em um balde "negativo":

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

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

Em vez disso, há um bom truque usado em vez do módulo:

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

Isso é semanticamente o mesmo que operação de módulo. Ele manterá os bits mais baixos. Isso tem uma consequência interessante quando você faz:

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

No caso acima, a decisão de para onde vai uma entrada é tomada com base nos últimos 4 bits apenas do seu hashcode.

É aqui que a multiplicação dos baldes entra em jogo. Sob certas condições (levaria muito tempo para explicar com detalhes exatos ), os baldes dobram de tamanho. Por quê? Quando os baldes dobram de tamanho, há mais um bit entrando em ação .

Portanto, você tem 16 depósitos - os últimos 4 bits do hashcode decidem para onde vai uma entrada. Você dobra os baldes: 32 baldes - os 5 últimos bits decidem para onde irá a entrada.

Como tal, este processo é denominado re-hashing. Isso pode ficar lento. Isto é (para pessoas que se importam) porque HashMap é "brincado" como: rápido, rápido, rápido, lento . Existem outras implementações - pesquisar hashmap sem pausa ...

Agora UNTREEIFY_THRESHOLD entra em jogo após o re-hash. Nesse ponto, algumas entradas podem mover-se desses compartimentos para outros (eles adicionam mais um bit ao (n-1)&hashcálculo - e, como tal, podem mover-se para outros depósitos) e podem chegar a isso UNTREEIFY_THRESHOLD. Neste ponto, não vale a pena manter a lixeira como red-black tree node, mas em LinkedListvez disso, como

 entry.next.next....

MIN_TREEIFY_CAPACITY é o número mínimo de depósitos antes que um determinado depósito seja transformado em uma árvore.

TreeNodeé uma maneira alternativa de armazenar as entradas que pertencem a um único compartimento do HashMap. Em implementações mais antigas, as entradas de um compartimento eram armazenadas em uma lista vinculada. No Java 8, se o número de entradas em um compartimento ultrapassar um limite ( TREEIFY_THRESHOLD), elas serão armazenadas em uma estrutura em árvore em vez da lista vinculada original. Esta é uma otimização.

Desde a implementação:

/*
 * 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.

Você precisaria visualizá-lo: digamos que haja uma chave de classe com apenas a função hashCode () substituída para retornar sempre o mesmo 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 
  }

}

e em outro lugar, estou inserindo 9 entradas em um HashMap com todas as chaves sendo instâncias desta classe. por exemplo

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
              /   \   /  \

A travessia da árvore é mais rápida {O (log n)} do que LinkedList {O (n)} e, à medida que n cresce, a diferença se torna mais significativa.

A mudança na implementação do HashMap foi adicionada ao JEP-180 . O objetivo era:

Melhore o desempenho de java.util.HashMap sob condições de alta colisão de hash usando árvores balanceadas em vez de listas vinculadas para armazenar entradas de mapa. Implemente a mesma melhoria na classe LinkedHashMap

No entanto, o desempenho puro não é o único ganho. Isso também impedirá o ataque de HashDoS , no caso de um mapa hash ser usado para armazenar a entrada do usuário, porque a árvore vermelho e preto usada para armazenar dados no depósito tem o pior caso de complexidade de inserção em O (log n). A árvore é usada depois que um determinado critério é atendido - veja a resposta de Eugene .

Para entender a implementação interna do hashmap, você precisa entender o hashing. Hashing em sua forma mais simples, é uma maneira de atribuir um código único para qualquer variável / objeto após aplicar qualquer fórmula / algoritmo em suas propriedades.

Uma verdadeira função hash deve seguir esta regra -

“A função hash deve retornar o mesmo código hash toda vez que a função for aplicada a objetos iguais ou iguais. Em outras palavras, dois objetos iguais devem produzir o mesmo código hash de forma consistente. ”