Introduction détaillée à la classe de collection Java Hashmap (exemple de code)

Cet article vous apporte une introduction détaillée (exemple de code) sur la classe de collection Java Hashmap. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. aidé.

1. Introduction à HashMap

HashMap est une classe de collection très couramment utilisée dans le processus de développement des programmeurs. C'est une classe de collection qui existe sous la forme de paires clé-valeur,

En développement, on peut profiter de sa fonctionnalité de remplacement d'une clé lorsqu'elle existe pour mettre en œuvre une opération de déduplication mise à jour.

Dans une autre commodité, nous pouvons utiliser map et fastJson pour former rapidement le format de données json dont nous avons besoin.

Avant jdk1.8, HashMap existait sous forme de tableau + liste chaînée. Le hashCode de la clé put était calculé par la fonction de perturbation pour obtenir la valeur de hachage, puis la valeur était calculée par (n-). 1)&hash à la position correspondante (n représente la longueur du tableau),

Si un conflit de hachage survient, déterminez d'abord si la clé existe, et si elle existe, écrasez-la, sinon utilisez la "méthode zipper" " pour résoudre le conflit, forme ensuite une liste chaînée.

Mais après jdk1.8, HashMap a changé. Si la longueur de la liste chaînée actuelle est supérieure au seuil (la valeur par défaut est 8), alors la liste chaînée sera convertie en un arbre rouge-noir, accélérer la recherche.

2. Propriétés de HashMap

//La capacité initiale par défaut de HashMap est de 2^4=16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // alias 16

//La capacité maximale de HashMap

static final int MAXIMUM_CAPACITY = 1 << >// Le facteur de charge par défaut est lorsque la longueur du tableau est
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// Lorsque le nombre de nœuds sur le bucket est supérieur à cette valeur, il sera converti en un arbre rouge-noir
static final int TREEIFY_THRESHOLD = 8;

// Lorsque le nombre de nœuds sur le bucket est inférieur à cette valeur, l'arbre sera converti en liste chaînée
static final int UNTREEIFY_THRESHOLD = 6;

// Structure dans le bucket Convertir à la taille minimale de la table correspondant à l'arbre rouge-noir
static final int MIN_TREEIFY_CAPACITY = 64;

// Le tableau pour stocker les éléments est toujours une puissance de 2
transitoire Node

//Ensemble de stockage d'éléments spécifiques
transitoire Set> EntrySet;

//Nombre de stockage d'éléments, Notez que ce n'est pas égal à la longueur du tableau.
transient int size;

// Compteur pour chaque extension et changement de structure de la carte
transient int modCount;

//La valeur critique est la taille réelle (capacité * remplissage facteur) Lorsqu'il dépasse la valeur critique, il sera étendu (*Lorsque
est supérieur ou égal à

, le mécanisme d'expansion ne sera pas nécessairement déclenché, mais il le sera très probablement, tant qu'il y aura est un

hachage nouvellement créé S'il y a un conflit, immédiatement size)threshold int seuil;Entryresize// Facteur de remplissage Lorsque Taille>= seuil, alors l'expansion du tableau doit être prise en compte , c'est-à-dire ce que cela signifie C'est une norme pour mesurer si le tableau doit être étendu
final float loadFactor;

3. Mécanisme d'expansion HashMap

Le le code pour tableSizeFor est :

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

>> Le nombre de la puissance carrée de 2, il est donc fixé ici que la capacité de HashMap doit être la puissance carrée de 2

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

Comme pour pourquoi c'est le nombre de la puissance carrée de 2, la raison est la suivante :

1.put Code source de la méthode :

Voir où p = tab[i = ( n - 1) & hash]) == null Cette phrase (n - 1) & hash est calculée sur une position, si celle-ci Si la position dans l'onglet est vide, effectuez directement l'opération d'insertion.

Par exemple, supposons qu'il y ait 16 postes et que 4 étudiants aient leur propre numéro d'étudiant

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

此时我们分配位置的时候可以采用 1%16 = 1；2%16=2；3%16 = 3；4%16=4；给他们分配位置,但是考虑到性能问题。由于%操作比&慢10倍左右，因此采用&运算会提高性能。

通过限制length是一个2的幂数， (n - 1) & hash和hash%n结果是一致的。这就是为什么要限制容量必须是一个2的幂的原因。

比如2的hashCode是2 那么它对应的二进制是 （0000 0010）

假设n=16

那么n-1=15对应的二进制是 1111 1111 & 0000 0010 = 1111 1111 = 0010 = 2

2%16=2

得到(n - 1) & hash和hash%n结果是一致的,考虑到性能所以每次的扩容都是以2的幂次方扩容。

四.HashMap的简单应用

public  static void mapMethod() {
		HashMap<String, Object> map = new HashMap<>();
		map.put("zhangsan", 11);
		map.put("lisi", 11);
		//重复key会覆盖
		map.put("zhangsan", 22);
		//便利
		for(String key:map.keySet()) {
			//根据key获取value
			System.out.println(key+"=======value:"+map.get(key));
		}
		//containsKey方法判断当前map是否包含该方法
		System.out.println(map.containsKey("zhangsan"));
		//size打印map的长度
		System.out.println(map.size());
		//移除key
		map.remove("zhangsan");
		//判断是否存在value
		System.out.println(map.containsValue("22"));
	}

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!