HashMap 原理源码分析
1.原理概述
首先呢HashMap 是哈希表的数据结构；(数组和链表的组合)；
Map 接口下的实现类 都有 Key=value 的存储特点 ， HashMap也不例外， 它的Key是不可重复的；
上面讲HashSet的时候 已经表明过 HashSet =HashMap<K,null>;
哈希表/散列表的数据结构图：（HashMap底层的存储结构：Node 数组+Node链表+红黑树）
这个红黑树随便画的不准确
这里主要想表达的是链表树化，所以红黑树的颜色随便弄的；；
别抬杠哈 兄弟们！
Node：
//put到Map的元素都会封装成Node元素，去存放到散列表/哈希表 当中；
static class Node<K,V> implements Map.Entry<K,V> {
//hash 存储的是key的哈希值，但是key.hashCode-->f()--->哈希值，是key的hashCode的值再经过哈希算法的得到的 一个哈希值
final int hash;
final K key;
V value;
//next是下一个节点的地址值，形成一个链表；主要原因是hash碰撞(hash碰撞指的是 两个不同的值经过hash计算后得到了 相同的hash值，)然而我们的数组一个位置只能存储一个元素，那就有了这个next，让它形成链表的结构；
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;
}
hash碰撞，会导致Node 链化(每次算出来都要存到数组同一个位置)，有可能会导致链化严重(就是该位置延伸出来的链表很长,比其他数组元素延伸出来的的链表长的太多，)，为了解决这个问题就引入了红黑树，当链表长度达到8 就树化；以提高检索效率；
先概述一下HashMap.put(k,v):
- hashMap.put(“Hello”，“耀华”);
- 获取"Hello".hashCode()的hash值
- 将2获取的hash值经过扰动函数获取一个更加散列的十进制的hash值；(例如获得的是1133)
- 构造出Node对象 hash=1133； Key=“Hello”，value =“耀华”，next=null；
- 拿这个1133通过 路由算法 ，找出4中构造的Node对象应该存放在数组的哪个位置；
- 路由寻址公式: (arr.length - 1) & node.hash; node.hash 指的就是1122；(注意这个arr数组的长度很特殊 一定是2的次方)
例如：假定数组长度是16； node.hash 是1133；
（16-1） & 1133；
0000 0000 1111 & 0100 0110 1101 = 0000 0000 1101 =13 （&运算 在基础语法的位运算有介绍）；
结果就是存在Node数组下标13的位置；
HashMap的扩容机制
为什么要扩容呢？
假如你的数组 长度为16 ；元素存了很多了；
有链表 有红黑树，此时这个hashMap 在get()查找数据的时候 性能就会很差；基本已经O(1)退化成O(n)了；
为了解决这个问题 就需要扩容， 比如扩了一个更大的数组长度是32；扩容一倍之后 原来很长的链表，减了一半，此时查找的效率就提升了一倍；（用空间换效率的思想）
2.核心方法源码
核心属性分析：
核心常量：
//缺省table长度，就是没有给你的数组指定长度 就按这个 1左移4位=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//数组table 最大长度 不能超过这个数 左移30位=1073741824；10亿多
static final int MAXIMUM_CAPACITY = 1 << 30;
//缺省负载因子大小 （负载因子：用于表示哈希表中元素填满的程度） 你不给你的hashMap传这个负载因子的值，就取0.75；
//它是用来计算扩容阈值的；下面会说
//建议 不要自己去设置这个值；
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树化 阈值；就是上面提到的当链表长度达到8就会树化；
static final int TREEIFY_THRESHOLD = 8;
//树 降级称为链表的阈值；当树的存储元素经过删除达到这个阈值的时候就会转换为链表的数据结构
static final int UNTREEIFY_THRESHOLD = 6;
//当你hash表中的所有元素个数达到64的时候，才能让达到8长度的链升级为树；也属于树化的一个阈值
static final int MIN_TREEIFY_CAPACITY = 64;
属性：
//散列表/哈希表维护的结构 Node类型的数组；就是一个散列表；目前是null；
transient Node<K,V>[] table;
//当前哈希表中元素个数
transient int size;
//当前哈希表的结构修改次数；插入或者删除都叫结构修改，你如果是替换覆盖不算；
transient int modCount;
//扩容阈值，当你的哈希表中的元素超过这个阈值时 触发扩容；(扩容的意义上面说过)
int threshold;
//就是负载因子 threshold = Capacity * loadFactor； 扩容阈值=数组长度 *负载因子；
final float loadFactor;
//内部类Node里面的属性 前面已经讲过了
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
}
4个构造方法分析
1.第一个构造器
//int 的数组初始化大小 负载因子大小
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，也不能是一个非数；
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//上面的三个if语句是对你传进来的参数进行一个合法化的校验；
//传进来的值赋值给属性
this.loadFactor = loadFactor;
//这个为什么不直接赋值给属性呢？
//这个比较特殊,table数组的初始化的大小有个要求：必须是2得到次方；就是因为这个方法；
this.threshold = tableSizeFor(initialCapacity);
}
1.1第一个构造器里面调用的 tablleSizeFor(initialCapacity);
//作用就是返回一个大于等于当前值cap 的一个值，并且这个值一定是2的次方数
//就是让你传进来任何的数都转换2的次方数
//0001 0100 1100 =》 0001 1111 1111 +1 =》0010 0000 000 一定是2的次方
//假设 cap=10；
//经过测试传入最小的0 ，返回为1
static final int tableSizeFor(int cap) {
//n=9 这里你不减一，有可能会得到你想要的值大了一倍 比如传入16 return32；
int n = cap - 1;
//1001 | 0100 = 1101 （不会二进制的位运算 看我上面的java入门基础语法里面的位运算）
n |= n >>> 1;
//1101 | 0011 =1111
n |= n >>> 2;
//1111 | 0000=1111
n |= n >>> 4;
//1111 | 0000=1111
n |= n >>> 8;
//1111 | 0000 =1111 =15
n |= n >>> 16;
// n=15 return n+1=16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
2.第二个构造器
//初始化数组大小
public HashMap(int initialCapacity) {
//就是套娃还是调用的第一个的，
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3.第三个构造器
//我们经常用的
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
4.第四个构造器
//根据一个Map 构建一个HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
HashMap.put()分析
1. put()方法
//传入你的key value
public V put(K key, V value) {
//调用putVal();
//int hash =hash(key)
return putVal(hash(key), key, value, false, true);
}
1.1hash()方法
//这里就是上面讲过的通过key.hashCode()方法在进行扰动函数,得到一个哈希值；
//作用让 key.hashCode()值的高16位也参与路由寻址；(具体原因不是很清楚：大概就是能猜到是拿这个hash值去进行路由寻址的时候 为了减少hash碰撞)
static final int hash(Object key) {
int h;
//注意key 等于null 的时候返回的是个0；也就说当你存放的数据key=null的时候；就存放在数组index0的位置；因为任何数& 0结果都是0； (补充：0 &任何数 结果都是任何数)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.2putVal()方法
//onlyIfAbsent 这个是如果你散列表里面已经有一个key和我现在要存入的key是一致的情况下，就不插了；但是我们我们固定传入的false 就成为了有就替换 ，没有就插入新的
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; //tab 散列表table 的引用
Node<K,V> p; //p 表示当前散列表的元素 （组成散列表的最基本元素就是Node）
int n, i; //n表示数组的长度，i表示路由寻址的结果，该元素要存在tab的哪个下标
// 在这里进行了赋值tab=table n=tab.length；
if ((tab = table) == null || (n = tab.length) == 0){
//延迟了初始化逻辑，第一次调用put()方法时会初始化HashMap对象中最耗费内存的散列表
//resize() 后面会讲；孔融方法
n = (tab = resize()).length;
}
//第一种情况:就是路由寻址，然后看tab[i]==null 是null就是该下标没数据；
if ((p = tab[i = (n - 1) & hash]) == null){
//没数据就把 要插入key 和value 封装为一个Node 放进去；
tab[i] = newNode(hash, key, value, null);
}else {
//不是null，该下标已经有元素了；
Node<K,V> e; // Node 的 临时元素
K k;//key的临时元素
// 第二种情况:判断是你要插入的元素的key与桶位中元素的key完全一致,后续会进行替换/覆盖操作
if (p.hash == hash &&
//p.key ==你要插入的key内存是否相等 //你插入的key不是null //key和k的值相等
((k = p.key) == key || (key != null && key.equals(k)))){
//把p赋值给e ；此时的e就代表我在数组中找到了一个与我要插入的key-value的key一致的元素
e = p;
//第三种情况：桶位的元素的的结构已经树化了；
}else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//最后的情况 是链表了；而且链表的头元素与我们要插入的key不一致；
else {
//迭代这个链表
for (int binCount = 0; ; ++binCount) {
//等于null的话，已经遍历到最后一个Node，整个链表都没有与我key一致的；
if ((e = p.next) == null) {
//那就把key，value 封装到Node里插入最后一个位置
p.next = newNode(hash, key, value, null);
//插完之后的这个判断，意思现在这个链表的元素hi不是到大于了树化的阈值8
if (binCount >= TREEIFY_THRESHOLD - 1)
//树化操作 树这次先不管等我哪天看树再说
treeifyBin(tab, hash);
break;
}
//条件成立的话，在这个链表中找到了与我key完全一致的元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
//这里的e是 p的下一个元素；
p = e;
}
}
//上面的代码有两种情况 e !=null;头元素与key一致，在链表中找到了与key一致的元素
if (e != null) {
V oldValue = e.value;
// 恒成立的判断
if (!onlyIfAbsent || oldValue == null){
//所以这一步肯定会走
//我们插入的value 覆盖了原来的value
e.value = value;
}
afterNodeAccess(e);
//替换的情况下把被覆盖的value值返回了
return oldValue;
}
}
//走到这里说明上面是新的数据封装插入的，没有在散列表中找到与他key一致的元素；
//散列表的结构被修改的次数，替换Node元素的Value值不算；
++modCount;
//++size 插入了一个元素 size要+1操作； 元素数大于了threshold(扩容阈值)
if (++size > threshold)
//扩容
resize();
afterNodeInsertion(evict);
//插入新元素返回null
return null;
}
resize（）扩容源码分析
//为了解决hash冲突，导致的链化严重而影响了查询效率的问题；扩容会缓解该问题；
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //扩容前的哈希表
//老的hash表不是null 就把长度赋值给OldCap； 是null就把0赋值给oldCap
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldTHr扩容之前的阈值；
int oldThr = threshold;
//newCap 扩容之后的大小 newThr扩容之后的新的阈值
int newCap, newThr = 0;
//1.条件成立说明：hsahMap中的散列表已经初始化过了
if (oldCap > 0) {
//1.1条件成立：说明你的需要扩容的散列表已经 达到这个扩容的最大值了；
if (oldCap >= MAXIMUM_CAPACITY) {
//把这个扩容阈值改为 Integer的最大值，就是不再让你触发扩容方法了
threshold = Integer.MAX_VALUE;
//直接返回了，不给扩了，已经最大了；
return oldTab;
// 1.2 老的长度*2赋值给新的长度 <最大扩容长度(基本是恒成立) && 老的长度 >=16(不一定成立)
}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY){
//同时把新的扩容阈值 赋值为 老的阈值*2；
newThr = oldThr << 1;
}
}
/*2.走到这里：说明hashMap中的散列表是null,但是oldThr>0，有哪几种情况呢？
public HashMap(int initialCapacity, float loadFactor) {}经过测试就算传0 ，oldThr=1；
public HashMap(int initialCapacity) {}
public HashMap(Map<? extends K, ? extends V> m) {}
*/
else if (oldThr > 0){
//初始化的长度 = 老的扩容阈值；
newCap = oldThr;
}
/*3.走到这里，说明hashMap中的散列表是null,但是oldThr=0；
就是用了无参构造器创建的对象；
*/
else {
//新的长度 是默认值16
newCap = DEFAULT_INITIAL_CAPACITY;
//新的阈值 就是 默认加载因子0.75* 默认长度16；=12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/* oldCap <= DEFAULT_INITIAL_CAPACITY
oldCap=0 && oldTher>0;
这两种情况会导致new Thr==0；
*/
if (newThr == 0) {
//新的长度*加载因子 得到一个值；
float ft = (float)newCap * loadFactor;
//新的长度小于最大长度 && ft<最大长度 那么新的阈值赋值为(int)ft，
//否则就是新的长度为Interenge最大范围值(也就意味着不能扩容)
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//下次扩容就按照 新的阈值来算；
threshold = newThr;
//上面的代码 确定出 newCap ； 确定出下次扩容的阈值；
//下面 用你的屁股想 就应该能想到该扩容了或者是第一次创建数组；
@SuppressWarnings({"rawtypes","unchecked"})
//根据你newCap 创建一个 Node类型的数组；
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//赋值给table；
table = newTab;
//该条件成立：说明不是第一次初始化哈希表，说明是老数组扩容，但是不知道老数组的元素是单个数据，还是链表还是红黑树；
if (oldTab != null) {
//老数组的元素一个一个的处理
for (int j = 0; j < oldCap; ++j) {
//临时变量
Node<K,V> e;
/*
这个for循环我们以老数组0下标为例子
*/
//条件成立说明桶位铀元素， 等于null的话，就说明老数组的元素都已经操作完了
if ((e = oldTab[j]) != null) {
//把老数组0下标元素存储的地址引用置空；方便老数组被jvm回收；
oldTab[j] = null;
//1.该条件成立，说明e是单个元素，没有发生过碰撞；
if (e.next == null){
//通过寻址公式 把e赋值给 新的数组里
newTab[e.hash & (newCap - 1)] = e;
}
//2.e数据结构已经树化了；
else if (e instanceof TreeNode){
// 树这次先不管
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
}
//3.e不是树 不是单个元素 那就是链表呗 你用屁股想想是不是；
//好，现在你已经想好了，那么我们来看看链表是怎么处理的； 下面有张图可以观摩看一下；
else {
//这4个临时变量 ，可以看出他要把一条链表拆分成两条链表
//低位链表：存放在扩容之后的数组下标位置，与当前数组的效标位置一致;
//说明低位链表里面的元素新老数组的寻址公式结果一致；
Node<K,V> loHead = null, loTail = null;
//高位链表：存放在扩容之后的数组下标位置=老数组的下标位置+ 老数组的长度；
Node<K,V> hiHead = null, hiTail = null;
//定义了一个 next变量；
Node<K,V> next;
do {
//next代表当前节点的下一个节点
next = e.next;
/*
这个判断条件 (e.hash & oldCap)==0 非常的巧妙 为什么这里是& oldCap,而不是oldCap-1;
我们还拿下面那张图举例子 还拿15= 1111下标的链表；
hase =----> 0 1111
hase =----> 1 1111
oldCap 16= 1 0000
放在低位的元素就是 0 ； 放在高位的元素是16；
妙不妙？？？
*/
//等于零的话 就是放低位的元素
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;
}
//判断条件e不是空
} while ((e = next) != null);
//低位链表有数据
if (loTail != null) {
//把lotail指向下一个的高位节点的地址值置空
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
//把hital指向的下一个的低位节点地址值置空
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容时链表的处理图；
怎么放的呢？
寻址算法：（length-1）& hash；
在length=16的时候；
15= 1111 & hash=未知 =15； 但是可以确定的是 ：hash 的后四位肯定也是1111 但是第五位 可能是0(0 1111) 可能是1(1 1111);
在length=32的时候；
31=1 1111 & hash =未知 = 那只能的出两个 结果 就是 1 11111=31和 0 1111=15；
就是这么放的 0 1111的 就放到了 新数组的15小标； 1 1111 就放到了 31的下标位置；
get()方法源码分析;
public V get(Object key) {
Node<K,V> e;
//和新方法是getNode()返回元素 ，元素不为空return元素.value
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//hash();这个方法前面讲过的：获取一个更加散列的hash值；
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; //tab就是当前的散列表
Node<K,V> first, e;//first桶位中的头元素， e是一个临时元素
int n; //table 数组长度
K k;
//判断了这散列表是不是空； 然后通过路由寻址公式找到头元素赋值给first；
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断头元素 是不是就是我们要找的元素
if (first.hash == hash &&((k = first.key) == key || (key != null && key.equals(k))))
return first;
//条件成立说明 first不是单个的数据,要么是链表，要么是树；
if ((e = first.next) != null) {
//条件成立的话 说明first是树结构
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//最后它只能是一个链表了 ，你用屁股想想 是不是？
do {
//遍历链表找到表中key与我们要获取的key完全一致的这个元素；
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//没找到呗
return null;
}
remove()方法源码分析
//这两个方法都是套娃 都是调用了removeNode()方法；
第一个remove方法
//两个参数这个 必须要key 和 value都相同才删除；
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
第二个remove方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//matchValue 这个参数true：key和Value都要比较相同才删除，fasle：只用比较key
//key的hash值 //key //null //fasle //true
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; //当前的散列表
Node<K,V> p; //p是的Node节点的变量；
int n, index;//n数组的长度 index是路由寻址公式结果
//条件成立说明桶位是有数据的，需要查找操作，并且删除
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//node 表示查到的结果
//e表示当前节点的下一个节点
Node<K,V> node = null, e;
K k;
V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//根据判断 头节点就是 要找的元素；将他赋值个node
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
node = e;
break;
}
//如果找到的话 p就是node的上一个元素
p = e;
} while ((e = e.next) != null);
}
}
//上面都是再找这个node
//下面就是删除操作了
//判断node不为空的话，说明按照key查找到了需要删除的数据了；
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v))))
{
//这个节点是树上的节点 那么要走树结构的删除逻辑
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//node==p 说明这个 头节点就是我要删除的元素的时候，node ==p；
else if (node == p)
//让头节点的下一个元素 当头节点
tab[index] = node.next;
else
//让上一个节点指向 被删除元素的下一个阶段；被删除的元素被置空；
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//node==p 说明这个 头节点就是我要删除的元素的时候，node ==p；
else if (node == p)
//让头节点的下一个元素 当头节点
tab[index] = node.next;
else
//让上一个节点指向 被删除元素的下一个阶段；被删除的元素被置空；
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}