分析了解JDK1.8版本的Java集合HashMap的put()方法
程序员文章站
2022-06-07 13:57:44
...
hashMap是java最常用的Key-Value形式的集合。了解其原理和底层代码是很有必要的，今天就记录下对HashMap的.put()方法的研究分析（元素添加方法）；
先说下个人研究分析结果：
- HashMap在实例初始化的时候并没有对存放元素的容器（1.8版本指数组链表红黑树、1.7版本指数组加链表）进行初始化，只是根据传参对相关属性进行了赋值。容器真正的初始化是在调用put()方法的时候实现的。初始化传参解释：initialCapacity 初始化容量和容器初始值有关，如果没有指定传参，则容器初始值默认值DEFAULT_INITIAL_CAPACITY=16，如果传参，则使用大于等于传参值的最小2的次方的，比如传值是5，那么容器初始化值便是2的3次方即8，另外传值大小有限制不能大于MAXIMUM_CAPACITY=1<<30，如果超过当前值则改变initialCapacity的值为MAXIMUM_CAPACITY的值 。loadFactor 加载因子和扩容有关，如果没指定传参，则使用默认值DEFAULT_LOAD_FACTOR=0.75f。
- 通过put()方法发现HashMap元素存放的数据结构是先生成数组，如果发生hash冲突则变成数组挂链表，默认当链表长度大于等于8且数组长度大于63的时候链表转为红黑树。验证了jdk1.8 HashMAp元素存放结构的说法是数组加链表+红黑树的说法。
- put()方法是有返回值的，返回值根据不同情况返回不同值，当添加元素的key在容器中不存在，那么元素返回为空，当添加元素的key在容器中存在则替换容器中的元素，并返回容器中原来的旧值元素
从new HashMap到调用put()方法分析底层源码验证上边结论：
//实例化一个hashmap 在IDEA编辑器通过Ctrl+鼠标左键点击HashMap可以查看源码
HashMap<String,String> s=new HashMap();
//添加两个元素 他们key相同，value不同
Object put = s.put("key键","第一个值" );
Object put1 = s.put("key键","第二个值");
System.out.println(put);
System.out.println(put1);
//输出结果put=null put1的key和value分别为"key键","第一个值"分析HashMap构造函数相关源码：
//有参构造，分别传入初始化容量值和加载因子*******1
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;
this.threshold = tableSizeFor(initialCapacity);//根据传入的常量值设置容器初始大小
}
//有参构造传入初始化容量***********2
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//内部调用了1构造，加载因子使用了默认值
}
//空参构造***********3 所有值默认
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//有参构造传入另外一个map集合（暂不过多分析当前构造函数，其原理是一样的）
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//加载因子使用默认值，初始化容量值(m.size()/loadFactor)+1.0f
putMapEntries(m, false);//把另外一个map集合元素全部放到当前map
}
通过上边源码我们可以发现在hashMap实例初始化的时候并没有初始化容器的大小，只是对相关属性进行了赋值。而且我们传入的初始化容量值并没有直接赋值给 初始化容量相关属性threshold，而是调用一个叫tableSizeFor(int cap)的方法传入initialCapacity值进行处理之后返回一个值给threshold.查看该方法源码 我们就会发现其内部通过多次位移和按位或运算获得了大于等于传参initialCapacity的最小2的次方的值。
tableSizeFor(int cap)源码如下：
/**
* Returns a power of two size for the given target capacity（这是一个令人佩服的获取最小大于等于传参二次方数的算法）.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;//这里先减1是为了防止cap本身就是2的次方数，比如cap是4,那么进行下列位移运会得到错误的值8.这是不对的。因为4本身就是2的次方数
n |= n >>> 1;//这段代码的意思是无符号向右位移一位然后再和原来再进行按位或操作得到新的n值。举例：假如原来n是3 在计算机二进制表示是0000 0011，向右移一位则变成0000 0001，这是两者按位或结果是0000 0011，换算成十进制便是3
n |= n >>> 2;//下方同理
n |= n >>> 4;//下方同理
n |= n >>> 8;//下方同理
n |= n >>> 16;//下方同理
//利用三元运算符判断 当得到的n小于0则返回1 大于最大默认值，则返回最大值，否者返回n+1(就是最小大于等于cap的二次方数 也就是你初始化传的initialCapacity的值的最小大于等于的二次方数)
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}分析put()方法的源码：
点击进去put（）方法的源码我们会发现其内部只调用putVal()方法和hash(key)方法，并发putVal()方法的返回值返回。二 hash(key)顾名思义仅仅对key做了hash操作，也就是说真正实现添加元素的方法其实是putVal（）方法。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}所以我们简单分析下hash(key)方法 重点分析putVal()方法
//当key为null 返回0 key如果不为空 那么key的hash方法返回的值便是 key的真正的hashcode按位异或（key的哈希值右移16位之后的值）这样做的好处就是 会让得到的下标更加散列 有助于减少hash冲突
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//这里把table赋值给tab并判断是否为空，tab如果不为空，把tab的长度赋值给n,并判断.这里table指代容器.这里的目的是看是不是第一次调用put方法，如果是则调用调整容器大小的方法resize（）完成容器的初始化(此时容器想当于是一维数组)并获取容器内元素长度赋值给n,resize()方法后边介绍。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//获取当前tab数组的最大下标与当前传入元素hash(key)进行按位与操作判断tab第i为是否存在元素（ 通过(n - 1) & hash进行与运算得到的就是新元素应该存放的位置），如果该位置没有元素则new一个节点传入当前元素，否则下一步
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断p元素也就是tab[i = (n - 1) & hash]元素的Hash值和当前插入元素hash值以及两者key是否一致，若一致则把p的值赋值给e 用于后期元素替换（解决key一样但是value不一样的情况）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//用于处理已经生成红黑树的情况
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果p元素也就是tab[i = (n - 1) & hash]元素的Hash值和当前插入元素hash值以及两者key不一致，则生成链表形式。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//p元素的下一个元素赋值给e,并判断是否为空
p.next = newNode(hash, key, value, null);//如果空则直接把把当前插入元素插入节点即可
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//这里是判断如果循环查找次数大于转红黑树阈值（8）开始尝试把链表转成红黑树（这个时候只是尝试，进入treeifyBin方法还要再判断数组长度是否超过64才会真正的转）
treeifyBin(tab, hash);
break;//跳出
}
//这里是判断如果p.next不等于空时候e也就是p.next的hash值和当前插入元素hash值以及两者key是否一致，若一致，则跳出当前循环，后续处理e
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;//跳出
p = e;//把p指向p的下一个节点
}
}
//这里便是用于当容器中存在key和待插入元素key hash值和值一样的时候的处理方式
if (e != null) { // existing mapping for key
V oldValue = e.value;//把容器中旧值复制给oldValue
if (!onlyIfAbsent || oldValue == null)//onlyIfAbsent是个标志 默认是false,一般不做变动
e.value = value;//把当前元素值赋值给e.value
afterNodeAccess(e);//这段代码没看懂 在这里好像没有意义。方法体内是空的
return oldValue; //put方法完成 返回旧值
}
}
++modCount;//相当于版本校验 用于快速失败 集合类元素一般都有这个校验
if (++size > threshold)//用于扩容 当当前容器内元素数量大于初始容量值threshold
resize();//调用调整大小方法容器大小
afterNodeInsertion(evict);//这段代码没看懂 在这里好像没有意义。方法体内是空的
return null;//新key时候返回的值
}