Compartilhamento de tecnologia

Análise de código-fonte HashMap

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Índice

1: processo de método put

Dois: método get

Três: Mecanismo de expansão

1: processo de método put

  1. public V put(K key, V value) {
  2.     return putVal(hash(key), key, value, false, true);
  3. }
  4.  
  5. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  6.                    boolean evict) {
  7.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  8.     //判断数组是否未初始化
  9.     if ((tab = table) == null || (n = tab.length) == 0)
  10.         //如果未初始化，调用resize方法 进行初始化
  11.         n = (tab = resize()).length;
  12.     //通过 & 运算求出该数据（key）的数组下标并判断该下标位置是否有数据
  13.     if ((p = tab[i = (n - 1) & hash]) == null)
  14.         //如果没有，直接将数据放在该下标位置
  15.         tab[i] = newNode(hash, key, value, null);
  16.     //该数组下标有数据的情况
  17.     else {
  18.         Node<K,V> e; K k;
  19.         //判断该位置数据的key和新来的数据是否一样
  20.         if (p.hash == hash &&
  21.             ((k = p.key) == key || (key != null && key.equals(k))))
  22.             //如果一样，证明为修改操作，该节点的数据赋值给e,后边会用到
  23.             e = p;
  24.         //判断是不是红黑树
  25.         else if (p instanceof TreeNode)
  26.             //如果是红黑树的话，进行红黑树的操作
  27.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  28.         //新数据和当前数组既不相同，也不是红黑树节点，证明是链表
  29.         else {
  30.             //遍历链表
  31.             for (int binCount = 0; ; ++binCount) {
  32.                 //判断next节点，如果为空的话，证明遍历到链表尾部了
  33.                 if ((e = p.next) == null) {
  34.                     //把新值放入链表尾部
  35.                     p.next = newNode(hash, key, value, null);
  36.                     //因为新插入了一条数据，所以判断链表长度是不是大于等于8
  37.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  38.                         //如果是，进行转换红黑树操作
  39.                         treeifyBin(tab, hash);
  40.                     break;
  41.                 }
  42.                 //判断链表当中有数据相同的值，如果一样，证明为修改操作
  43.                 if (e.hash == hash &&
  44.                     ((k = e.key) == key || (key != null && key.equals(k))))
  45.                     break;
  46.                 //把下一个节点赋值为当前节点
  47.                 p = e;
  48.             }
  49.         }
  50.         //判断e是否为空（e值为修改操作存放原数据的变量）
  51.         if (e != null) { // existing mapping for key
  52.             //不为空的话证明是修改操作，取出老值
  53.             V oldValue = e.value;
  54.             //一定会执行  onlyIfAbsent传进来的是false
  55.             if (!onlyIfAbsent || oldValue == null)
  56.                 //将新值赋值当前节点
  57.                 e.value = value;
  58.             afterNodeAccess(e);
  59.             //返回老值
  60.             return oldValue;
  61.         }
  62.     }
  63.     //计数器，计算当前节点的修改次数
  64.     ++modCount;
  65.     //当前数组中的数据数量如果大于扩容阈值
  66.     if (++size > threshold)
  67.         //进行扩容操作
  68.         resize();
  69.     //空方法
  70.     afterNodeInsertion(evict);
  71.     //添加操作时 返回空值
  72.     return null;
  73. }

Dois: método get

  1. public V get(Object key) {
  2.     Node<K,V> e;
  3.     //hash(key)，获取key的hash值
  4.     //调用getNode方法，见下面方法
  5.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  6. }
  7.  
  8.  
  9. final Node<K,V> getNode(int hash, Object key) {
  10.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  11.     //找到key对应的桶下标，赋值给first节点
  12.     if ((tab = table) != null && (n = tab.length) > 0 &&
  13.         (first = tab[(n - 1) & hash]) != null) {
  14.         //判断hash值和key是否相等，如果是，则直接返回，桶中只有一个数据（大部分的情况）
  15.         if (first.hash == hash && // always check first node
  16.             ((k = first.key) == key || (key != null && key.equals(k))))
  17.             return first;
  18.         
  19.         if ((e = first.next) != null) {
  20.             //该节点是红黑树，则需要通过红黑树查找数据
  21.             if (first instanceof TreeNode)
  22.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  23.             
  24.             //链表的情况，则需要遍历链表查找数据
  25.             do {
  26.                 if (e.hash == hash &&
  27.                     ((k = e.key) == key || (key != null && key.equals(k))))
  28.                     return e;
  29.             } while ((e = e.next) != null);
  30.         }
  31.     }
  32.     return null;
  33. }

Três: Mecanismo de expansão

  1. //扩容、初始化数组
  2. final Node<K,V>[] resize() {
  3.         Node<K,V>[] oldTab = table;
  4.     	//如果当前数组为null的时候，把oldCap老数组容量设置为0
  5.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  6.         //老的扩容阈值
  7.     	int oldThr = threshold;
  8.         int newCap, newThr = 0;
  9.         //判断数组容量是否大于0，大于0说明数组已经初始化
  10.     	if (oldCap > 0) {
  11.             //判断当前数组长度是否大于最大数组长度
  12.             if (oldCap >= MAXIMUM_CAPACITY) {
  13.                 //如果是，将扩容阈值直接设置为int类型的最大数值并直接返回
  14.                 threshold = Integer.MAX_VALUE;
  15.                 return oldTab;
  16.             }
  17.             //如果在最大长度范围内，则需要扩容  OldCap << 1等价于oldCap*2
  18.             //运算过后判断是不是最大值并且oldCap需要大于16
  19.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  20.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  21.                 newThr = oldThr << 1; // double threshold  等价于oldThr*2
  22.         }
  23.     	//如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在，       			如果是首次初始化，它的临界值则为0
  24.         else if (oldThr > 0) // initial capacity was placed in threshold
  25.             newCap = oldThr;
  26.         //数组未初始化的情况，将阈值和扩容因子都设置为默认值
  27.     	else {               // zero initial threshold signifies using defaults
  28.             newCap = DEFAULT_INITIAL_CAPACITY;
  29.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  30.         }
  31.     	//初始化容量小于16的时候，扩容阈值是没有赋值的
  32.         if (newThr == 0) {
  33.             //创建阈值
  34.             float ft = (float)newCap * loadFactor;
  35.             //判断新容量和新阈值是否大于最大容量
  36.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  37.                       (int)ft : Integer.MAX_VALUE);
  38.         }
  39.     	//计算出来的阈值赋值
  40.         threshold = newThr;
  41.         @SuppressWarnings({"rawtypes","unchecked"})
  42.         //根据上边计算得出的容量 创建新的数组       
  43.     	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  44.     	//赋值
  45.     	table = newTab;
  46.     	//扩容操作，判断不为空证明不是初始化数组
  47.         if (oldTab != null) {
  48.             //遍历数组
  49.             for (int j = 0; j < oldCap; ++j) {
  50.                 Node<K,V> e;
  51.                 //判断当前下标为j的数组如果不为空的话赋值个e，进行下一步操作
  52.                 if ((e = oldTab[j]) != null) {
  53.                     //将数组位置置空
  54.                     oldTab[j] = null;
  55.                     //判断是否有下个节点
  56.                     if (e.next == null)
  57.                         //如果没有，就重新计算在新数组中的下标并放进去
  58.                         newTab[e.hash & (newCap - 1)] = e;
  59.                    	//有下个节点的情况，并且判断是否已经树化
  60.                     else if (e instanceof TreeNode)
  61.                         //进行红黑树的操作
  62.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  63.                     //有下个节点的情况，并且没有树化（链表形式）
  64.                     else {
  65.                         //比如老数组容量是16，那下标就为0-15
  66.                         //扩容操作*2，容量就变为32，下标为0-31
  67.                         //低位：0-15，高位16-31
  68.                         //定义了四个变量
  69.                         //        低位头          低位尾
  70.                         Node<K,V> loHead = null, loTail = null;
  71.                         //        高位头		   高位尾
  72.                         Node<K,V> hiHead = null, hiTail = null;
  73.                         //下个节点
  74.                         Node<K,V> next;
  75.                         //循环遍历
  76.                         do {
  77.                             //取出next节点
  78.                             next = e.next;
  79.                             //通过 与操作 计算得出结果为0
  80.                             if ((e.hash & oldCap) == 0) {
  81.                                 //如果低位尾为null，证明当前数组位置为空，没有任何数据
  82.                                 if (loTail == null)
  83.                                     //将e值放入低位头
  84.                                     loHead = e;
  85.                                 //低位尾不为null，证明已经有数据了
  86.                                 else
  87.                                     //将数据放入next节点
  88.                                     loTail.next = e;
  89.                                 //记录低位尾数据
  90.                                 loTail = e;
  91.                             }
  92.                             //通过 与操作 计算得出结果不为0
  93.                             else {
  94.                                  //如果高位尾为null，证明当前数组位置为空，没有任何数据
  95.                                 if (hiTail == null)
  96.                                     //将e值放入高位头
  97.                                     hiHead = e;
  98.                                 //高位尾不为null，证明已经有数据了
  99.                                 else
  100.                                     //将数据放入next节点
  101.                                     hiTail.next = e;
  102.                                //记录高位尾数据
  103.                                	hiTail = e;
  104.                             }
  105.                             
  106.                         } 
  107.                         //如果e不为空，证明没有到链表尾部，继续执行循环
  108.                         while ((e = next) != null);
  109.                         //低位尾如果记录的有数据，是链表
  110.                         if (loTail != null) {
  111.                             //将下一个元素置空
  112.                             loTail.next = null;
  113.                             //将低位头放入新数组的原下标位置
  114.                             newTab[j] = loHead;
  115.                         }
  116.                         //高位尾如果记录的有数据，是链表
  117.                         if (hiTail != null) {
  118.                             //将下一个元素置空
  119.                             hiTail.next = null;
  120.                             //将高位头放入新数组的(原下标+原数组容量)位置
  121.                             newTab[j + oldCap] = hiHead;
  122.                         }
  123.                     }
  124.                 }
  125.             }
  126.         }
  127.     	//返回新的数组对象
  128.         return newTab;
  129.     }

Quatro: Resumo

HashMap é uma das estruturas de dados comumente usadas em Java, usada para armazenar pares de valores-chave. A seguir está um resumo de vários cenários de uso comuns do HashMap:

1. Gerenciamento de cache: HashMap pode ser usado para implementar a função de cache, armazenando dados no HashMap na forma de pares chave-valor. Você pode obter os dados necessários consultando o HashMap, evitando o custo de recalcular ou consultar o banco de dados.

2. Índice de dados: HashMap é uma estrutura de dados que pode encontrar dados rapidamente. Ele pode encontrar rapidamente o valor correspondente com base na chave. Portanto, o HashMap pode ser usado para construir uma estrutura de índice e melhorar a eficiência da recuperação de dados.

3. Dicionário: HashMap pode ser usado para implementar a função de dicionário, armazenando palavras e significados correspondentes como pares de valores-chave no HashMap. Obtenha o significado correspondente por meio da chave de consulta para obter uma pesquisa rápida.

4. Estatísticas de frequência: HashMap pode ser usado para contar a frequência de ocorrência de cada elemento nos dados. Você pode usar o elemento como chave e o número de ocorrências como valor e obter o elemento com a maior frequência classificando ou consultando os valores.

5. Armazenamento e recuperação de dados: HashMap é uma estrutura de dados eficiente que pode ser usada para armazenar e recuperar grandes quantidades de dados. O valor correspondente pode ser encontrado rapidamente com base na chave, melhorando a eficiência do acesso aos dados.

Resumindo, o HashMap pode desempenhar um papel em cenários onde os dados precisam ser armazenados e recuperados e, devido ao seu método de acesso eficiente, é uma boa escolha na maioria dos casos.

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência