HashMap est une structure complexe composée d'un tableau et d'une liste chaînée. La valeur de hachage détermine la position de la valeur clé dans le tableau. Lorsque les valeurs de hachage sont les mêmes, il est stocké sous la forme d'une liste chaînée. Lorsque la longueur de la liste chaînée Lorsque le seuil défini est atteint, elle sera arborescente pour garantir la sécurité des données et l'efficacité des opérations liées aux données
Les performances de HashMap dépendent de l'efficacité du code de hachage, donc les bases des règles d'accord hashCode et égal sont particulièrement importantes, telles que : si égal est égal, hashCode doit être égal si hashCode est réécrit, égal à hashCode ; doit maintenir la cohérence, et la valeur de hachage renvoyée par le changement de statut doit toujours être cohérente ; la symétrie, la réflexion et la transmission des égaux, etc. Caractéristiques
Différences entre HashMap et Hashtable, TreeMap
HashMap : table de hachage asynchrone basée sur un tableau, prend en charge la clé nulle ou Value est le premier choix pour les scénarios de données d'accès par paire clé-valeurHashtable : un tableau Table de hachage synchronisée basée sur qui ne prend pas en charge les clés ou les valeurs nulles. Étant donné que la synchronisation a un impact sur les performances, elle est rarement utiliséeTreeMap : une carte qui fournit un accès séquentiel basé sur des arbres rouge-noir. Elle économise de l'espace par rapport à HashMap. , mais la complexité temporelle de son opération de données (recherche, ajout, suppression) est : O (log (n)), ce qui est différent de HashMap. Prend en charge les valeurs nulles. Lorsque la clé est vide et que l'interface Comparator n'est pas implémentée, une NullPointerException se produit. L'implémentation de l'interface Comparator et le jugement de l'objet nul peuvent obtenir un stockage normal HashMap, Hashtable et TreeMap utilisent tous la clé. -Paires de valeurs Les formulaires stockent ou manipulent des éléments de données. HashMap et TreeMap héritent de la classe AbstractMap, et Hashtable hérite de la classe Dictionary Tous les trois implémentent l'interface MapAnalyse du code source HashMap
public HashMap(int initialCapacity, float loadFactor){
// ...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
} public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定义新tab数组及node对象
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果原table是空的或者未存储任何元素则需要先初始化进行tab的初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 当数组中对应位置为null时，将新元素放入数组中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 若对应位置不为空时处理哈希冲突
else {
Node<K,V> e; K k;
// 1 - 普通元素判断： 更新数组中对应位置数据
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2 - 红黑树判断：当p为树的节点时，向树内插入节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 3 - 链表判断：插入节点
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;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 回调以允许LinkedHashMap后置操作
afterNodeAccess(e);
return oldValue;
}
}
// 更新修改次数
++modCount;
// 检查数组是否需要进行扩容
if (++size > threshold)
resize();
// 回调以允许LinkedHashMap后置操作
afterNodeInsertion(evict);
return null;
} if (++size > threshold)
resize(); if ((p = tab[i = (n - 1) & hash]) == null)
// 向数组赋值新元素
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果新插入的结点和table中p结点的hash值，key值相同的话
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);
// 链表长度大于8时，将链表转红黑树
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
p = e;
}
}
// 如果存在这个映射就覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 回调以允许LinkedHashMap后置操作
return oldValue;
}
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} final Node<K,V>[] resize() {
// 把当前底层数组赋值给oldTab，为数据迁移工作做准备
Node<K,V>[] oldTab = table;
// 获取当前数组的大小，等于或小于0表示需要初始化数组，大于0表示需要扩容数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取扩容的阈值（容量*负载系数）
int oldThr = threshold;
// 定义并初始化新数组长度和目标阈值
int newCap, newThr = 0;
// 判断是初始化数组还是扩容，等于或小于0表示需要初始化数组，大于0表示需要扩容数组。若 if(oldCap > 0)=true 表示需扩容而非初始化
if (oldCap > 0) {
// 判断数组长度是否已经是最大，MAXIMUM_CAPACITY =（2^30）
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值设置为最大
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 目标阈值扩展2倍，数组长度扩展2倍
newThr = oldThr << 1; // double threshold
}
// 表示需要初始化数组而不是扩容
else if (oldThr > 0)
// 说明调用的是HashMap的有参构造函数，因为无参构造函数并没有对threshold进行初始化
newCap = oldThr;
// 表示需要初始化数组而不是扩容，零初始阈值表示使用默认值
else {
// 说明调用的是HashMap的无参构造函数
newCap = DEFAULT_INITIAL_CAPACITY;
// 计算目标阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 当目标阈值为0时需重新计算，公式：容量（newCap）*负载系数（loadFactor）
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 根据以上计算结果将阈值更新
threshold = newThr;
// 将新数组赋值给底层数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// -------------------------------------------------------------------------------------
// 此时已完成初始化数组或扩容数组，但原数组内的数据并未迁移至新数组（扩容后的数组），之后的代码则是完成原数组向新数组的数据迁移过程
// -------------------------------------------------------------------------------------
// 判断原数组内是否有存储数据，有的话开始迁移数据
if (oldTab != null) {
// 开始循环迁移数据
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 将数组内此下标中的数据赋值给Node类型的变量e，并判断非空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 1 - 普通元素判断：判断数组内此下标中是否只存储了一个元素，是的话表示这是一个普通元素，并开始转移
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 2 - 红黑树判断：判断此下标内是否是一颗红黑树，是的话进行数据迁移
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 3 - 链表判断：若此下标内包含的数据既不是普通元素又不是红黑树，则它只能是一个链表，进行数据转移
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回初始化完成或扩容完成的新数组
return newTab;
}Par conséquent, la capacité prédéfinie satisfait, est supérieure au nombre d'éléments/facteur de charge estimé, et est une puissance de 2
Mais il convient de noter :S'il n'y a pas de besoin particulier, ne procédez pas facilement au changement, car le facteur de charge par défaut du JDK lui-même est très cohérent avec les besoins des scénarios courants. Si vous avez vraiment besoin d'ajuster, il est recommandé de ne pas définir une valeur supérieure à 0,75, car cela augmenterait considérablement les conflits et réduirait les performances de HashMap. Si un facteur de charge trop faible est utilisé, la valeur de capacité prédéfinie sera également ajustée selon la formule ci-dessus, sinon cela pourrait entraîner une expansion plus fréquente de la capacité, augmenter les frais généraux inutiles et les performances d'accès elles-mêmes seront également affectées.
HashMap.get()
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 将table赋值给变量tab并判断非空 && tab 的厂部大于0 && 通过位运算得到求模结果确定链表的首节点赋值并判断非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断首节点hash值 && 判断key的hash值（地址相同 || equals相等）均为true则表示first即为目标节点直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 若首节点非目标节点，且还有后续节点时，则继续向后寻找
if ((e = first.next) != null) {
// 1 - 树：判断此节点是否为树的节点，是的话遍历树结构查找节点，查找结果可能为null
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 2 - 链表：若此节点非树节点，说明它是链表，遍历链表查找节点，查找结果可能为null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}Afin de garantir la sécurité des données et l'efficacité des opérations associées
Parce que pendant le processus de placement d'éléments, si un hachage d'objet entre en conflit et est placé dans le même compartiment, une liste chaînée sera formée. Nous savons que la requête de liste chaînée est linéaire, ce qui affectera sérieusement les performances d'accès
Dans le monde réel, la création de données de conflit de hachage n'est pas une affaire très compliquée. Un code malveillant peut utiliser ces données pour interagir en grande quantité avec le côté serveur, provoquant une utilisation importante du processeur côté serveur. Cela constitue un déni de collision de hachage. d'attaque de service. Domestique Des attaques similaires ont eu lieu contre des sociétés Internet de première ligneCe 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!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
