国外的哪个网站可以做跳转,网站建设需要服务器吗,注册公司网上核名流程,贵阳网站开发人员工资前言
List、Set、HashMap作为Java中常用的集合#xff0c;需要深入认识其原理和特性。
本篇博客介绍常见的关于Java中HashMap集合的面试问题#xff0c;结合源码分析题目背后的知识点。
关于List的博客文章如下#xff1a;
Java进阶#xff08;List#xff09;——面试…
前言
List、Set、HashMap作为Java中常用的集合需要深入认识其原理和特性。
本篇博客介绍常见的关于Java中HashMap集合的面试问题结合源码分析题目背后的知识点。
关于List的博客文章如下
Java进阶List——面试时List常见问题解读 结合源码分析
关于的Set的博客文章如下
Java进阶Set——面试时Set常见问题解读 结合源码分析
其他关于HaseMap的文章如下
Java学数据结构3——树Tree B树 红黑树 Java标准库中的集合Set与映射Map 使用多个映射Map的案例Java学数据结构4——散列表Hash table 散列函数 哈希冲突 目录 前言引出HashMap底层结构是什么JDK 1.7和1.8 对比源码Node类 HashMap如何解决Hash碰撞问题HashMap 何时从单链表转换为红黑树当链表节点的数量达到8个时通过treeify转为红黑树 HashMap的扩容机制HashMap的数组何时需要扩容1.首次添加元素2.初始容量163.大于16时双倍扩容总结分析 HashMap设置长度为11那么数组的容量为多少第一个2的幂次方的值 HashMap 何时从红黑树转换为 单链模式split方法和untreeify方法 HashMap 为什么在多线程并发使用过程中容易造成死循环/死锁如何得到一个线程安全的HashMap集合总结 引出 1.jdk1.7 HashMap数组单向链表 2.jdk1.8 HashMap数组链表单向红黑树 3.当链表节点的数量达到8个时通过treeify转为红黑树 4.首次添加元素初始容量16大于16时双倍扩容 5.HashMap设置长度第一个2的幂次方的值 6.红黑树元素的高位或者低位节点个数6时那么就调用untreeify方法来退回链表结构 7.jdk1.7采用的是头插法即新来元素在链表起始的位置而jdk1.8采用尾插法可以有效的避免在多线程操作中产生死循环 8.ConcurrentHashMap高并发线程安全
核心键值对KEY不可重复VALUE可以重复
HashMap底层结构是什么
JDK 1.7和1.8 对比
jdk1.7 HashMap数组单向链表
jdk1.8 HashMap数组链表单向红黑树
源码Node类
源码可以看到HashMap内部定义了静态Node类Node类中成员有 NodeK,V next;同样可以看到HashMap内部定义了静态TreeNode类TreeNode类中成员有 TreeNodeK,V left;
TreeNodeK,V right;可以看出存在红黑树
而TreeNode继承了 LinkedHashMap.Entry点进查看可以看到 Entry也继承了 HashMap.Node。所以TreeNode红黑树是从链表Node中转换过来的 整体图 HashMap如何解决Hash碰撞问题HashMap 何时从单链表转换为红黑树
首先理解什么是hash碰撞问题HashMap存放的元素的KEY需要经过hash计算得到hash值而这个hash值可以理解为就是此元素要存放的位置即数组中的下标但是如果两个不同元素经过hash计算后得到的hash值相同时即两个元素要存放的位置为同一个位置产生冲突这种现象就叫做hash碰撞。要想了解HashMap是如何解决hash碰撞的那我们就需要看看HashMap的put方法的源码中的核心操作 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;//添加第一个元素时会进入这个if结构table为null则第一次初始化这个table数组的长度为16if ((tab table) null || (n tab.length) 0)n (tab resize()).length;//判断添加的元素的KEY经过hash计算得到的下标位置是否为nullif ((p tab[i (n - 1) hash]) null)//如果是null则直接添加元素tab[i] newNode(hash, key, value, null);//不为null的情况else {NodeK,V e; K k;//如果key相同则用新的元素添加到旧元素的位置后续会将就元素返回if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;//判断是否为红黑树节点如果是红黑树节点则添加为红黑树else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);//链表类型else {//通过for循环遍历链表节点for (int binCount 0; ; binCount) {//如果链表节点next节点为空if ((e p.next) null) {//则添加至链表的next节点属性中p.next newNode(hash, key, value, null);//如果链表节点 7 说明链表存在8个已存的元素节点if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//转为红黑树方法treeifyBin(tab, hash);break;}//如果KEY相同匹配其他API 如 putIfAbsent()if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}//存入新值返回旧值if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}....当链表节点的数量达到8个时通过treeify转为红黑树
总结HashMap是通过3层 if 结构来判断数组下标位置是否有元素和下标位置的类型是链表还是红黑树然后通过链表和红黑树来解决hash碰撞的问题当链表节点7时当链表节点的数量达到8个时会通过treeify转为红黑树。
HashMap的扩容机制HashMap的数组何时需要扩容
1.首次添加元素
HashMap在第一次添加元素时会进入第一个if结构来初始化数组的长度 2.初始容量16
//添加第一个元素时会进入这个if结构table为null则第一次初始化这个table数组的长度为16if ((tab table) null || (n tab.length) 0)n (tab resize()).length;3.大于16时双倍扩容
此处resize方法就是扩容方法jdk8中resize方法除了扩容还增加了初始化的功能进入此方法我们可以看一下源码 final NodeK,V[] resize() {NodeK,V[] oldTab table;int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;int newCap, newThr 0;if (oldCap 0) {//如果当前数组的长度最大值2^30时将预值threshold设置为最大值if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}//如果当前数组的长度默认的初始长度16则双倍扩容else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}...调用resize方法的地方 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { ...modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;总结分析
从上面可以看出HashMap在完成put元素存储后会判断size是否了阈值如果是就会去扩容下面这个方法是在put元素为链表节点并且要转为红黑树时会调用该方法该方法会在一开始就判断是否需要扩容 final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();判断扩容的核心就是threshold这个值 从resize方法中看到HashMap在扩容时是之前的双倍扩容
HashMap设置长度为11那么数组的容量为多少
第一个2的幂次方的值
指定了长度初始化HashMap时它会将数组的容量经过一系列算法设置为大于我们自定义值的第一个2的幂次方的值
即 设置为11 则为2^416 static final int tableSizeFor(int cap) {int n cap - 1;n | n 1;n | n 2;n | n 4;n | n 8;n | n 16;return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;}HashMap 何时从红黑树转换为 单链模式 HashMap在resize方法执行时会将元素从旧数组转入新数组此时如果转移元素为红黑树结构那么就会调用split方法来分割红黑树方便转移split方法内部在分割时会生成高位树与低位树两种此时也会进行判断如果红黑树元素的高位或者低位节点个数6时那么就调用untreeify方法来退回链表结构
split方法和untreeify方法 final void split(HashMapK,V map, NodeK,V[] tab, int index, int bit) {... //lowhead 低位树if (loHead ! null) {//在红黑树节点元素往新数组中添加时会调用split方法来重组这个红黑树//此时会判断红黑树的节点操作次数是否6即low树低位树的节点数 6时会通过untreeify方法来退化为链表if (lc UNTREEIFY_THRESHOLD)tab[index] loHead.untreeify(map);else {tab[index] loHead;if (hiHead ! null) // (else is already treeified)loHead.treeify(tab);}}//此时会判断红黑树的节点操作次数是否6即high树高位树的节点数 6时会通过untreeify方法来退化为链表//highhead 高位树 if (hiHead ! null) {if (hc UNTREEIFY_THRESHOLD)tab[index bit] hiHead.untreeify(map);else {tab[index bit] hiHead;if (loHead ! null)hiHead.treeify(tab);}}
}HashMap 为什么在多线程并发使用过程中容易造成死循环/死锁
图示 产生死循环的核心原因是因为jdk1.7采用的是头插法即新来元素在链表起始的位置而jdk1.8采用尾插法可以有效的避免在多线程操作中产生以上死循环但是HashMap不是线程安全的所以在多线程的场景中虽然不会出现死锁/死循环但是还是会出现节点丢失的情况所以在并发的场景中推荐使用ConcurrentHashMap
如何得到一个线程安全的HashMap集合 ConcurrentHashMap concurrentHashMap new ConcurrentHashMap();总结
1.jdk1.7 HashMap数组单向链表 2.jdk1.8 HashMap数组链表单向红黑树 3.当链表节点的数量达到8个时通过treeify转为红黑树 4.首次添加元素初始容量16大于16时双倍扩容 5.HashMap设置长度第一个2的幂次方的值 6.红黑树元素的高位或者低位节点个数6时那么就调用untreeify方法来退回链表结构 7.jdk1.7采用的是头插法即新来元素在链表起始的位置而jdk1.8采用尾插法可以有效的避免在多线程操作中产生死循环 8.ConcurrentHashMap高并发线程安全
