devbox
煮酒与君饮
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

HashMap源码解析

作者：煮酒与君饮 | 2024-07-13 22:55:52

赞

踩

HashMap源码解析

目录

一:put方法流程

二：get方法

三：扩容机制

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

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

三：扩容机制

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

四：总结

HashMap是Java中常用的数据结构之一，用于存储键值对的键值对。以下是HashMap的几个常见的使用场景总结：

1. 缓存管理：HashMap可以用于实现缓存功能，将数据存储在HashMap中，以键值对的形式保存。可以通过查询HashMap来获取需要的数据，避免了再次计算或查询数据库的开销。

2. 数据索引：HashMap是一种快速查找数据的数据结构，可以根据键快速找到对应的值。因此，HashMap可以用于构建索引结构，提高数据的检索效率。

3. 字典：HashMap可以用于实现字典功能，将单词与对应的意义作为键值对存储在HashMap中。通过查询键来获取对应的意义，实现快速查找。

4. 频率统计：HashMap可以用于统计数据中各个元素出现的频率。可以将元素作为键，出现的次数作为值，通过对值进行排序或查询，获取频率最高的元素。

5. 数据存储和检索：HashMap是一种高效的数据结构，可以用于存储和检索大量数据。可以根据键快速找到对应的值，提高数据的存取效率。

总之，HashMap可以在需要存储和检索数据的场景中发挥作用，并且由于其高效的存取方式，在大多数情况下，都是一个不错的选择。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/821953
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号