Analyse du principe d'implémentation de HashMap en Java

Le contenu de cet article concerne l'analyse du principe d'implémentation de HashMap en Java. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Aperçu de HashMap :
HashMap est une implémentation asynchrone de l'interface Map basée sur des tables de hachage. Cette implémentation fournit toutes les opérations de mappage facultatives et autorise les valeurs nulles et les clés nulles. Cette classe ne garantit pas l'ordre du mappage, et en particulier elle ne garantit pas que l'ordre soit immuable.
2. Structure des données HashMap :
Dans le langage de programmation Java, il existe deux structures de base, l'une est un tableau et l'autre est un pointeur simulé (référence). Toutes les structures de données peuvent être construites à l'aide de ces deux structures de base, et HashMap ne fait pas exception. HashMap est en fait une structure de données de « hachage de liste chaînée », qui est une combinaison d'un tableau et d'une liste chaînée.
Comme vous pouvez le voir sur l'image ci-dessus, la couche inférieure de HashMap est une structure de tableau, et chaque élément du tableau est une liste chaînée. Lorsqu'un nouveau HashMap est créé, un tableau sera initialisé.

/** 
 * The table, resized as necessary. Length MUST Always be a power of two. 
 */  transient Entry[] table;  

static class Entry<K,V> implements Map.Entry<K,V> {  
    final K key;  
    V value;  
    Entry<K,V> next;  
    final int hash;  
    ……  
}

3. Implémentation de l'accès HashMap :
1) Stockage :

public V put(K key, V value) {  
    // HashMap允许存放null键和null值。  
    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  
    if (key == null)  
        return putForNullKey(value);  
    // 根据key的keyCode重新计算hash值。  
    int hash = hash(key.hashCode());  
    // 搜索指定hash值在对应table中的索引。  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
        Object k;  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
            V oldValue = e.value;  
            e.value = value;  
            e.recordAccess(this);  
            return oldValue;  
        }  
    }  
    // 如果i索引处的Entry为null，表明此处还没有Entry。  
    modCount++;  
    // 将key、value添加到i索引处。  
    addEntry(hash, key, value, i);  
    return null;  
}

Comme le montre le code source ci-dessus : lorsque nous mettons un élément dans le HashMap, nous recalculons d'abord la valeur de hachage en fonction du hashCode de la clé, et obtenons l'élément en fonction de la valeur de hachage. La position (c'est-à-dire l'indice) dans le tableau S'il y a d'autres éléments stockés à cette position dans le tableau, alors les éléments à cette position seront stockés sous la forme d'une liste chaînée. sera placé en tête de chaîne, et les premiers éléments ajoutés seront placés en tête de chaîne. S'il n'y a aucun élément à cette position dans le tableau, l'élément est directement placé à cette position dans le tableau.
La méthode addEntry(hash, key, value, i) place la paire clé-valeur à l'index i de la table du tableau en fonction de la valeur de hachage calculée. addEntry est une méthode d'accès au package fournie par HashMap. Le code est le suivant :

void addEntry(int hash, K key, V value, int bucketIndex) {  
    // 获取指定 bucketIndex 索引处的 Entry   
    Entry<K,V> e = table[bucketIndex];  
    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
    // 如果 Map 中的 key-value 对的数量超过了极限  
    if (size++ >= threshold)  
    // 把 table 对象的长度扩充到原来的2倍。  
        resize(2 * table.length);  
}

Lorsque le système décide de stocker les paires clé-valeur dans le HashMap, il ne prend pas en compte la valeur dans l'entrée à tout, mais uniquement en fonction de la clé. Calculez et déterminez l'emplacement de stockage de chaque entrée. Nous pouvons complètement considérer la valeur de la collection Map comme un accessoire de la clé. Une fois que le système a déterminé l'emplacement de stockage de la clé, la valeur peut y être stockée.

La méthode hash(int h) recalcule le hachage en fonction du hashCode de la clé. Cet algorithme ajoute un calcul de bits hauts pour éviter les conflits de hachage provoqués lorsque le bit bas reste inchangé et que le bit haut change.

static int hash(int h) {  
    h ^= (h >>> 20) ^ (h >>> 12);  
    return h ^ (h >>> 7) ^ (h >>> 4);  
}

On voit que pour trouver un élément dans un HashMap, il faut trouver la position dans le tableau correspondant en fonction de la valeur de hachage de la clé. Comment calculer cette position est l'algorithme de hachage. Comme mentionné précédemment, la structure de données de HashMap est une combinaison de tableau et de liste chaînée, nous espérons donc bien sûr que les positions des éléments dans ce HashMap soient réparties aussi uniformément que possible, de sorte qu'il n'y ait qu'un seul élément dans chaque position. nous utilisons l'algorithme de hachage pour obtenir A cette position, nous pouvons immédiatement savoir que l'élément à la position correspondante est ce que nous voulons, sans avoir à parcourir la liste chaînée, ce qui optimise grandement l'efficacité de la requête.

Pour tout objet donné, tant que sa valeur de retour hashCode() est la même, la valeur du code de hachage calculée par le programme appelant la méthode hash(int h) est toujours la même. La première chose à laquelle nous pensons est de prendre la valeur de hachage modulo la longueur du tableau, afin que la répartition des éléments soit relativement uniforme. Cependant, la consommation de l'opération "modulo" est encore relativement importante. Cela se fait dans HashMap : appelez la méthode indexFor(int h, int length) pour calculer à quel index du tableau l'objet doit être enregistré. Le code de la méthode indexFor(int h, int length) est le suivant :

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

Cette méthode est très astucieuse Elle utilise h & (table.length -1) pour obtenir le bit de stockage du. objet et le tableau sous-jacent de HashMap La longueur est toujours de 2 à la nième puissance, ce qui correspond à l'optimisation de la vitesse de HashMap. Il y a le code suivant dans le constructeur HashMap :

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

Ce code garantit que la capacité de HashMap lors de l'initialisation est toujours de 2 à la puissance n, c'est-à-dire que la longueur du tableau sous-jacent est toujours de 2 à la nième puissance.
Lorsque la longueur est toujours 2 à la nième puissance, l'opération h& (longueur-1) équivaut à prendre la longueur modulo, c'est-à-dire h%longueur, mais & est plus efficace que %.
Lorsque la longueur du tableau est de 2 élevée à la puissance n, la probabilité de calculer le même index pour différentes clés est faible, donc les données sont réparties uniformément sur le tableau, ce qui signifie que la probabilité de collision est faible. En revanche, la requête À ce stade, il n'est pas nécessaire de parcourir la liste chaînée à une certaine position, l'efficacité de la requête est donc plus élevée.

D'après le code source de la méthode put ci-dessus, on peut voir que lorsque le programme essaie de mettre une paire clé-valeur dans un HashMap, le programme détermine d'abord l'emplacement de stockage de l'entrée en fonction du valeur de retour hashCode() de la clé : si les valeurs de retour hashCode() de deux clés d'entrée sont les mêmes, alors leurs emplacements de stockage sont les mêmes. Si les clés de ces deux entrées renvoient vrai via une comparaison égale, la valeur de l'entrée nouvellement ajoutée écrasera la valeur de l'entrée d'origine dans la collection, mais la clé ne sera pas écrasée. Si les clés de ces deux entrées renvoient faux via une comparaison égale, l'entrée nouvellement ajoutée formera une chaîne d'entrée avec l'entrée d'origine dans la collection, et l'entrée nouvellement ajoutée est située en tête de la chaîne d'entrée - continuez à voir la description de la méthode addEntry() pour des instructions spécifiques.
(2) Lire

public V get(Object key) {  
    if (key == null)  
        return getForNullKey();  
    int hash = hash(key.hashCode());  
    for (Entry<K,V> e = table[indexFor(hash, table.length)];  
        e != null;  
        e = e.next) {  
        Object k;  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
            return e.value;  
    }  
    return null;  
}

有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

3) 归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
4. HashMap的resize（rehash）：
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
5. HashMap的性能参数：
HashMap 包含如下几个构造器：
HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。
HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。
initialCapacity：HashMap的最大容量，即为底层数组的长度。
loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。
负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。
HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：

if (size++ >= threshold)     
    resize(2 * table.length);

6. Fail-Fast机制：
我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

HashIterator() {  
    expectedModCount = modCount;  
    if (size > 0) { // advance to first entry  
    Entry[] t = table;  
    while (index < t.length && (next = t[index++]) == null)  
        ;  
    }  
}

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：
注意到modCount声明为volatile，保证线程之间修改的可见性。

final Entry<K,V> nextEntry() {     
    if (modCount != expectedModCount)     
        throw new ConcurrentModificationException();

在HashMap的API中指出：

Les itérateurs renvoyés par les « méthodes d'affichage de collection » de toutes les classes HashMap sont rapides : après la création de l'itérateur, si la carte est structurellement modifiée, sauf via la méthode remove de l'itérateur lui-même, tout autre Si le temps est modifié de quelque manière que ce soit, l'itérateur lancera ConcurrentModificationException. Par conséquent, face à des modifications concurrentes, l’itérateur échouera rapidement et complètement sans risquer un comportement arbitraire non spécifié à un moment futur non spécifié.

Notez que le comportement rapide des itérateurs n'est pas garanti et qu'en général, il est impossible de donner des garanties fermes lorsqu'il y a des modifications simultanées non synchronisées. Les itérateurs à échec rapide lancent ConcurrentModificationException au mieux. Par conséquent, c'est une erreur d'écrire un programme qui s'appuie sur cette exception ; l'approche correcte est que le comportement rapide des itérateurs doit être utilisé uniquement pour détecter les erreurs du programme.

Recommandations associées :

Compréhension approfondie du principe d'implémentation de HashMap en java (photo)

Explication détaillée du principe et implémentation de hashmap java sans verrouillage

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!