hashmapput方法源码（2、HashMap源码分析）
导读：特别：下文的“容量”、“数组长度”，“capacity” 都是指底层数组长度，即 table.length...
特别：下文的“容量 ” 、“数组长度 ” ，“capacity ” 都是指底层数组长度 ，即 table.length
1 一般数据结构及特点
数组：占用连续内存的数据结构 ，查找容易[O(1)] ，插入困难[O(n)] 链表：由一组指向（单向或者双向）的节点连接的数据结构 ，内存不连续 ，查找困难 ，但插入删除容易 哈希表：插入删除查找都容易的数据结构 数组下标是通过：（Node<K, V>[] 的容量-1）&（hash(key)）的出来的本章要解决的问题：
HashMap的数据结构实现方式 HashMap是怎么做到为get 、put操作提供稳定的时间复杂度的 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树 HashMap初始化时为什么要给自定义的初始容量 。 HashMap如何保证容量始终是2的幂 HashMap为何要保证容量始终是2的幂 HashMap的hash值如何计算 HashMap为什么是线程不安全的2 HashMap基本属性说明
常量部分：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量 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; //链表转转红黑树的数组最小容量 transient int size; //HashMap的元素个数 default_initial_capacity：初始容量=16 maximum_capacity：最大容量=1<<30 。 default_load_factor：负载因子=0.75 。 threshold：下一个触发扩容操作的阈值 ，threshold = capacity * load_factor 。当元素数量(size值)超过阈值时触发扩容 ，新容量是旧容量2倍 。 treeify_threshold：链表转红黑树时链表长度阈值=8 untreeify_threshold： 红黑树转链表阈值=6 ，红黑树节点小于6就会转成链表 。 Node<K, V> implements Map.Entry<K, V> ：HashMap存放数据的基本单位 ，里面存有hash值 、key 、value 、next 。 Node<K, V>[] table：存放Node节点的数组 ，HashMap底层数组 ，数组元素可以为单节点Node 、多节点链表 、多节点红黑树 。 size：成员变量 ，表示当前Map的键值对数量 ，在put 、remove 、clear操作 ，会修改该值 。扩容也是通过阈值跟size进行比较决定3 HashMap 数据结构
HashMap是一个Node类型的数组 ，每个元素可以为单节点 、链表 、红黑树 。
Java8之前 ，HashMap的数据结构如下：
数组+链表
：链表是为了解决hash冲突
Java8 ，HashMap的数据结构如下：
数组+链表+红黑树3.1构造函数
Tips：
确定加载因子 根据初始容量参数重新计算扩容阈值（大于或等于初始容量且一定等于2的幂的那个数）
tableSizeFor(initialCapacity):确定扩容阈值：大于或等于初始容量且一定等于2的幂的那个数；比如cap=8则返回8；cap=9则返回16源码分析如下：
//构造函数一：无参构造函数：加载因子（0.75）和初始容量（16）分别使用默认值 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } //构造函数二： //指定初始容量 ，调用HashMap(int initialCapacity, float loadFactor) public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //构造函数三：同时指定初始容量和加载因子 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;//初始容量不能超过最大容量： if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " +loadFactor); this.loadFactor = loadFactor; // 确定扩容阈值：大于或等于初始容量且一定等于2的幂的那个数；比如cap=8则返回8；cap=9则返回16 this.threshold = tableSizeFor(initialCapacity); } //构造函数三：创建一个跟参数有相同结构的map public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }3.2 Node<k,v>分析
tips：一个简单的K-V模型的数据体 ，提供对key value的set get操作 源码如下：
/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); // key value 的hash值再做异或运算 } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }4 put过程分析
4.1 扩容方法resize()分析
HashMap的容量变化通常存在以下几种情况：
空参数的构造函数：实例化的HashMap默认内部数组是null ，即没有实例化 。第一次调用put方法时 ，则会开始第一次初始化扩容 ，长度为16 。【懒加载】
有参构造函数：用于指定容量 。根据阈值计算方式【大于或等于初始容量且一定等于2的幂的那个数】 ，将这个数设置赋值给阈值 。第一次调用put方法时 ，会将阈值赋值给容量（第一步） ，然后让 阈值=负载因子X容量
（第二步）
。（因此并不是我们手动指定了容量就一定不会触发扩容 ，超过阈值后一样会扩容！！）如果不是第一次扩容 ，则容量变为原来的2倍 ，阈值也变为原来的2倍 。（负载因子还是不变）
首次put时 ，先会触发扩容（底层table初始化） ，然后存入数据 ，然后判断是否需要扩容；不是首次put ，则不再初始化 ，直接存入数据 ，然后再判断是否需要扩容；
参看源码：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//当前数组 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //非首次put ，扩容阈值变为原来2倍；容量变为原来的2倍 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab;//达到最大值 ，不能扩容 ，返回当前数组 } //数组容量扩大为原来2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // 将扩容阈值变为原来2倍 } //第一次 put 的时候 ，【对应使用 new HashMap(int initialCapacity) 初始化后】 else if (oldThr > 0) newCap = oldThr; //如果初始化Map时指定了初始容量 ，则数组容量=扩容阈值（参照阈值的计算） //第一次 put 的时候 ，【对应使用 new HashMap() 初始化后】 else { newCap = DEFAULT_INITIAL_CAPACITY;//没有指定初始容量 ，则数组容量=默认初始容量 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//扩容阈值=加载因子*默认初始容量=12 } //第一次put且有指定初始容量时 ：重新计算扩容阈值：新扩容阈值=加载因子*新数组长度 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //计算好容量初始化一个新的数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //如果第一次put ，这里就直接返回newTab ，扩容过程结束； table = newTab; if (oldTab != null) { // 开始遍历原数组 ，进行数据迁移 。 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null)//数组当前位置不存在链表或者红黑树 ，则直接put到该位置 newTab[e.hash & (newCap - 1)] = e; //返回单节点的Node数组 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; do { next = e.next; 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; }4.2 put方法分析
源码分析：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * @param hash：key的hash值 * @param onlyIfAbsent ：false表示key存在时 ，覆盖value * @param evict if false, the table is in creation mode. 待补充 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) //第一次put ，先执行数组初始化操作 n = (tab = resize()).length; //当前key对应的数组下标没有元素 ，则直接初始化新的Node到该数组位置 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //注意此时Node没有Next else { //当前key对应的数组下标已经存在元素 Node<K,V> e; K k; // 情况一：//该位置的元素跟新put进来的数据key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //注意这里是引用的赋值 ，因此后面e.value=value可以实现value覆盖 //情况二：当前位置是红黑树结构 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //情况三：当前位置是链表结构 for (int binCount = 0; ; ++binCount) { //遍历到达链表末端 if ((e = p.next) == null) { //创建新的Node并放在链表的末端 p.next = newNode(hash, key, value, null); // treeify_threshold 为 8 ，所以 ，如果新插入的值是链表中的第 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; //这里break ，代码后面统一对e进行value的覆盖处理 //此时既未遍历到链表末端 ，也没有发现key相等 ，则继续链表遍历 p = e; //这个赋值 ，相当于链表的遍历 ，尾部指向下一个节点的头部 ，实现链表遍历 } } if (e != null) { // existing mapping for key key相等时 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //新的value覆盖旧的value值 afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) //每次put操作完成后 ，size自增； //如果size超过阈值 ，则在put完成后 ，再次执行扩容 resize(); afterNodeInsertion(evict);//父类抽象方法的实现 ，HashMap不做任何实现 return null; } 第一次put时扩容过程如下： 容量：C 加载因子：F 扩容阈值：T ------ 1 、无参初始化： F=0.75 C=0 T=0 ------ 2 、有参初始化：容量参数=7 F=0.75 C=0 T=tableSizeFor(7)=8 //1 、2 、4 、8 。 。 。大于7 所以取8 ------ 3 、第一次put && 无参初始化时 F=0.75 C=16（默认容量） T=16*0.75=12 ------ 4 、第一次put && 有参初始化时 F=0.75 C=T=8 // 容量=阈值 T=8*0.75=6 // 阈值更新：容量*加载因子5 关于HashMap
5.1 HashMap如何实现put 、get操作时间复杂度为O(1)~O(n)?
首先 ，对于数组的元素 ，如果知道index ，那查找的复杂度就是O(1)级别 对于get操作 ，首先根据key计算出hash值 ，而这个hash值 执行操作hash&(n-1)就是它所在的index ，在最好的情况下 ，该index只有一个节点且hash值与key的hash值相等 ，那么时间的复杂度就是O(1) 。当该节点为链表或者红黑树时 ，时间复杂度会上升 ，但是由于HashMap的优化（链表长度 、红黑树长度相对HashMap容量不会过长 ，过长会触发resize操作） ，所以 最坏的情况也就是O(n) ,可能还会小于这个值 。【链表的查询时间复杂度是：O (n) ，红黑树是 O(logN) ，比O (n)更小】 对于put操作 ，我们知道 ，数组插入元素的成本是高昂的 ，HashMap巧妙的 使用链表和红黑树代替了数组插入元素需要移动后续元素的消耗 ，这样在最好的情况下 ，插入一个元素 ，该index位置恰好没有元素的话 ，时间复杂度就是O(1),当该位置有元素且为链表或者红黑树的情况下 ，时间复杂度会上升 ，但是最坏的情况下也就是O(n) 。5.2 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树？
单节点转链表：当计算出来的index处有元素 ，且元素是单节点时 ，则该节点变为链表； 链表转红黑树有两个条件： 链表长度大于TREEIFY_THRESHOLD ，默认阈值是8； HashMap长度大于645.3 HashMap初始化时为什么要给自定义的初始容量？
不指定初始容量时 ，HashMap底层数组的在第一次put值时 ，数组长度为默认初始长度即16 ，加载因子为0.75 ，扩容阈值为16*0.75=12；当元素数量大于12时 ，底层数组进行扩容 ，长度翻倍为32 ，扩容阈值翻倍为24 ，依次类推； 指定初始容量时 ，假设初始容量为C=1000 。HashMap底层数组的在第一次put值时 ，数组长度初始化为 1024 ，扩容阈值为1024*0.75=768；当元素数量大于768时 ，底层数组进行扩容 ，长度和阈值同时翻倍 。 因此 ，当HashMap元素足够多时 ，不指定初始容量要比指定初始容量进行更多次的扩容 ，扩容涉及数组拷贝 、链表或红黑树重建 ，消耗更多性能 。 根据要使用的HashMap大小确定初始容量 ，这也不是说为了避免扩容初始容量给的越大越好 ， 越大申请的内存就越大 ，如果你没有这么多数据去存 ，又会造成hash值过于离散 ，增加查询或修改的时间复杂度 。5.4 HashMap如何保证容量始终是2的幂？
HashMap使用方法tableSizeFor()来保证无论你给值是什么 ，返回的一定是2的幂
/** * Returns a power of two size for the given target capacity. */ 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; }5.5 HashMap为何要保证容量始终是2的幂
HashMap在定位元素在数组的index时 ，运算公式是 (n-1)&hash ,n为数组的长度 。如果容量始终是2的次幂 ，例如 0000 0000 0000 0000 0000 0000 1000 0000 ，则n-1的二进制形式为：0000 0000 0000 0000 0000 0000 0111 1111 ，低位区一定是1 ，在进行 (n-1)&hash ，hash低位区的0 、1特征能够保留 因此 ，容量始终是2的幂 ，这样 下标index值的取值范围更广 ，减少hash碰撞 。5.6 HashMap计算hash值
1 、带着疑问
：
key的hashCode为什么右移16位后再进行异或运算？2 、关于 | & ^ 三种运算的特征说明：
^按位异或运算：位相同返回0 ，不同返回1；可推导出：任何数跟0异或返回任何数 ，任何数跟1异或返回对应的取反 异或运算能更好的保留各部分的特征 ，如果采用逻辑与&运算计算出来的值会向0靠拢（00得0 ，01得0 ，11得1 因此0的概率2/3） ，采用逻辑或|运算计算出来的值会向1靠拢 (00得0 ，01得1 ，11得1 ，因此1的概率为2/3)3 、hash()源码：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //key.hashCode() ;hashCode是Object对象的一个native方法 ，由操作系统实现 ，跟内存地址存在某种映射关系4 、进入分析：
5.6.1 key的hash值>>>16 ，为什么要这样做呢？
h值右移16后 ，高16位都为0 ，这样h^(h>>>16)时 ，高16位的值不会有任何变化 ，但是低16位的值混杂了key的高16位的值 ，从而增加了hash值的复杂度 ，进一步减少了hash值一样的概率 。 计算数组下标公式：(n-1)&hash ，n-1的结果：高位趋于0；&运算的结果：高16位向0靠拢 ，hash的高位特征丢失 因此 ，如果我们不做hash值的移位和异或运算 ，那么在计算数组index时将丢失高区特征简单点：
因为：(n-1)&hash中 ，hash的高位数将被数组长度的二进制码锁屏蔽 ，为确保hash的高位尽可能利用 ，就先对hash值先右移16位 ，再跟原hash值进行异或运算 ，同时保留高位和低位特征 。
数组长度二进制码屏蔽是什么意思？
数组长度的数据类型int转化为32位的二进制 ，因为长度值对比最大值（2的32位）总是比较小的 ，所以它的高位趋向0 ，与其他数进行&运算后 ，结果值的高位趋向0 ，那么其他数的高位特征就丢失了下面用例子分析：
### 计算hash hashCode： 0000 0000 0101 0000 0000 0000 1111 1010 hashCode>>>16: 0000 0000 0000 0000 0000 0000 0101 0000 hashCode^hashCode>>>16: 0000 0000 0101 0000 0000 0000 0110 1010 hash=hashCode^hashCode>>>16 0000 0000 0101 0000 0000 0000 0110 1010 ### 计算index时： (n-1) (假设n=16) 0000 0000 0000 0000 0000 0000 0000 1111 (n-1)&hash 0000 0000 0000 0000 0000 0000 0000 1010 仔细观察上文不难发现 ，高16位很有可能会被数组长度的二进制码锁屏蔽 ， 如果我们不做移位异或运算 ，那么在计算数组index时将丢失高区特征5.7 HashMap为什么是线程不安全的？
它没有任何的锁或者同步等多线程处理机制 ，无法控制并发下导致的线程冲突 。 如果想要线程安全的使用基于hash表的map ，可以使用ConcurrentHashMap ，该实现get操作是无锁的 ，put操作也是分段锁 ，性能很好6 get 过程分析
计算 key 的 hash 值 ，根据 hash 值找到对应数组下标: hash & (length-1) 判断数组该位置处的元素是否刚好就是我们要找的 ，如果不是 ，走第三步 判断该元素类型是否是 TreeNode ，如果是 ，用红黑树的方法取数据 ，如果不是 ，走第四步 遍历链表 ，直到找到相等(==或equals)的 key参考资料：
[良许-HashMap源码实现分析]：https://www.cnblogs.com/yychuyu/p/13357218.html
声明：本站所有文章 ，如无特殊说明或标注 ，均为本站原创发布 。任何个人或组织 ，在未征得本站同意时 ，禁止复制 、盗用 、采集 、发布本站内容到任何网站 、书籍等各类媒体平台 。如若本站内容侵犯了原著者的合法权益 ，可联系我们进行处理 。
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！