HashMap（JDK8）源码分析（jdk8 hashmap原理）

2023-03-23 06:35:33 分类：java 阅读()

　　本篇文章为你整理了HashMap（JDK8）源码分析（jdk8 hashmap原理）的详细内容，包含有jdk1.7 hashmap源码 jdk8 hashmap原理 java hashmap 源码 jdk1.8 hashmap的实现原理 HashMap（JDK8）源码分析，希望能帮助你了解 HashMap（JDK8）源码分析。

　　get逻辑：

　　

HashMap数据结构为数组加链表加红黑树、只有当链表数量大于8时、才将链表转换为红黑树、时间复杂度由链表的O(N)转换为红黑树的O(logN)

 

　　// 主要看getNode下的方法、传入key的hash值和key

　　public V get(Object key) {

　　 Node K,V

　　 return (e = getNode(hash(key), key)) == null ? null : e.value;

　　// 返回一个Node对象、包含了key和value、在get方法中在返回value值

　　final Node K,V getNode(int hash, Object key) {

　　 // tab：Node K, V 对象数组

　　 Node K,V [] tab;

　　 // first: 指向key hash值对应的数组值 e: first对应Node对象的下一个节点

　　 Node K,V first, e;

　　 // n: 指向当前HashMpa的数组长度

　　 int n;

　　 // k: 临时变量、指向 key

　　 K k;

　　 // 这里检测HashMap对象的数组是否存在、长度是否大于0、((n - 1) hash)根据此表达式算出key对应的数组位置、在检查是否存在对象。

　　 if (

　　 (tab = table) != null

　　 (n = tab.length) 0

　　 (first = tab[(n - 1) hash]) != null

　　 // first当前值为一个Node节点

　　 // 这个if是检测当前的first指向的Node是否是要获取的对象

　　 // 直接判断first的hash值和要获取的hash值是否一直、并且key的值是否一直、通过 ==判断地址!=null和equals判断、key赋值为first的key

　　 if (first.hash == hash ((k = first.key) == key (key != null key.equals(k))))

　　 // 判断一致后直接返回要获取的Node节点给get、get在返回Node的value值

　　 return first;

　　 // 由于上面查找都查找不到、所以要查找Node的下一个节点、即查询链表或者红黑树

　　 if ((e = first.next) != null) {

　　 // 检查first对象是否是TreeNode（红黑树）

　　 if (first instanceof TreeNode)

　　 // 当前first为红黑树对象、直接根据key调用内部的检索方法获取对应的value

　　 return ((TreeNode K,V )first).getTreeNode(hash, key);

　　 do {

　　 // 链表查询、由于first上面判断过不是要查找的对象、e在上面语句已经指向first下一个节点、所以直接开始判断

　　 // 和上面的判断一样、检查hash值和key、qeuals判断、如果有则返回对应的Node对象、没有则最终执行下面的return null;语句。

　　 if (e.hash == hash

　　 ((k = e.key) == key (key != null key.equals(k))))

　　 return e;

　　 } while ((e = e.next) != null);

　　 // 表示当前对象并没有存储相关的key值、返回null

　　 return null;

　　

 

　　put逻辑

　　

public V put(K key, V value) {

 

　　 // 内部调用putVal设置值、参数如下int hash, K key, V value, boolean onlyIfAbsent（如果为 true，则不更改现有值）,boolean evict（如果为 false，则表处于创建模式）

　　 return putVal(hash(key), key, value, false, true);

　　// 参数如下int hash, K key, V value, boolean onlyIfAbsent（如果为 true，则不更改现有值）,boolean evict（如果为 false，则表处于创建模式）

　　final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

　　 boolean evict) {

　　 // tab指向当前HashMap对象数组

　　 Node K,V [] tab;

　　 // p指向key的hash值所在的数组Node对象

　　 Node K,V

　　 // n：HashMap数组的长度、i：key的hash值对应的索引（index）

　　 int n, i;

　　 // 判断当前HashMap的数组对象是否为空、并且长度是否为0

　　 if ((tab = table) == null (n = tab.length) == 0)

　　 // 分配数组空间并把长度返回给n

　　 n = (tab = resize()).length;

　　 // 计算hash对应的索引是否有对象存在、没有的话则创建Node对象、并将要put的值写入Node对象、在返回给数组

　　 if ((p = tab[i = (n - 1) hash]) == null)

　　 tab[i] = newNode(hash, key, value, null);

　　 // 要将Node对象写入到链表或者红黑树中

　　 else {

　　 // e: 代表最终你要写入的Node对象

　　 Node K,V

　　 // k: 指向hash值对象的Node节点的key

　　 K k;

　　 // 检查是否是同一个hash值、key是否相对或者进行equals判断

　　 if (p.hash == hash

　　 ((k = p.key) == key (key != null key.equals(k))))

　　 // 代表同一个对象、赋值给e、最后在写入值

　　 e = p;

　　 // 检测是否是红黑树节点

　　 else if (p instanceof TreeNode)

　　 // 检测是红黑树对象、直接调用内部的写入方法、在返回一个Node K, V 节点对象、最后在写入值、putTreeVal里面其实已经写入value了、后面在写入一次。

　　 e = ((TreeNode K,V )p).putTreeVal(this, tab, hash, key, value);

　　 else {

　　 // 链表操作、binCount检测有多少个链表节点、根据TREEIFY_THRESHOLD常量设定的值8、超过8个链表节点、则将该链表转换为红黑树

　　 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;

　　 // 检测当前插入的对象是否一致、一致的话直接返回e、下面在将要写入的值赋值给变量e对象

　　 if (e.hash == hash

　　 ((k = e.key) == key (key != null key.equals(k))))

　　 break;

　　 p = e;

　　 // 检测e对象是否不为空、不为空则下面写入对应的value值

　　 if (e != null) { // existing mapping for key

　　 V oldValue = e.value;

　　 // onlyIfAbsent为true表示不更新对象

　　 if (!onlyIfAbsent oldValue == null)

　　 // 将值写入

　　 e.value = value;

　　 afterNodeAccess(e);

　　 return oldValue;

　　 ++modCount;

　　 // 当前数组长度自增1大于上次扩容长度后、重新扩容并且把重新扩容的大小赋值给threshold

　　 if (++size threshold)

　　 // 重新调整数组长度

　　 resize();

　　 // LinkedHashMap中重写了、HashMap中没有具体实现

　　 afterNodeInsertion(evict);

　　 // 对应的key无法写入、返回null

　　 return null;

　　

 

　　数组扩容(resize)

　　

final Node K,V [] resize() {

 

　　 // 获取当前数组

　　 Node K,V [] oldTab = table;

　　 // 获取数组长度

　　 int oldCap = (oldTab == null) ? 0 : oldTab.length;

　　 // size threshold (capacity * loadFactor) 执行扩容

　　 int oldThr = threshold;

　　 int newCap, newThr = 0;

　　 if (oldCap 0) {

　　 // MAXIMUM_CAPACITY数组最大容量、如果大于等于则不扩容、直接返回数组

　　 if (oldCap = MAXIMUM_CAPACITY) {

　　 threshold = Integer.MAX_VALUE;

　　 return oldTab;

　　 // oldCap 1: 数组长度 * 2

　　 else if ((newCap = oldCap 1) MAXIMUM_CAPACITY

　　 oldCap = DEFAULT_INITIAL_CAPACITY)

　　 // newThr = oldThr * 2

　　 newThr = oldThr 1;

　　 // 数组长度为0时的情况、并且调用构造函数初始话过 loadFactor和threshold

　　 else if (oldThr 0)

　　 // 初始化新创建的数组长度

　　 newCap = oldThr;

　　 // 默认情况、即无参构造函数、第一次数组扩容会走这里

　　 else {

　　 // 默认数组长度16

　　 newCap = DEFAULT_INITIAL_CAPACITY;

　　 // 默认 threshold = 默认装载因子0.75f * 默认数组长度16 = 12

　　 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

　　 // 计算newThr、防止过大

　　 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"})

　　 // 创建新的数组、并返回给HashMap对象

　　 Node K,V [] newTab = (Node K,V [])new Node[newCap];

　　 table = newTab;

　　 // 对整个数据结构的重新操作、即将旧的数据结构（数组+链表+红黑树）中的数据一个个转移至新创建的数组中

　　 if (oldTab != null) {

　　 // 先对之前的长度遍历

　　 for (int j = 0; j oldCap; ++j) {

　　 // 临时Node节点

　　 Node K,V

　　 // 遍历之前的数组、从中取出数据转移至新数组中、并将之前的数组引用着的对象置为null、方便垃圾回收

　　 if ((e = oldTab[j]) != null) {

　　 oldTab[j] = null;

　　 // 数组中获得的节点没有下一个节点的情况

　　 if (e.next == null)

　　 // 直接给新数组传递Node节点

　　 newTab[e.hash (newCap - 1)] = e;

　　 // 当数组中的节点存在下一个节点并且是红黑树时

　　 else if (e instanceof TreeNode)

　　 // 红黑树数据转移

　　 ((TreeNode K,V )e).split(this, newTab, j, oldCap);

　　 // 当数组中的节点存在下一个节点并且是链表

　　 else {

　　 Node K,V loHead = null, loTail = null;

　　 Node K,V hiHead = null, hiTail = null;

　　 Node K,V next;

　　 // 循环遍历当前链表中的Node节点

　　 do {

　　 // 先获取下一个Node节点

　　 next = e.next;

　　 // 判断当前节点是否需要移位、即在新数组中的索引位置和旧数组的索引位置是否相同

　　 // 等价于 (e.hash (newCap - 1)) == j

　　 // 不移位的Node节点

　　 if ((e.hash oldCap) == 0) {

　　 if (loTail == null)

　　 loHead = e;

　　 else

　　 loTail.next = e;

　　 loTail = e;

　　 // 移位的Node节点

　　 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;

　　

 

　　红黑树节点转移

　　

final void split(HashMap K,V map, Node K,V [] tab, int index, int bit) {

 

　　 // 获取要转移的红黑树Node节点

　　 TreeNode K,V b = this;

　　 TreeNode K,V loHead = null, loTail = null;

　　 TreeNode K,V hiHead = null, hiTail = null;

　　 int lc = 0, hc = 0;

　　 // 遍历红黑树的Node节点、因为该Node继承了LinkedHashMap.Entry、所有可以根据next遍历整个树的节点

　　 for (TreeNode K,V e = b, next; e != null; e = next) {

　　 next = (TreeNode K,V )e.next;

　　 e.next = null;

　　 // 判断当前节点是否需要移位、即在新数组中的索引位置和旧数组的索引位置是否相同

　　 // 等价于 (e.hash (newCap - 1)) == j

　　 // 不移位的Node节点

　　 if ((e.hash bit) == 0) {

　　 if ((e.prev = loTail) == null)

　　 loHead = e;

　　 else

　　 loTail.next = e;

　　 loTail = e;

　　 ++lc;

　　 // 移位的Node节点

　　 else {

　　 if ((e.prev = hiTail) == null)

　　 hiHead = e;

　　 else

　　 hiTail.next = e;

　　 hiTail = e;

　　 ++hc;

　　 if (loHead != null) {

　　 // 检查红黑树节点数量、小于6则转换为链表

　　 if (lc = UNTREEIFY_THRESHOLD)

　　 tab[index] = loHead.untreeify(map);

　　 else {

　　 tab[index] = loHead;

　　 if (hiHead != null)

　　 // 将新的节点转换为红黑树

　　 loHead.treeify(tab);

　　 if (hiHead != null) {

　　 // 检查红黑树节点数量、小于6则转换为链表

　　 if (hc = UNTREEIFY_THRESHOLD)

　　 tab[index + bit] = hiHead.untreeify(map);

　　 else {

　　 tab[index + bit] = hiHead;

　　 if (loHead != null)

　　 // 将新的节点转换为红黑树

　　 hiHead.treeify(tab);

　　

 

　　关键变量解释

　　size表示HashMap中存放KV的数量（为链表和树中的KV的总和）。

　　capacity

　　capacity译为容量。capacity就是指HashMap中数组的数量。默认值为16。一般第一次扩容时会扩容到64，之后好像是2倍。总之，容量都是2的幂。

　　loadFactor

　　loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为：size/ capacity

　　默认值为0.75f，设置成0.75有一个好处，那就是0.75正好是3/4

　　对于一个默认的HashMap来说，默认情况下，当其size大于12(16*0.75)时就会触发扩容。

　　threshold

　　threshold表示当HashMap的size大于threshold时会执行resize(数组扩容)操作。
 

　　threshold = capacity * loadFactor

　　以上就是HashMap（JDK8）源码分析（jdk8 hashmap原理）的详细内容，想要了解更多 HashMap（JDK8）源码分析的内容，请持续关注盛行IT软件开发工作室。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

标签： java

相关文章阅读

  • java Springboot集成mybatis-plus的方法是什么
  • 浅谈几种Java自定义异常处理方式
  • Java Map所有的值转为String类型
  • java代码中格式化金额 java格式化小数
  • java计算器源代码资源 java计算器简单代码
  • 【java】（一）SpringBoot 源码解析——SpringApplication 初始化（）
  • Spring学习笔记（spring教程 csdn）
  • HDFS Architecture Guide（）
  • 哈工大软件构造Lab3（2022）（哈工大软件构造lab3）
  • nginx基础（nginx基础教程）
  • Java 中HashMap详解(含HashTable, ConcurrentHashMap)（java hashmap使用方法）
  • Java 线程池之Jetty 线程池学习总结（java线程池的使用方法）
  • java线程基础（java 线程教程）
  • 聊聊 Netty 那些事儿之 Reactor 在 Netty 中的实现(创建篇)（）
  • nginx（nginx负载均衡）
    • 留言与评论（共有 条评论）
       
    验证码：