HashMap Java 8 implémentation

Question

Comme par le lien suivant document: Java HashMap mise en Œuvre

Je suis confus avec la mise en œuvre de l' HashMap (ou plutôt, une mise en valeur en HashMap). Mes questions sont les suivantes:

Tout d'abord

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

Pourquoi et comment sont ces constantes utilisées? Je veux des exemples de cette. La manière dont ils sont la réalisation d'un gain de performance par rapport à cela?

Deuxièmement

Si vous consultez le code source de l' HashMap dans le JDK, vous trouverez ci-après statique intérieur de la classe:

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;
        }
    }
    //...
}

Comment est-il utilisé? Je veux juste une explication de l'algorithme.

Answer 1

HashMap contient un certain nombre de compartiments. Il utilise hashCode pour déterminer le seau à les mettre en. Pour des raisons de simplicité l'imaginer comme un module.

Si notre hashcode est 123456 et nous avons 4 seaux, 123456 % 4 = 0 afin que l'élément va dans le premier seau, Seau de 1.

Si notre hashcode de la fonction est bonne, il doit fournir une répartition uniforme de sorte que tous les compartiments sera utilisé un peu aussi. Dans ce cas, le seau utilise une liste liée à stocker les valeurs.

Mais vous ne pouvez pas compter sur les gens pour mettre en place les bonnes fonctions de hachage. Les gens vont souvent écrire des pauvres des fonctions de hachage qui aboutira à un non-même de la distribution. Il est également possible que nous pourrions juste pas de chance avec nos entrées.

La encore moins de cette distribution est, plus nous avançons en O(1) opérations et plus nous nous dirigeons vers O(n) opérations.

La mise en œuvre de la Hashmap tente d'atténuer ce, par l'organisation de certains compartiments des arbres plutôt que des listes liées si les seaux devient trop grand. C'est ce qu' TREEIFY_THRESHOLD = 8 est pour. Si un seau contient plus de huit éléments, il devrait devenir un arbre.

C'est un arbre Rouge-Noir arbre. Il est tout d'abord triés par code de hachage. Si le hash codes sont les mêmes, il utilise l' compareTo méthode de Comparable si les objets à implémenter cette interface, sinon l'identité de code de hachage.

Si les entrées sont supprimées de la carte, le nombre d'entrées dans le seau peut réduire, de sorte que cette structure de l'arbre n'est plus nécessaire. C'est ce que l' UNTREEIFY_THRESHOLD = 6 est pour. Si le nombre d'éléments dans un seau descend au-dessous de six, nous pourrions aussi bien aller en arrière à l'aide d'une liste liée.

Enfin, il y a l' MIN_TREEIFY_CAPACITY = 64.

Lorsqu'un hachage de la carte augmente en taille, il redimensionne automatiquement pour avoir plus de seaux. Si nous avons une petite carte de hachage, le risque de nous arriver très seaux pleins est assez élevé, parce que nous n'avons pas qui ont de nombreux compartiments différents pour mettre des trucs dans. C'est beaucoup mieux d'avoir un plus gros hachage de la carte, avec plus de seaux qui sont moins complète. Cette constante indique fondamentalement de ne pas commencer à faire des seaux dans les arbres si notre hash map est très petite, il devrait redimensionner à être plus première place.

---

Pour répondre à votre question au sujet de le gain de performance, ces optimisations ont été ajoutés pour améliorer le pire des cas. Je ne fais que spéculer, mais vous auriez probablement seulement voir une notable amélioration de la performance en raison de ces optimisations si votre hashCode fonction n'était pas très bonne.

---

Les Images sont à moi (merci MSPaint). De les réutiliser comme bon vous semble.

Answer 2

Pour le placer plus simple (autant que je le pouvais plus simple) + un peu plus de détails.

Ces propriétés dépendent beaucoup de l'intérieur des choses, ce serait très cool de le comprendre avant de le déplacer directement.

TREEIFY_THRESHOLD -> quand un seul seau est atteint (et le nombre total dépasse MIN_TREEIFY_CAPACITY), il est transformé en un parfait équilibre rouge/noir nœud de l'arborescence. Pourquoi? En raison de la vitesse de recherche. Pensez à ce sujet d'une manière différente:

il faudrait au plus 32 étapes pour rechercher une Entrée dans un seau/poubelle avec Entier.MAX_VALUE entrées.

Certains d'intro pour le sujet suivant. Pourquoi le nombre de bacs/seaux toujours une puissance de deux? Au moins deux raisons: plus rapide que modulo et modulo sur les nombres négatifs sera négatif. Et vous ne pouvez pas mettre une Entrée dans le "négatif" seau:

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

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

Au lieu de cela il y a une belle astuce utilisée à la place de modulo:

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

Qui est sémantiquement le même que modulo. Il va garder les bits de poids faible. Cela a une conséquence interessante lorsque vous faites:

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

Dans le cas ci-dessus, la décision de l'endroit où une entrée est prise en se basant sur les 4 derniers bits seulement de vous hashcode.

C'est là multipliant les seaux entre en jeu. Sous certaines conditions (qui prendra beaucoup de temps à expliquer dans le détail exact), les seaux sont doublé de taille. Pourquoi? Quand les seaux sont doublé de taille, il y a un peu plus de venir en jeu.

Si vous avez 16 seaux - les 4 derniers bits de l'hashcode décider où une entrée va. Vous double seaux: 32 seaux 5 derniers bits décider de l'endroit où l'entrée va aller.

Comme tel, ce processus est appelé re-hachage. Ce peut être lente. C'est (pour les personnes qui prennent soin) comme HashMap est "plaisanté" comme: rapide, rapide, rapide, slooow. Il existe d'autres implémentations de recherche pauseless hashmap...

Maintenant UNTREEIFY_THRESHOLD entre en jeu après re-hachage. À ce stade, certaines entrées peuvent se déplacer à partir de ce bacs à d'autres (ils ajoutent un peu plus à l' (n-1)&hash calcul et comme tel, il pourrait passer à d'autres seaux) et il pourrait atteindre ce UNTREEIFY_THRESHOLD. À ce stade, il n'est pas rentable de garder le bac red-black tree node, mais en tant que LinkedList au lieu de cela, comme

 entry.next.next....

MIN_TREEIFY_CAPACITY est le nombre minimum de seaux avant une certaine seau est transformée en un Arbre.

Answer 3

TreeNode est une autre façon de stocker les entrées appartenant à un seul groupe de HashMap . Dans les implémentations plus anciennes, les entrées d'une corbeille étaient stockées dans une liste chaînée. En Java 8, si le nombre d'entrées d'un bac a dépassé un seuil ( TREEIFY_THRESHOLD ), elles sont stockées dans une structure arborescente à la place de la liste liée d'origine. Ceci est une optimisation.

De la mise en œuvre:

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

Answer 4

Vous devez le visualiser: disons qu'il existe une clé de classe avec uniquement la fonction hashCode () remplacée pour toujours renvoyer la même valeur

 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 
  }

}
 

Et puis, ailleurs, j'insère 9 entrées dans un HashMap, toutes les clés étant des instances de cette classe. par exemple

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

La traversée des arbres est plus rapide {O (log n)} que LinkedList {O (n)} et à mesure que n grandit, la différence devient plus significative.

Answer 5

Le changement dans la table de hachage de la mise en œuvre a été ajouté avec JEP-180. Le but était de:

Améliorer les performances de java.util.HashMap sous haute hash collision conditions à l'aide équilibrée des arbres plutôt que des listes liées à stocker des entrées de mappage. Mettre en œuvre la même amélioration dans la LinkedHashMap classe

Cependant la performance pure n'est pas le seul gain. Il permettra également d' éviter HashDoS attaque, dans le cas d'un hachage de la carte est utilisé pour stocker les entrées de l'utilisateur, parce que le rouge noir de l'arbre qui est utilisé pour stocker des données dans le seau a pire des cas, l'insertion de la complexité en O(log n). L'arbre est utilisé après un certains critères sont remplis - voir Eugène de réponse.