Analyse détaillée du code source du framework de collection Java HashSet et HashMap (photo)

Introduction générale

La raison pour laquelle HashSet et HashMap sont expliqués ensemble est qu'ils ont la même implémentation en Java, et le premier est juste pour le second est une couche d'emballage, ce qui signifie que HashSet a un HashMap (mode adaptateur) à l'intérieur. Par conséquent, cet article se concentrera sur l’analyse du HashMap.

HashMap implémente l'interface Map, permettant de placer des éléments null Sauf que cette classe n'implémente pas la synchronisation, le reste est à peu près le même que <.> et TreeMapHashtable, ce conteneur ne garantit pas l'ordre des éléments. Le conteneur peut re-hacher les éléments selon les besoins, et l'ordre des éléments sera également remanié, donc le même <.>HashMap est itéré à différents moments. L'ordre peut varier. Selon les différentes manières de gérer les conflits, il existe deux façons d'implémenter des tables de hachage, l'une est l'adressage ouvert et l'autre est une liste liée de conflit (chaînage séparé avec des listes

liées).

Java HashMap utilise la méthode de liste chaînée de conflit .

Il est facile de voir à partir de la figure ci-dessus que si vous choisissez la fonction de hachage

appropriée, les méthodes

et peuvent être réalisé en temps constant. Mais lors d'une itération sur HashMapput(), vous devez parcourir l'intégralité de la table et la liste chaînée des conflits qui suit. Par conséquent, pour les scénarios avec des itérations fréquentes, il n'est pas approprié de définir la taille initiale de get()HashMap trop grande. a deux paramètres qui peuvent affecter les performances de HashMap

 : la capacité initiale et le facteur de charge. La capacité initiale spécifie la taille initiale de

et le facteur de charge est utilisé pour spécifier la valeur critique pour l'expansion automatique. Lorsque le nombre de dépasse , le conteneur sera automatiquement agrandi et rehaché. Pour les scénarios dans lesquels un grand nombre d’éléments sont insérés, la définition d’une capacité initiale plus grande peut réduire le nombre de répétitions. Lorsque tableentry est placé dans capacity*load_factorHashMap

ou

HashSet, deux méthodes nécessitent une attention particulière : et . La méthode hashCode() détermine dans quel equals() l' objet hashCode() sera placé. Lorsque les valeurs de hachage de plusieurs objets sont en conflit, la méthode détermine si ces objets sont "les mêmes un". Objet”. Par conséquent, si vous souhaitez placer un objet personnalisé dans bucket ou equals(), vous avez besoin des méthodes @Override et HashMap. HashSethashCode()Méthode d'analyseequals()

get()

get(<h3>Objet</h3> <a href="http://www.php.cn/%20La%20m%C3%A9thode%20wiki/1051.html" target="_blank">key<p>)</p></a> renvoie le get(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object</a> <a href="http://www.php.cn/wiki/1051.html" target="_blank">key</a>) correspondant en fonction de la valeur key spécifiée. Cette méthode appelle value pour obtenir le getEntry(Object key) correspondant . Puis reviens entry. entry.getValue() est donc le cœur de l’algorithme. L'idée de l'algorithme getEntry() est d'obtenir d'abord l'indice correspondant à

via la fonction hash(), puis de parcourir la liste chaînée de conflit dans l'ordre et d'utiliser la méthode bucket pour déterminer si c'est le key.equals(k) que vous recherchez. entry

Dans la figure ci-dessus,

est équivalent à hash(k)&(table.length-1) La raison est que hash(k)%table.lengthHashMap exige que soit un exposant. de 2, donc table.lengthC'est-à-dire que les bits de poids faible du système binaire sont tous 1. Le ET avec table.length-1 effacera tous les bits de poids fort de la valeur de hachage, et le reste est le reste. La méthode hash(k)

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[hash&(table.length-1)];//得到冲突链表
         e != null; e = e.next) {//依次遍历冲突链表中的每个entry
        Object k;
        //依据equals()方法判断是否相等
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

put()

ajoute la paire put(K key, V value) spécifiée à key, value. Cette méthode recherchera d'abord map pour voir s'il contient le tuple, s'il est inclus, il retournera directement. Le processus de recherche est similaire à la méthode map s'il n'est pas trouvé, un nouveau getEntry() sera. inséré via la méthode addEntry(int hash, K key, V value, int bucketIndex) 🎜>, la méthode d'insertion est la entry méthode d'insertion de la tête .

//addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//自动扩容，并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);//hash%table.length
    }
    //在冲突链表头部插入新的entry
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

remove()

est utilisé pour supprimer le remove(Object key) correspondant à la valeur key La logique spécifique de. cette méthode est implémentée dans entry. La méthode removeEntryForKey(Object key) trouvera d'abord le removeEntryForKey() correspondant à la valeur key, puis supprimera le entry (modifier le pointeur correspondant de la liste chaînée). Le processus de recherche est similaire au processus entry. getEntry()

//removeEntryForKey()
final Entry<K,V> removeEntryForKey(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);//hash&(table.length-1)
    Entry<K,V> prev = table[i];//得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {//遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry
            modCount++; size--;
            if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry
            else prev.next = next;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

HashSet

前面已经说过HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法，因此HashSet的实现非常简单，只有不到300行代码。这里不再赘述。

//HashSet是对HashMap的简单包装
public class HashSet<E>
{
    ......
    private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

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!