导言
- HashMap 的源码分析，是面试中经常问到的地方，这也是写这篇博文的重要原因之一。
- 源码中有很多基础知识，是平时用不到的，比如位运算法，所以这里第一节就是先了解和学习一下位运算符。
一、基础铺垫
导言中也说了，基础知识有位运算法，位运算符的基础知识又与原码、反码、补码紧密相关，所以首当其冲的也要了解一下原码、反码、补码的基础知识。网上有比较好的资料，我也就不总结了，直接贴上他们的链接了
1. 文档学习
这几篇博文质量都很高，值得细细观看～
2. 总结知识点
1. Java基础之位运算法
位运算 就是直接对整数在内存中的二进制位进行操作，针对与int类型进行操作
Java中常用的位运算符有以下7种：
| & | | | ^ | ~ | << | >> | >>> |
|---|---|---|---|---|---|---|
| 按位与 | 按位或 | 按位异或 | 取反 | 左移 | 带符号右移 | 无符号右移 |
左移（ << ）整体左移，右边空出位补零，左边位舍弃 （-4 << 1 = -8）右移（ >> ）整体右移，左边空出位补零或补1（负数补1，正数补0），右边位舍弃 （-4 >> 1 = -2）无符号右移（ >>> ）同>>,但不管正数还是负数都左边位都补0 （-4 >>> 1 = 2147483646）与（ & ）每一位进行比较，两位都为1，结果为1，否则为0（-4 & 1 = 0）或（ | ）每一位进行比较，两位有一位是1，结果就是1（-4 | 1 = -3）非（ ~ ）每一位进行比较，按位取反（符号位也要取反）（~ -4 = 3）异或（ ^ ）每一位进行比较，相同为0，不同为1（^ -4 = -3）
3. 运算法-细节
- 位运算是针对整数的二进制进行的位移操作
- 整数 32位 , 正数符号为0，负数符号为1。十进制转二进制 不足32位的，最高位补符号位，其余补零
- 在Java中，整数的二进制是以补码的形式存在的
- 位运算计算完，还是补码的形式，要转成原码，再得出十进制值
- 正数：原码=反码=补码 负数：反码=原码忽略符号位取反, 补码=反码+1
例如：十进制4 转二进制在计算机中表示为（补码） 00000000 00000000 00000000 00000100
例如：十进制-4 转二进制在计算机中表示为（补码） 11111111 11111111 11111111 11111100
负数转二进制过程（以-4为例）
1、原码：10000000 00000000 00000000 00000100（转二进制，最高位为符号位）
2、反码：11111111 11111111 11111111 11111011（符号位不变，其余取反）
3、补码：11111111 11111111 11111111 11111100（反码+1）
-4 << 1 计算过程
1、-4 补码 11111111 11111111 11111111 11111100
2、左移一位 11111111 11111111 11111111 11111000 （这时候还是补码）
# 如果最高位符号位为0，就不需要继续操作了，因为正数的补码=原码，如果最高位是1，继续往下走
3、转成反码 11111111 11111111 11111111 11110111 （补码-1）
4、转成原码 10000000 00000000 00000000 00001000 （忽略符号位取反）
5、转十进制 -8
二、HashMap 源码分析
1. jdk对应
jdk7版本是：数组+链表
jdk8版本是：数组+链表 or 数组+红黑树
HashMap 的 源码主要分析和学习有下面几个点
- 常量（6个）
- 构造函数（4个）
- put() 函数
- get() 函数
- 扩容机制
- 其他知识点
- 哈希函数
- 哈希冲突
- 红黑树
2. jdk8 HashMap 中常量解析
// 默认的容量大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大的容量 为2 的 30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的加载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 与JDK7区别：jdk8专有，红黑树。 链表的阈值大雨8的时候，转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 与JDK7区别：jdk8专有，红黑树。 链表还原阈值，HashMap扩容时，会重新计算m，红黑树中的数量小于6时，红黑树转化为 链表 的结构
static final int UNTREEIFY_THRESHOLD = 6;
// 与JDK7区别：jdk8专有，红黑树。当哈希表中的容量大于64时，允许链表转化为红黑色。
// 存储箱可以树化的最小表容量。（否则，如果bin中的节点太多，则会调整表的大小。）应至少为4*TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;
3. jdk8 HashMap 构造函数解析
按源码顺序 拿过来的代码
a、HashMap(int initialCapacity, float loadFactor)
可以自定义初始容量和加载因子
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;
// 与JDK7区别：与JDK7功能一致，JDK7名为，jdk8换了一个名称。将当前桶的大小变为2的幂。
this.threshold = tableSizeFor(initialCapacity);
}
// 返回给定目标容量的二次方大小。
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;
}
b、HashMap(int initialCapacity)
仅自定义初始化容量大小，使用默认的加载因子，还是调用的上一节的有参构造函数
public HashMap(int initialCapacity){
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
c、HashMap()
无参构造函数
默认的加载因子0.75，默认的容量176
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
d、HashMap(Map<? extends K, ? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
4. jdk8 HashMap put方法 解析
a、put(K key, V value)
public V put(K key, V value) {
// 四个参数，第一个hash()值，第四个参数表示如果该key存在值，
// 如果为null的话，则插入新的value，最后一个参数，在hashMap中没有用，可以不用管，使用默认的即可
return putVal(hash(key), key, value, false, true);
}
b、hash(Object key)
// hash():哈希函数，根据key值通过hash()函数计算出哈希值，找到对应的table当中的位置。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
c、putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab 哈希数组， p: 该哈希桶的首节点， n: hashmap 的长度， i:计算出的数组下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 先判断，然后获取长度 并 进行扩容，使用的是懒加载，table 一开始是没有加载的，等put后才开始加载
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
计算插入存储的数组索引i：根据键值key计算的hash值得到 i
此处的数组下标方式 i=(n - 1) & hash, 同JDK 1.7 中的 indexFor()一致，JDK8变成了一句话
插入时，需判断是否存在Hash冲突：
若不存在（即当前tab[i]==null）,则直接在该数组位置新建节点，插入完毕
**/
if ((p = tab[i = (n - 1) & hash]) == null)
// 插入新节点
tab[i] = newNode(hash, key, value, null);
// 否则，代表存在Hash冲突，即当前存储位置已存在节点，则依次往下判断：
else {
// e: 临时节点的作用， k 存放该当前节点的key
Node<K,V> e; K k;
// 第一种：当前位置的key是否与需插入的key相同，若相同 则 直接用 新value 覆盖 旧value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 第二种：判断需插入的数据结构是否为 红黑树 or 链表发生哈希冲突的几种情况
else if (p instanceof TreeNode)
/**
如果是红黑树的节点，向红黑树插入 or 更新数据（键值对）
过程：遍历红黑树 判断该节点的key 是否与需插入的key相同：
a、若相同，则新value 覆盖 旧value
b、若不相同，则插入
**/
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 第三种：hash值 不等于首节点，不为红黑树的节点，则为链表的节点
else {
// 遍历该链表
for (int binCount = 0; ; ++binCount) {
// 如果找到尾部，则表明添加的 key-value 没有重复，在尾部进行添加
if ((e = p.next) == null) {
// 与JDK7区别，JDK8是在链表尾部添加，JDK7在头部添加
p.next = newNode(hash, key, value, null);
// 判断是否要转换为红黑树结构 TREEIFY_THRESHOLD值为8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果 链表中有重复的 key ,e 则为当前重复的节点，结束循环
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;
afterNodeAccess(e);
return oldValue;
}
}
// 到了此步骤，则表明待插入的key-value 是没有key 的重复，因为插入成功e节点的值为null
// 修改次数 +1
++modCount;
// 实际长度 +1，判断是否大于临界值，大于则扩容
if (++size > threshold)
resize();
// 调用 LinkedHashMap的实现方法，其实什么也没做，因为这里 evict=true
afterNodeInsertion(evict);
// 添加成功
return null;
}
d、resize() 扩容
e、putTreeVal(this, tab, hash, key, value) 插入到红黑树
f、treeifyBin(tab, hash);链表转红黑树
5. jdk8 HashMap get方法 解析
a、get(Object key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
b、getNode(int hash, Object key)
final Node<K,V> getNode(int hash, Object key) {
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) {
// 判断第一个key是否为想要查询的key，如果是则返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 判断如果第一个节点的next节点不为null
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;
}
c、getTreeNode(hash, key) 红黑树查询
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
d、find(int h, Object k, Class<?> kc)红黑树查询节点
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
