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=16static final int DEFAULT_INITIAL_CAPACITY = 1 7f47301affd17fbae2ab6dffd28e89c7> 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 à
hachage nouvellement créé S'il y a un conflit, immédiatement size
)threshold
int seuil;Entry
resize
// 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
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的幂次方扩容。
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!