Compartir tecnología

Análisis del código fuente de HashMap

2024-07-12

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

Tabla de contenido

1: proceso de método de colocación

Dos: método de obtención

Tres: mecanismo de expansión

1: proceso de método de colocación

  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. }

Dos: método de obtención

  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. }

Tres: mecanismo de expansión

  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.     }

Cuatro: resumen

HashMap es una de las estructuras de datos más utilizadas en Java y se utiliza para almacenar pares clave-valor. El siguiente es un resumen de varios escenarios de uso comunes de HashMap:

1. Gestión de caché: HashMap se puede utilizar para implementar la función de caché y almacenar datos en HashMap en forma de pares clave-valor. Puede obtener los datos requeridos consultando HashMap, evitando el costo de recalcular o consultar la base de datos.

2. Índice de datos: HashMap es una estructura de datos que puede encontrar datos rápidamente. Puede encontrar rápidamente el valor correspondiente según la clave. Por lo tanto, HashMap se puede utilizar para crear una estructura de índice y mejorar la eficiencia de la recuperación de datos.

3. Diccionario: HashMap se puede utilizar para implementar la función de diccionario, almacenando palabras y significados correspondientes como pares clave-valor en HashMap. Obtenga el significado correspondiente a través de la clave de consulta para lograr una búsqueda rápida.

4. Estadísticas de frecuencia: HashMap se puede utilizar para contar la frecuencia de aparición de cada elemento en los datos. Puede utilizar el elemento como clave y el número de apariciones como valor, y obtener el elemento con la frecuencia más alta ordenando o consultando los valores.

5. Almacenamiento y recuperación de datos: HashMap es una estructura de datos eficiente que se puede utilizar para almacenar y recuperar grandes cantidades de datos. El valor correspondiente se puede encontrar rápidamente según la clave, lo que mejora la eficiencia del acceso a los datos.

En resumen, HashMap puede desempeñar un papel en escenarios donde es necesario almacenar y recuperar datos y, debido a su método de acceso eficiente, es una buena opción en la mayoría de los casos.

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi información de contacto

Correo