java集合HashMap源码解析(基于JDK1。8)
一、Hashmap简介
类继承关系图如下:
HashMap实现了三个接口,一个抽象类。主要的方法都在Map接口中,AbstractMap抽象类实现了Map方法中的公共方法,例如:size(),containsKey(),clear()等,主要方法由子类自己实现。
HashMap结构如下图:
HashMap的主要结构由数组、链表/红黑树组成,当数组中某个节点大于等于8个并且数组长度大于等于64时,链表会转换为红黑树。 二、HashMap的主要属性public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L; /* ---------------- 默认值 -------------- */ /** * 默认初始化大小,必须是二的次幂 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 数组最大值,当大于该值时使用该值 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认负载因子 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 某个节点由链表转为红黑树时候的阈值 */ static final int TREEIFY_THRESHOLD = 8; /** * 节点由红黑树转为链表时的阈值 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 节点转为红黑树时数组的阈值 */ static final int MIN_TREEIFY_CAPACITY = 64; /* ---------------- 字段 -------------- */ /** * HashMap的数组(划重点,主要结构) * HashMap的由数组+链表/红黑树组成,数组指的就是这个数组,链表和红黑树则是由Node结构组成 */ transient Node[] table; /** * 保存缓存的set.AbstractMap字段用于实现keySet()和values()。 */ transient Set> entrySet; /** * HashMap中数据量大小. */ transient int size; /** * HashMap的修改次数 */ transient int modCount; /** * 阈值,当HashMap中数据大于该值时将进行扩容 */ int threshold; /** * 加载因子 */ final float loadFactor; /* ---------------- Node结构 -------------- */ /** * HashMap的基础节点 */ static class Node implements Map.Entry { //当前节点的hash值 final int hash; //当前节点的key final K key; //当前节点的value V value; //指向下一个节点的引用 Node next; //node的构造函数 Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } //...其他方法省略 } 复制代码三、源码解析1、初始化方法
HashMap共有四个构造函数,参数分别是1、初始化数组大小、加载因子。2、初始化数组大小。3、无参。4、HashMap结构。
其中1、2、3三个参数的构造函数性质相同,都是传入初始化数组大小或加载因子,没传的使用默认值。构造函数4使用默认的初始化大小和加载因子,并且是将传入的HashMap添加到新的结构中。
具体代码如下:/** * 有初始化大小和加载因子大小的构造函数 * @param initialCapacity 初始化大小 * @param loadFactor 加载因子 * @throws IllegalArgumentException 非法参数异常 */ public HashMap(int initialCapacity, float loadFactor) { //如果初始化大小小于0,抛出异常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //如果初始化大小大于最大值,那么就把初始化大小设置为最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //如果加载因子小于等于0或者是非法的float类型,则抛出异常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //设置加载因子 this.loadFactor = loadFactor; //设置下一次扩容阈值 this.threshold = tableSizeFor(initialCapacity); } /** * 有初始化大小的构造函数 加载因子使用默认值(0.75) * * @param 初始化大小 * @throws IllegalArgumentException 非法参数异常 */ public HashMap(int initialCapacity) { //调用第一个构造函数,加载因子使用默认值DEFAULT_LOAD_FACTOR(0.75) this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 无参构造函数,使用默认大小(16)和默认加载因子(0.75) */ public HashMap() { //设计加载因子为默认值,其他所有值都是要默认值 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 使用一个HashMap为参数的构造函数,加载因子使用默认(0.75) * * @param 一个HashMap数据 * @throws NullPointerException 空指针异常 */ public HashMap(Map<? extends K, ? extends V> m) { //加载因子为默认值 this.loadFactor = DEFAULT_LOAD_FACTOR; //将传入的HashMap数据放入当前结构中 putMapEntries(m, false); } 复制代码2、get方法
先看源码,再做总结,源码:/** * HashMap的get方法 * @param 要查找的key */ public V get(Object key) { //定义一个node Node e; //通过getNode()方法获取node,getNode返回null则get方法返回null,否则返回node的value return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * 实现Map.get和相关方法 * @param key的hash值 * @param key * @return 结构中的node或者null */ final Node getNode(int hash, Object key) { //定义说明 tab:数组,first:该数组节点中的第一个值,n:数组大小,k:first的key Node[] tab; Node first, e; int n; K k; //如果数组不为null、数组大小大于0、通过hash获取到的数组中的节点不为null if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //该节点的hash等于要查找的hash值(始终检查第一个节点)、该节点的key与要查找的key相等(==为true或者equals为true) if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //如果第first节点不为null并且first节点不是要查找的节点(上面的if判断,如果是要查找的接口则上一步就返回了) if ((e = first.next) != null) { //如果是红黑树类型 if (first instanceof TreeNode) //遍历红黑树 return ((TreeNode)first).getTreeNode(hash, key); //循环遍历链表 do { //当hash值相同、该节点的key与要查找的key相等(==为true或者equals为true) if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } //如果hash值对应的数组为null,则返回null return null; } 复制代码
get方法总结:根据key的hash值找到数组中对应的位置。判断该位置上的值和要查找的值是否相等(==或者equals),如果是则返回如果不是则判断该节点的下一个节点是否为空,为空则返回null。判断结构是否是红黑树,如果是,遍历树。如果不是树,则遍历链表。如果不符合上面的条件则返回null。3、put方法
先看源码:/** * 添加key-value,如果key已经对应value,则替换,返回之前的值 * * @param key * @param value * @return 返回之前的value */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * 实现Map.put和相关方法 * * @param hash值 * @param key * @param value * @param onlyIfAbsent 是否只在不存在的时候修改值,true不修改,false修改 * @param evict 如果为false,则为创建模式 * @return 返回之前的value,如果没有则为null */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //变量说明tab:当前数组,p:当前节点,n:数组大小,i:要插入的数据在数组中的位置 Node[] tab; Node p; int n, i; //数组为空或者数组大小为0 初始化数组(resize()扩容函数,也包括初始化数组,后面扩容会分析) if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果对应数组中的位置为null,将当前数据构造成Node放入该节点 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; //当hash值相同、该节点的key与要插入的key相等(==为true或者equals为true),则替换该value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果是树结构,插入树节点 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { //遍历链表节点 for (int binCount = 0; ; ++binCount) { //如果没有遍历到与该key相同的数据,则在链表最后添加该数据节点 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果该链表长度大于等于8,则将链表转换为树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果key相同,则跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果存在key对应的数据,替换数据,返回之前的数据 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //LinkedHashMap使用,HashMap中方法体为空 afterNodeAccess(e); return oldValue; } } ++modCount; //如果数组中的值大于阈值,则扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 复制代码
put方法总结:判断HashMap中的数组是否为空或者大小为0,如果是则初始化数组。如果该hash值对应的数组中的位置为空,则将该数据组成的节点直接插入到该位置中。如果数组对应位置数据不为空,判断该位置节点的key与要插入的key是否相等,如果是设置e(局部变量)等于该节点。如果Node结构为树结构,则遍历树结构找到key对应的节点,设置为e。如果Node结构为链表,遍历链表,如果链表中没有找到对应的key,将数据构造成Node节点插入链表最后,如果链表长度大于等于8,则将结构转为树。如果在链表中找到对应的key,则将该节点设置为e.如果e(上面遍历找到的节点)不为null,则设置新的value,返回旧的value.如果e为null,说明是新增,HashMap大小加一,判断是否大于阈值,如果大于,则扩容。4、扩容
先看源码:/** * 初始化或者扩容 * * @return the table */ final Node[] resize() { //旧的数组 Node[] oldTab = table; //旧的数组大小 int oldCap = (oldTab == null) ? 0 : oldTab.length; //旧的阈值 int oldThr = threshold; //新的数组大小和阈值 int newCap, newThr = 0; //如果旧的数组大小大于0(只要初始化过就都会大于0) if (oldCap > 0) { //旧的数组大小已经达到最大,那么设置阈值为最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //如果旧的数组扩大两倍小鱼最大值并且旧的数组大于等于初始化值,那么设置新的阈值为旧的阈值的两倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //如果数组大小为0,阈值大小大于0,则设置新的初始化大小为阈值,否则全部使用默认值 else if (oldThr > 0) // 初始容量设置为阈值 newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果新的阈值等于0,那么设置新的阈值为新的数组大小*加载因子 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"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; //旧的数组不为null,说明不是初始化,需要扩容 if (oldTab != null) { //遍历旧得数组 for (int j = 0; j < oldCap; ++j) { Node e; //如果该位置的节点不为null,那么遍历链表或者树放入新的数组中 if ((e = oldTab[j]) != null) { oldTab[j] = null; //如果只有一个节点,直接放入新数组中对应的位置 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果是树结构,拆分树 else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); //链表结构,拆分链表 else { // 保持之前的顺序 //低位头、尾节点 Node loHead = null, loTail = null; //高位头、尾节点 Node hiHead = null, hiTail = null; Node next; do { next = e.next; //如果hash值&旧的数组大小为0,说明放到新数组后还是之前的位置,否则为(当前位置+旧数组大小)的位置 //遍历第一个节点时,头、尾都设置为该节点,之后的节点添加到该节点之后,并设置尾节点为后添加的节点 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } 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; } 复制代码
扩容方法总结:数组是否已经达到最大值,如果已经最大,设置阈值也为最大值,否则数组大小和阈值都改为之前的两倍。数组是否已经初始化,如果没有则初始化数组和阈值。旧数组不为null,遍历旧数组,将对应位置的链表/树分为成两个链表/数组,一个在原先的位置上,一个在原先的位置+原先数组大小的位置上,将两个链表/树放入新数组的对应位置。
以鲁迅先生的角度感悟这个世界站在鲁迅先生的角度思考问题,我也横竖睡不着!在无数个无法入眠的夜里思考,我终于看懂了这世道人心!这里的人很可怜!这里的人也很可悲!可怜的是他们一直在为犯错的人买单,买到一贫如洗,买
20个醍醐灌顶的处世语录,为生活指点迷津,愿11月份事事顺心1。先脱贫,再脱单。如果想要尝到爱情的甜头,那就得先尝尽脱贫前的苦头。记住一句话当你没有钱时,任何海誓山盟白头到老的爱情诺言,都将荡然无存。2。别担心,别着急,人生不过短短数十年,
写给自己我就这么想像着,这么痴呆着,这么憨坐着,任凭脑中翻云覆海神志模糊。如果三生有幸,我能陪着某个人看花开花谢潮起潮落云卷云舒。并这样静静的守候着,携手着,微笑着步入坟墓。我希望有这么一
女高中生休学旅游两年走遍49个城市长白山吐鲁番武汉黄鹤楼17岁宜昌女高中生琪琪因病休学独自旅行,2年间她兼职存钱旅行。历时600余天,走遍全国49个城市。最近,她将自己的旅行经历以视频日记的方式发到抖音平台,超过7
流浪地球221009由于越南的商务签证已经过期,所以不得不选择去一个对中国护照免签或者落地签的国家,先安顿下来,于是泰国成为了目的地。在曼谷机场办理值机的时候,工作人员要求我们先去移民局解决签证过期问
北雁南飞,又有13只白额雁现身青山湖钱江晚报小时新闻记者黄伟芬文王卫国摄第四批大雁来了。今天(11月2日),王卫国在青山湖国家森林公园拍到了13只白额雁。白额雁是国家二级保护动物,作为冬候鸟,光是今年已经在杭州就被拍
让人反胃的2大景点,中国占了一个,看下你有没有去过?大家出去旅游的时候,都是优先选择那些风景很漂亮,适合拍照的地方,毕竟这样心情也会好很多。但是也有一些人是比较独特的,他们就是不愿意去那些风景好看的地方,反而是要去那些看起来非常恶心
宜昌磨基山森林公园获评湖北省2022年最美城市公园万里奔流长江水,千年屹立磨基山。磨基山对于宜昌市民来说,是刻在骨子里的乡愁记忆。随着城市的快速发展,磨基山森林公园的颜值也在逐年提升,成功获评湖北省2022年最美城市公园。磨基山森
在冷湖,追逐最亮的星夜幕下的冷湖天文观测基地。柴达木循环经济试验区冷湖科技创新产业园区管理委员会供图核心阅读每当夜幕降临,浩瀚戈壁星河灿烂,光学望远镜静静矗立,捕捉宇宙讯息得天独厚的自然条件,让位于青
国内5天4晚的豪华旅游火车,票价近3万,堪比五星级酒店如今的生活节奏越来越快,人们很难有时间欣赏生活中的美,只能在闲暇的时候,用旅行的方式放松心情。火车旅游相比于其他旅行方式而言更加缓慢,可正是这种缓慢的前进方式,能够让人们体会到慢游
机票的种类有哪些?大家只知道购买机票,很少有人知道票务也是分类别的。主要分为散票团队票积分票三种,那就让小编给你简单介绍一下吧!散客票如同标题一样,散客就是你直接在官网或者OTA上面看到就直接买,如