news 2026/5/1 11:21:45

HashMap底层原理常见面试题

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
HashMap底层原理常见面试题

章节目录

文章目录

  • 1.HashMap的底层数据结构
  • 2.HashMap的重要方法
    • 查询方法（get方法）
    • 新增（put方法）
    • 扩容（resize方法）
  • HashMap有哪些属性？
  • 为什么HashMap的初始化长度是16？（必须是2的幂次方）
  • 5.为什么树化是8，退树化是6？
  • 6.什么是加载因子？加载因子为什么是0.75？
  • 7.HashMap是线程安全的吗？
  • 7.为什么重写equals方法的时候，需要重新hashCode方法呢？
  • 9.HashMap死循环分析

1.HashMap的底层数据结构

  • 在JDK7中HashMap是以[数组+链表]的形式组成的；
  • JDK8以后新增了[红黑树]的组成结构；
  • 当链表长度大于8并且hash桶的容量大于64时，链表结构会转成红黑树结构。

HashMap 中数组的每一个元素又称为哈希桶，也就是 key-value 这样的实例。在Java7中叫 Entry，Java8中叫 Node。

它的源码为

staticclassNode<K,V>implementsMap.Entry<K,V>{finalinthash;finalKkey;Vvalue;Node<K,V>next;...}
  • 从这里我们可以看出来每个哈希桶中包含了4个字段：hash，key，value，next；
  • 其中next表示表示链表的下一个节点。

[!NOTE]

  • JDK8之所以添加红黑树是因为一旦链表过长，会严重影响HashMap的性能；
  • 而红黑树具有快速增删改查的特点，这样就可以有效的解决链表过长是操作比较慢的问题。

2.HashMap的重要方法

查询方法（get方法）

publicVget(Objectkey){Node<K,V>e;// 对 key 进行哈希操作return(e=getNode(hash(key),key))==null?null:e.value;}finalNode<K,V>getNode(inthash,Objectkey){Node<K,V>[]tab;Node<K,V>first,e;intn;Kk;// 非空判断if((tab=table)!=null&&(n=tab.length)>0&&(first=tab[(n-1)&hash])!=null){// 判断第一个元素是否是要查询的元素// always check first nodeif(first.hash==hash&&((k=first.key)==key||(key!=null&&key.equals(k))))returnfirst;// 下一个节点非空判断if((e=first.next)!=null){// 如果第一节点是树结构，则使用 getTreeNode 直接获取相应的数据if(firstinstanceofTreeNode)return((TreeNode<K,V>)first).getTreeNode(hash,key);do{// 非树结构，循环节点判断// hash 相等并且 key 相同，则返回此节点if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;}while((e=e.next)!=null);}}returnnull;}
  • 当hash冲突的时候，我们不仅需要判断hash值，还需要通过判断key值是否相等；
  • 才可以确定次元素是不是我们想要的元素。

新增（put方法）

publicVput(Kkey,Vvalue){// 对 key 进行哈希操作returnputVal(hash(key),key,value,false,true);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node<K,V>[]tab;Node<K,V>p;intn,i;// 哈希表为空则创建表if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;// 根据 key 的哈希值计算出要插入的数组索引 iif((p=tab[i=(n-1)&hash])==null)// 如果 table[i] 等于 null，则直接插入tab[i]=newNode(hash,key,value,null);else{Node<K,V>e;Kk;// 如果 key 已经存在了，直接覆盖 valueif(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;// 如果 key 不存在，判断是否为红黑树elseif(pinstanceofTreeNode)// 红黑树直接插入键值对e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);else{// 为链表结构，循环准备插入for(intbinCount=0;;++binCount){// 下一个元素为空时if((e=p.next)==null){p.next=newNode(hash,key,value,null);// 转换为红黑树进行处理if(binCount>=TREEIFY_THRESHOLD-1)// -1 for 1sttreeifyBin(tab,hash);break;}// key 已经存在直接覆盖 valueif(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}// existing mapping for keyif(e!=null){VoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;// 超过最大容量，扩容if(++size>threshold)resize();afterNodeInsertion(evict);returnnull;}

扩容（resize方法）

finalNode<K,V>[]resize(){// 扩容前的数组Node<K,V>[]oldTab=table;// 扩容前的数组的大小和阈值intoldCap=(oldTab==null)?0:oldTab.length;intoldThr=threshold;// 预定义新数组的大小和阈值intnewCap,newThr=0;if(oldCap>0){// 超过最大值就不再扩容了if(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;returnoldTab;}// 扩大容量为当前容量的两倍，但不能超过 MAXIMUM_CAPACITYelseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;// double threshold}// 当前数组没有数据，使用初始化的值elseif(oldThr>0)// initial capacity was placed in thresholdnewCap=oldThr;else{// zero initial threshold signifies using defaults// 如果初始化的值为 0，则使用默认的初始化容量newCap=DEFAULT_INITIAL_CAPACITY;newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}// 如果新的容量等于 0if(newThr==0){floatft=(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>[])newNode[newCap];// 开始扩容，将新的容量赋值给 tabletable=newTab;// 原数据不为空，将原数据复制到新 table 中if(oldTab!=null){// 根据容量循环数组，复制非空元素到新 tablefor(intj=0;j<oldCap;++j){Node<K,V>e;if((e=oldTab[j])!=null){oldTab[j]=null;// 如果链表只有一个，则进行直接赋值if(e.next==null)newTab[e.hash&(newCap-1)]=e;elseif(einstanceofTreeNode)// 红黑树相关的操作((TreeNode<K,V>)e).split(this,newTab,j,oldCap);else{// preserve order// 链表复制，JDK 1.8 扩容优化部分// 如果节点不为空，且为单链表，则将原数组中单链表元素进行拆分Node<K,V>loHead=null,loTail=null;//保存在原有索引的链表Node<K,V>hiHead=null,hiTail=null;//保存在新索引的链表Node<K,V>next;do{next=e.next;// 哈希值和原数组长度进行 & 操作，为 0 则在原数组的索引位置if((e.hash&oldCap)==0){if(loTail==null)loHead=e;elseloTail.next=e;loTail=e;}// 原索引 + oldCapelse{if(hiTail==null)hiHead=e;elsehiTail.next=e;hiTail=e;}}while((e=next)!=null);// 将原索引放到哈希桶中if(loTail!=null){loTail.next=null;newTab[j]=loHead;}// 将原索引 + oldCap 放到哈希桶中if(hiTail!=null){hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}}returnnewTab;}

扩容主要分为2步：

  • 扩容：创建一个新的Entry空数组，长度是原数组的2倍；

  • 位运算：原来的元素哈希值和原数组长度进行&运输。

  • JDK8在扩容时没有像JDK7那样重新计算每个元素的哈希值；

  • 而是通过高位运算（e.hash & oldCap）来确定元素是否需要移动；

  • 假如key1的信息为：key1.hash=10、二进制：0000 1010；oldCap = 16、二进制0001 0000；

  • 使用e.hash & oldCap得到的结果，高一位位0，当结果为0时表示元素在扩容时位置不会发生任何变化；

  • 当高1位为1是，表示元素在扩容时位置发生了变化，新的下标位置等于原下标位置+原数组长度。

HashMap有哪些属性？

// HashMap 初始化长度staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;// aka 16// HashMap 最大长度staticfinalintMAXIMUM_CAPACITY=1<<30;// 1073741824// 默认的加载因子 (扩容因子)staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;// 当链表长度大于此值且数组长度大于 64 时，会从链表转成红黑树staticfinalintTREEIFY_THRESHOLD=8;// 转换链表的临界值，当元素小于此值时，会将红黑树结构转换成链表结构staticfinalintUNTREEIFY_THRESHOLD=6;// 最小树容量staticfinalintMIN_TREEIFY_CAPACITY=64;

为什么HashMap的初始化长度是16？（必须是2的幂次方）

  • 我们观察前面的源码发现HashMap初始化长度用的是1<<4，而不是直接写16；
  • 这是因为位运算的方便，位运算比运算算数计算的效率高很多；
  • 之所以选择16，是为了服务Key映射到index的算法。

如何实现一个尽量均匀分布的Hash函数？从而尖山HashMap碰撞？

  • 通过Key的HashCode值来做位运算；
  • HashCode（Key） & （Length- 1）；

[!NOTE]

也就是：hash算法最终得到的index结果，取决于hashcode值的最后几位。

[!NOTE]

  • 可以把长度指定为10以及其他非2次幂的数字，做位预算；
  • 发现index出现相同的概率大大升高；
  • 而长度为16或者其他2次幂，length-1的值是所有二进制位全为1；
  • 这种情况下，index的结果等同于hashcode后几位的值；
  • 只要输入的hashCode本身分布均匀，hash算法的结果就是均匀的。

所以HashMap的默认长度为16，是为了降低hash碰撞的机率。

5.为什么树化是8，退树化是6？

  • 红黑树平均查找长度Log(n)，长度为8时，查找长度为3；
  • 而链表平均查找长度为N/2，也就是8/2；
  • 查找长度链表大于树，转换为树，效率更高；
  • 当为6时，树2.6、链表3；链表>树；
  • 这是应该来说还是树化合理，但是树化需要时间，为了这点效率牺牲时间是不划算的 🙅。

6.什么是加载因子？加载因子为什么是0.75？

  • 前面我们讲到了扩容机制。那么什么时候进行扩容？
  • 这取决于原数组长度和加载因子两个因素。

[!NOTE]

  • 加载因子也叫做扩容因子或者负载因子；
  • 用来判断什么时候进行扩容，假如加载因子为0.5，HashMap的初始化容量为16；
  • 那当HashMap中有16*0.5=8个元素时，HashMap就会扩容。

现在我们来分析为什么加载因子一定为0.75？

  • 为了提升扩容向量，HashMap的容量有一个固定的要求，那就是一定为2的幂；
  • 所以，如果负载因子为0.75，那么和容量乘积就可以是一个整数；
  • 当加载因子较大时，扩容门槛变高，扩容频率变低，占用空间小；
  • 但是此时发生Hash冲突可能性变高，因此需要更复杂的数据结构存储元素，对元素操作时间会增加，运行效率变低；
  • 当加载因子较小时，扩容门槛变低，占用空间大；
  • 此时元素存储比较稀疏，发生Hash冲突的可能性小，因此操作性会比较高；
  • 所以我们在0.5和1之间去了一个平均数为加载因子🌟。

7.HashMap是线程安全的吗？

  • 不是，get和put方法都没有上锁；
  • 多线程操作无法保障：此时put的值，片刻后get还是相同的值，会造成线程安全问题；
  • 但是有个HashTable是线程安全的，但是加锁的粒度太大；
  • 并发度降低，最多同时允许一个线程访问，性能不高，我们一般使用currentHashMap。

7.为什么重写equals方法的时候，需要重新hashCode方法呢？

[!IMPORTANT]

Java中，所以对象都是集成于Object类，Object类中有两个方法equals，hashCode，这两个方法都是用来比较两个对象是否相等的。

publicbooleanequals(Objectobj){return(this==obj);}
  • 在未重新equals方法，其就是==；
  • 对于值对象，==比较的是两个对象的值；
  • 对于引用对象，==比较的是两个对象的地址。

现在我们来分析为什么重写equals时候需要重写hashCode方法？

  • 前面我们分析到put方法时，HashMap是通过key的hashcode去寻找地址index的，如果index一样就会形成链表；
  • 在使用get方法的时候，当哈希冲突时我们不仅需要判断hash值，还需要通过判断key值是否相等，才能确认此元素是不是我们想要的元素；
  • 我们去get首先是找到hash值一样的，那怎么知道你想要的是哪个对象呢？
  • 就是利用equals方法，如果重新hashCode方法，不写equals方法，当发生hash冲突，hashCode一样时，就不知道去哪个对象了。

9.HashMap死循环分析

voidtransfer(Entry[]newTable,booleanrehash){intnewCapacity=newTable.length;for(Entry<K,V>e:table){while(null!=e){Entry<K,V>next=e.next;// 此处加断点if(rehash){e.hash=null==e.key?0:hash(e.key);}inti=indexFor(e.hash,newCapacity);e.next=newTable[i];newTable[i]=e;e=next;}}}
  • 上面是JDK7链表头插法，假设HashMap默认大小为2，原本HashMap中没有一个元素，3个线程添加3个元素；
  • 加入3个元素hash冲突，放到同一个链表，就是key1，key2，key3的顺序；

  • 此时HashMap进行扩容，就可能变为key1和key2还是同一个位置，这时形成链表；
  • 如果key2比key1后插入，根据头插法就变为key2，key1；

  • 链表反转：最终3个线程调整完毕，会出现死循环，这个时候get（key1）就会出现infinite Loop异常。

在JDK8这个问题得到了改善，变成了尾部正序插入，在扩容时会保持链表元素原本的顺序，就不会出现链表成环问题。

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/26 23:59:31

运营商信创系统 BCLinux 21.10 SP2 编译安装Mellanox网卡驱动 MLNX_EN-23.10（Mellanox OFED）全过程：原理、打包与内核适配

前言 写在前面&#xff1a;Mellanox 网卡、OFED 与本次编译的关系说明 在开始编译和安装 MLNX-EN / OFED 之前&#xff0c;有一个非常关键、但经常被忽略的问题需要先说明清楚&#xff1a; Mellanox 网卡是什么&#xff1f; 我现在编译的这些软件是干什么用的&#xff1f; 如…

作者头像 李华
网站建设 2026/4/17 23:26:55

PyTorch U-Net ResNet-50 图像分割终极指南：从入门到精通

PyTorch U-Net ResNet-50 图像分割终极指南&#xff1a;从入门到精通 【免费下载链接】pytorch-unet-resnet-50-encoder 项目地址: https://gitcode.com/gh_mirrors/py/pytorch-unet-resnet-50-encoder 想要快速实现高质量的图像分割效果吗&#xff1f;基于预训练ResNe…

作者头像 李华
网站建设 2026/5/1 8:04:05

英语词汇库终极指南：快速构建强大语言应用的完整解决方案

英语词汇库终极指南&#xff1a;快速构建强大语言应用的完整解决方案 【免费下载链接】english-words :memo: A text file containing 479k English words for all your dictionary/word-based projects e.g: auto-completion / autosuggestion 项目地址: https://gitcode.co…

作者头像 李华
网站建设 2026/4/30 3:42:36

FIFA 23 Live Editor完全指南：从零开始掌握游戏修改艺术

FIFA 23 Live Editor完全指南&#xff1a;从零开始掌握游戏修改艺术 【免费下载链接】FIFA-23-Live-Editor FIFA 23 Live Editor 项目地址: https://gitcode.com/gh_mirrors/fi/FIFA-23-Live-Editor FIFA 23 Live Editor是一款革命性的游戏修改工具&#xff0c;专为希望…

作者头像 李华
网站建设 2026/4/18 10:53:19

WebGL魔兽争霸3与星际争霸2模型查看器完全指南

WebGL魔兽争霸3与星际争霸2模型查看器完全指南 【免费下载链接】mdx-m3-viewer A WebGL viewer for MDX and M3 files used by the games Warcraft 3 and Starcraft 2 respectively. 项目地址: https://gitcode.com/gh_mirrors/md/mdx-m3-viewer 还在为查看魔兽争霸3的M…

作者头像 李华
网站建设 2026/5/1 7:05:06

告别混乱，新手必选！功能超全的进销存系统源码！

温馨提示&#xff1a;文末有资源获取方式进销存管理常常陷入一种困境&#xff1a;手工记账易出错、Excel表格难协同、而复杂的专业软件又价格高昂、不易上手。管理的混乱直接导致库存不清、成本失控、决策失准。针对这一痛点&#xff0c;我们带来了一套专为中小企业及管理新手设…

作者头像 李华