JDK1.8HashMap源码学习笔记

• • 一、HashMap核心属性分析（threshold，loadFactory，size，modCount）
  • 二、构造方法分析
  • 三、HashMap put方法分析=>putVal方法分析
  • 四、HashMap resize扩容方法分析（核心）
  • 五、HashMap get方法分析
  • 六、HashMap remove方法分析
  • 七、HashMap replace方法分析
  • 八、其他
  • • 为什么数组容量是二的次方（扩容为什么是扩两倍）？
    • 为什么负载因子默认是0.75？

一、HashMap核心属性分析（threshold，loadFactory，size，modCount）

//默认的数组大小 必须是2的次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //1左移4位
//table数组最大长度默认值
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树化阈值 链表长度超过8后 升级为树
static final int TREEIFY_THRESHOLD = 8;
//树降级为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//树化的另一个参数 Hash表中的元素达到64后 才可以升级为树
static final int MIN_TREEIFY_CAPACITY = 64;
//hash表，
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
//当前hash表中的元素个数
transient int size;
//当前hash表结构修改次数 在hash表中插入或删除是结构修改 替换不算是结构修改
transient int modCount;
//扩容阈值 当你的哈希表中的元素超过阈值时 触发扩容
int threshold;
*//负载因子 threshold=capacity（当前表的大小）loadFactor
final float loadFactor;

二、构造方法分析

//initialCapacity是初始化大小 loadFactor负载因子
public HashMap(int initialCapacity, float loadFactor) {

//校验initialCApacity，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); //此处用到tableSizefor方法↓
}

/**

• 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;
  }

//该方法返回一个大于等于cap的最小的二次方数 举个栗子： 假设cap=10 n=9 n= 0b1001| 0b0100 =0b1101
n= 0b1101| 0b0011 =0b1111 n= 0b1111| 0b0000 =0b1111 … n=0b1111=15

return 先判断n是否小于0 如果小于就返回1 如果不小于就进入判断2
判断2：判断n是否大于等于MAXIMUM_CAPACITY(数组最大容量) 如果大于等于就返回MAXIMUM_CAPACITY
如果不大于等于就返回n+1

所以返回15+1=16

该方法实际上就是找到一个最高位的1 然后把这个1后面的位全改为1 最后结果+1 比如10=0b0000 1010 改为0b0000
1111即15 然后15+1=16

//套上面的构造方法的娃 负载因子为默认值0.75

public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

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;
putMapEntries(m, false);
}

三、HashMap put方法分析=>putVal方法分析

//内部调用putVal

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
此处调用了hash方法（扰动方法）

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash方法作用：让key的hash值的高16位也参与路由运算 如果key为空 则返回0 不为空 则进行如下运算：
假设h（key的哈希值）=0b 0010 0101 1010 1100 0011 1111 0010 1110 h右移16位=0b 0000
0000 0000 0000 0010 0101 1010 1100 将这两个数进行异或（同0异1）
0b 0010 0101 1010 1100 0011 1111 0010 1110
0b 0000 0000 0000 0000 0010 0101 1010 1100

得0b 0010 0101 1010 1100 0001 1010 1000 0010

为什么要进行扰动？ 路由寻址公式：（数组长度-1）&Node的hashCode值 &：按位与 因为在路由寻址时
需要HashCode与（数组长度-1）进行按位与
如果数组长度很小（高位是0，0与任何数相与都是0）会导致不同的hashCode的高位不同但低位相同而导致的hash冲突
所以需要进行扰动来把高位的特征和低位的特征结合 降低哈希冲突的概率 也就是尽量让每一位的变化都能对最终得到的结果产生影响

/**

• 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 true：如果散列表中已经存在某个key与要插入的key是一样的 那就不插入了
• @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) {
  //tab:引用当前hashMap的散列表
  //p：当前散列表的元素
  //n：散列表数组的长度
  //i：路由寻址的结果
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  //把table赋值给tab 给n赋值 如果tab是空的 就建表
  //为了节约空间 不会在hashmap初始化时就建好表（有可能初始化了也不用） 而是在第一次putVal时建表
  if ((tab = table) == null || (n = tab.length) == 0)
  n = (tab = resize()).length;

//如果tab[i]是空的 则把key，value通过newNode封装后放入tab[i]

if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//e:Node临时元素
//k:表示临时的一个key

Node<K,V> e; K k;

//此时的p是路由寻址到的桶位的元素 即 tab[i]
//如果桶位中的元素与当前要插入的key value一致 就把这个元素赋值给e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断p是为是TreeNode或者其子类实例化的对象 即判断p是否树化
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) {
p.next = newNode(hash, key, value, null);
//如果链表元素超过了8 进行树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果在链表中找到一个与要插入的元素key value一致的元素 那就跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果散列表中存在与要插入的元素key value一致的元素
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

四、HashMap resize扩容方法分析（核心）

final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//oldCap：扩容前的table数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr：扩容前的扩容阈值 触发本次扩容的阈值
int oldThr = threshold;

//newCap扩容后的数组大小 newThr：扩容后的下次触发扩容的阈值
int newCap, newThr = 0;
//oldCap>0：散列表已经初始化过 本次是一次正常扩容
if (oldCap > 0) {
//如果之前的数组长度已经大于最大长度 把阈值设置为最大 然后返回（没法再扩容了）
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//newCap变为oldCap的二倍 newCap小于最大值限制 并且扩容之前的数组长度>=16（16是默认大小）
//这种情况下 扩容后的阈值是扩容前的阈值的二倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//oldCap为0（散列表未初始化）而扩容前的阈值大于0
//何时会出现这种情况？
//调用构造方法时 调用 1.new HashMap(initCap,loadFactor);
2.new HashMap(initCap);
3.new HashMap(map);//且map里有数据
调用这三个时会初始化threshold（详情看前面构造方法的源码）
else if (oldThr > 0) // initial capacity was placed in threshold 初始容量会放在阈值中
newCap = oldThr;

//oldCap为0（散列表未初始化）oldThr也等于0
//调用无参的构造方法时
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

//何时会newThr==0？
1.newCap小于最大值限制 并且扩容之前的数组长度>=16 上面的if中的else if不成立时
2.调用有参的构造方法时 上面的else if成立时 没有给newThr赋值
此时的newThr就根据公式计算 容量容量因子*
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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//oldTab!=null说明扩容之前的table不是空的 有可能有数据
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
//当前Node
Node<K,V> e;
//当前桶位有数据 但不知道是链表还是红黑树
if ((e = oldTab[j]) != null) {
//置空方便JVM GC时回收
oldTab[j] = null;
//第一种情况：如果是单个元素（没有与其他元素发生碰撞）
//直接重新计算新数组中的位置然后放入
if (e.next == null)
//重新路由寻址
newTab[e.hash & (newCap - 1)] = e;
//第二种情况：当前桶位已经树化
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//第三种情况：当前桶位链化
else { // preserve order
//低位链表：存放在扩容前的数组的位置和扩容后数组的位置一致
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;
else
loTail.next = e;
loTail = e;
}
//高位为1
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;
}

五、HashMap get方法分析

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
//tab：当前散列表
//first：桶位中的头元素
//n：table数组长度
//e：临时Node元素
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果路由算法算出的桶位有数据
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//该桶位的数据与要查的数据一样
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//该桶位链化或者树化
if ((e = first.next) != null) {
*//如果是树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//是链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;

六、HashMap remove方法分析

public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}

public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
都是套娃removeNode

/**

• Implements Map.remove and related methods.
• @param hash hash for key
• @param key the key
• @param value the value to match if matchValue, else ignored
• @param matchValue if true only remove if value is equal
• @param movable if false do not move other nodes while removing
• @return the node, or null if none
  */
  //matchValue：如果为true 则需要key和value都匹配才删除
  //movable：如果为false，则在删除时不要移动其他节点
  final Node<K,V> removeNode(int hash, Object key, Object value,
  boolean matchValue, boolean movable) {
  //p：当前Node元素
  //n：散列表数组长度
  //index：寻址结果
  Node<K,V>[] tab; Node<K,V> p; int n, index;
  //如果当前桶位不为空
  if ((tab = table) != null && (n = tab.length) > 0 &&
  (p = tab[index = (n - 1) & hash]) != null) {
  //node：查找到的结果
  //e：当前元素的next元素
  Node<K,V> node = null, e; K k; V v;

//当前桶位的元素就是要查找删除的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//当前桶位的元素链化或树化
else if ((e = p.next) != null) {
//如果树化
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//链化
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
上半部分是查找要删除的元素
/--------------------------------------------------------------------------------------------------------------------------------
下半部分是删除
//node不为空 说明按照key查找到了需要删除的数据
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//第一种情况：node是树节点 进行树节点移除
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//第二种情况：当前桶位的元素刚好是需要删除的元素
else if (node == p)
tab[index] = node.next;
//第三种情况：node在链表里 此时p不一定是头元素 是node的上一个节点
else
p.next = node.next;
++modCount;
–size;
afterNodeRemoval(node);
return node;
}
}
return null;
}

七、HashMap replace方法分析

//通过genode查找 需要key value都匹配才换
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
//通过getNode查找 找到以后替换
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}

八、其他

为什么数组容量是二的次方（扩容为什么是扩两倍）？

是为了减小碰撞几率 hashmap路由寻址公式是（容量-1）&hashcode
容量是二的次方 那么（容量-1）转换成的二进制数的每一位都是1 这样可以减少碰撞几率（因为0与任何数相与结果都是0 导致不同的hashcode寻找到的地址可能相同 也就是碰撞 所以需要减少容量-1的二进制数中的0的个数）

为什么负载因子默认是0.75？

负载因子决定了数据密度 负载因子越大表中的链表 树就更大 发生碰撞的几率就越高 查询和插入需要的时间就增多 负载因子越小 发生碰撞的几率小 查询和插入需要的时间也小 但是会浪费内存空间 负载因子是0.75是平衡时间效率和空间效率之后的结果 在jdk中官方也做出了解释