前言
文章仅是笔者个人的学习笔记，存在一些只有笔者个人能看到的用词或者描述，如果有不明确的地方，欢迎留言，理性讨论。
一、概述
- HashMap是Map的一种，它的继承结构如下：
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
...
}
- Map是一种多对多的结构，Java里面的Map是Key-value结构，由于可以使用泛型，所以实际也能做到多对多。
- 所谓Key-Value，在HashMap中的具体存在形式，就是Entry 对象(同时包含了 Key 和 Value)。
- 同时注意，包括Map和List在内的所有容器，它们存的都是引用对象，也就是实际对象的地址数据。
- 以上继承和实现需要注意：
- Cloneable：表明可以实现clone方法
- AbstractMap：基本上Map都会继承它，它完成了Map类型集合的骨干方法
二、基础的哈希知识
-
哈希和拉链法
- 哈希的定义：Hash 就是把任意长度的输入(又叫做预映射， pre-image)，通过哈希算法，变换成固定长度的输出(通常是整型)
- 拉链法：
- 数组的特点是：寻址容易，插入和删除困难；
- 链表的特点是：寻址困难，插入和删除容易
- 结合两者优点，数组+链表+哈希 = 拉链法：
- HashMap使用的就是拉链法，它的底层实现还是数组。
- 数组的每一项都是一条链。
- 其中参数initialCapacity 就代表了该数组的长度，也就是桶的个数。
-
链表与红黑树
- 在jdk1.8之前使用的就是纯拉链法，在jdk1.8开始，链的长度如果>=8，会转换成红黑树。
- 关于红黑树，可以去看 TreeMap 探究 ，TreeMap 实现就是红黑树，里面解析了一些红黑树的知识。
-
哈希位置定位
- 不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。
- 先看源码：
// 代码1
static final int hash(Object key) { // 计算key的hash值
int h;
// 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代码2
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;
- ~~（这部分算法感觉可以单独写一篇来学了，实际原理有点复杂啊~~
- 不行，就是干！冲就完事了，一定要搞懂
- 步骤1：拿到key的hashCode值
- 步骤2：将hashCode的高位参与运算，重新计算hash值
- 这里首先要说一下，求取hash值对应的数组位置（桶位置），在java里面用的是 & 的方法，也就是位运算。没有用 % 的方法，也就是取余，是因为取余的开销是远大于位运算的（相当于要做大数除法，这还是比较好理解的）
- hashCode() 是int类型，取值范围是非常大的（int的最大值-最小值），只要哈希函数映射的比较均匀松散，碰撞几率是很小的。
- 由于存放的数组本身长度是有限的，远小于hashCode() 的数量，且如上文所说，求取桶位置的方法是位运算，这就导致只有 hash 值的低位会参与运算，那么就算 hashCode() 取的很完美，最后得到相同 Index 几率也是会大大增加的。
- 在jdk 1.8 以下，会通过 扰动方法 ，对 hasd值 多次进行右移，以使得低位的数据尽可能不同
- 在jdk 1.8以上，会通过将高位数据与低位数据异或的方式，让hash值高低位都参与运算，从而增加随机性
- 步骤3：将计算出来的hash值与(table.length - 1)进行&运算
- 这里就是上面所说的，为了减少开销，用位运算的方式得到最后的index
三、源码分析
-
构造方法：
- HashMap(int initialCapacity, float loadFactor)：自定义属性的构造方法（默认构造方法其实和它是一样的，只是使用默认值）
//以下是 jdk 1.8 以下的方法！
public HashMap() {
//负载因子:用于衡量的是一个散列表的空间的使用程度，默认0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
//HashMap进行扩容的阈值，它的值等于 HashMap 的容量，默认16，乘以负载因子
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
// HashMap的底层实现仍是数组，只是数组的每一项都是一条链
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
//以下是 jdk1.8的方法！
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);
}
- 可以传入自定义的初始大小和负载因子，不过需要注意：
- jdk 1.8 之前，构造方法中就进行了 数组的初始化，但是 1.8 开始，只是记录初始容量和负载因子的值，到第一次put的时候才会真正去初始化数组，等于是有懒加载的机制
- 初始容量和负载因子对HashMap性能的影响是非常大的，对于 拉链法 的哈希表（jdk 1.7及以下是纯链表），查找一个元素的平均时间是 O(1+a)，a 指的是链的长度，是一个常数。若负载因子越大，那么对空间的利用更充分，但查找效率的也就越低
- 剩余的两个构造方法就不用多说了：
- 一个是自定义初始大小，但是用默认的负载因子
- 一个是传入一个已有的Map集合进行Copy然后初始化
-
扩容：resize() 方法
- 扩容和赋值的时机与顺序问题：
- 第一次Put的时候，会调用一次扩容，这一次其实等于是初始化，所以是先扩容后赋值
- 第二次开始，如果触发扩容，才是真正的扩容，是先完成赋值，后扩容
- 扩容的时候，所有的元素，包括链表/红黑树里面的，都要重新判定index位置！
- 所以这里也会判断是否要将，红黑树–>链表（<=6），或者 链表 --> 红黑树 (>=8)
- 扩容的步骤解析，我们假定数组为 tabel , 其大小是 n ，新数组为 newTabel ：
- 扩容其实就是把数组 tabel 中的元素，分散映射到大小为 n*2 的 newTabel 的过程
- 那么很显然，newTabel 的下标是包含了 tabel 的 (4包括3，8当然也包括3)，所以一部分元素是不用动的，一部分元素要移动
- 那么这里有三个问题需要判断：
- 哪些元素不用移动，哪些元素要移动？
- 移动的偏移量是多少？
- 扩容的方法 resize () ，主要就是解决这几个问题的：
- 判断是否需要移动，就是判断：元素的 hash值 & n == 0，这是因为：
- HashMap 计算 hash值对应下标的方法是 hash值 & (n-1)
- 例如扩容前 n = 4 的时候，n-1=3，对应的二进制为 ：011
- 那么很显然，这时候只有 hash值的最后两位会起作用，前面的高位都被抛弃了
- 而扩容之后 n=8 ，n-1=7，对应的二级制为：0111
- 这时候是 hash 的后三位起作用了，多了一位，
- 如果hash值对应的多出的这一位是 1 ，那么，它对应的 Index 就变了，变成oldIndex + n
- 如果hash值对应的多出的这一位是 0 ，那么，它对应的 index 还是原来的值，不用变。
- 那么如何判断 hash 值的这一位是 0 还是 1 呢？
- 这里也很明显了，tabel 的长度 n 必然是 2的幂次方，所以 n-1 的二进制，必然比n小一位，n 和 2*n-1 的最高位是同样的
- 例如 n =4 , 0100；2*n-1= 7，0111
- 所以，直接用 hash值 & n == 0 ，判断需要移动还是不需要移动，是最快的。
- 处理需要移动的数组元素。
- 其实感觉现在我已经理解透彻了，要是后面又忘了，可以看下面这段解析，很详细了
- 判断是否需要移动，就是判断：元素的 hash值 & n == 0，这是因为：
- 扩容和赋值的时机与顺序问题：
/**
* 测试目的：理解HashMap发生resize扩容的时候对于链表的优化处理：
* 初始化一个长度为8的HashMap，因此threshold为6，所以当添加第7个数据的时候会发生扩容；
* Map的Key为Integer，因为整数型的hash等于自身；
* 由于hashMap是根据hash &（n - 1）来确定key所在的数组下标位置的，因此根据公式 m（m >= 1）* capacity + hash碰撞的数组索引下标index，可以拿到一组发生hash碰撞的数据；
* 例如本例子capacity = 8， index = 7，数据为：15，23，31，39，47，55，63；
* 有兴趣的读者，可以自己动手过后选择一组不同的数据样本进行测试。
* 根据hash &（n - 1）， n = 8 二进制1000 扩容后 n = 16 二进制10000， 当8的时候由后3位决定位置，16由后4位。
*
* n - 1 : 0111 & index resize--> 1111 & index
* 15 : 1111 = 0111 resize--> 1111 = 1111
* 23 : 10111 = 0111 resize--> 10111 = 0111
* 31 : 11111 = 0111 resize--> 11111 = 1111
* 39 : 100111 = 0111 resize--> 100111 = 0111
* 47 : 101111 = 0111 resize--> 101111 = 1111
* 55 : 110111 = 0111 resize--> 110111 = 0111
* 63 : 111111 = 0111 resize--> 111111 = 1111
*
* 按照传统的方式扩容的话那么需要去遍历链表，然后跟put的时候一样对比key，==，equals，最后再放入新的索引位置；
* 但是从上面数据可以发现原先所有的数据都落在了7的位置上，当发生扩容时候只有15，31，47，63需要移动（index发生了变化），其他的不需要移动；
* 那么如何区分哪些需要移动，哪些不需要移动呢？
* 通过key的hash值直接对old capacity进行按位与&操作如果结果等于0，那么不需要移动反之需要进行移动并且移动的位置等于old capacity + 当前index。
*
* hash & old capacity（8）
* n : 1000 & index
* 15 : 1111 = 1000
* 23 : 10111 = 0000
* 31 : 11111 = 1000
* 39 : 100111 = 0000
* 47 : 101111 = 1000
* 55 : 110111 = 0000
* 63 : 111111 = 1000
*
* 从下面截图可以看到通过源码中的处理方式可以拿到两个链表，需要移动的链表15->31->47->63，不需要移动的链表23->39->55；
* 因此扩容的时候只需要把loHead放到原来的下标索引j（本例j=7），hiHead放到oldCap + j（本例为8 + 7 = 15）
*
* @param args
*/
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<>(8);
for (int i = 1; i <= 7; i++) {
int sevenSlot = i * 8 + 7;
map.put(sevenSlot, sevenSlot);
}
}
- 引申：死循环问题：jdk 1.8之前HashMap扩容可能导致死循环。
- 本质是因为HashMap是非线程安全的，同时 1.8 之前扩容之后的链表顺序会和扩容前不同，所以导致多线程操作会有严重问题。
- 这个虽然在1.8解决了，但是 HashMap 本身还是非线程安全的，所以不要在多线程环境下使用
-
查找：
- get(Object key)
- 先看代码：
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) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table不为空 && table长度大于0 && table索引位置(根据hash值计算出)不为空
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; // first的key等于传入的key则返回first对象
if ((e = first.next) != null) { // 向下遍历
if (first instanceof TreeNode) // 判断是否为TreeNode
// 如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode
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; // 找不到符合的返回空
}
- 总的来说，查找的代码是比较清晰的，分以下几步：
- 算出传入的 target 的hash值
- 根据hash值定位到数组的index
- 取出对应的 Index 的数据进行判断
- 如果是第一个 Entry 的 Key 就是 target ，那么等于直接找到了
- 如果第一 Entry 不符合要求，那么要进行判断了
- 如果Entry 的类型是 TreeNode ，也就是红黑树，那么调用红黑树的遍历方法去找
- 如果Entry 的类型不是 TreeNode，那么就是链表了，顺着链条遍历一遍去找即可
- 将找到的数据返回即可，如果找不到数据，那么就返回 null 了
-
增加
- put(K key, V value)
- 同样先看代码：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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是否为空或者length等于0, 如果是则调用resize方法进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通过hash值计算索引位置, 如果table表该索引位置节点为空则新增一个
if ((p = tab[i = (n - 1) & hash]) == null)// 将索引位置的头节点赋值给p
tab[i] = newNode(hash, key, value, null);
else { // table表该索引位置不为空
Node<K,V> e; K k;
if (p.hash == hash && // 判断p节点的hash值和key值是否跟传入的hash值和key值相等
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 如果相等, 则p节点即为要查找的目标节点，赋值给e
// 判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 走到这代表p节点为普通链表节点
for (int binCount = 0; ; ++binCount) { // 遍历此链表, binCount用于统计节点数
if ((e = p.next) == null) { // p.next为空代表不存在目标节点则新增一个节点插入链表尾部
p.next = newNode(hash, key, value, null);
// 计算节点是否超过8个, 减一是因为循环是从p节点的下一个节点开始的
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);// 如果超过8个，调用treeifyBin方法将该链表转换为红黑树
break;
}
if (e.hash == hash && // e节点的hash值和key值都与传入的相等, 则e即为目标节点,跳出循环
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 将p指向下一个节点
}
}
// e不为空则代表根据传入的hash值和key值查找到了节点,将该节点的value覆盖,返回oldValue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
if (++size > threshold) // 插入节点后超过阈值则进行扩容
resize();
afterNodeInsertion(evict); // 用于LinkedHashMap
return null;
}
- 梳理步骤如下：
- 算出传入的 Key 的hash值
- 判断当前数组是否为空或者大小是0，是的话进行初始化
- 需要注意，这里包括下面的代码有很多的在 if() 判断中进行赋值的操作，这个做法是不规范的
- 根据hash值定位到数组的index
- 取出对应的 Index 的数据进行判断
- 如果数据为Null，说明当前put的数据，是这个 index 的第一个数据，直接 new 一个新的节点，并将值赋给新的这个节点。
- 这时候要判断，新增一个数组元素后，数组元素的个数，如果超出阈值（概述中有说），那么就要resize，扩大数组的容量。
- 因为没有旧值，所以返回的旧值是 Null。
- 如果不是 Null， 证明数组要加入新的一个item了，按以下流程做出判断：
- 如果数据是 TreeNode，那么证明当前的 index 数据达到8个已经转成红黑树了，调用红黑树查找并加入子节点的方法，并持有最终的节点的对象 e
- 其他情况就是对应数据是链表，这时候要做以下操作
- 遍历链表去找是否有对应key的节点
- 如果到链表尾部都没找到，那么就新建一个节点 e ，新建之后注意要判断当前链表的长度，如果长度已经是7了（加入新节点就=8了），那么要把链表转成红黑树。
- 这里会校验数组是否为空，或者长度小于转树的最小长度64，如果是则调用resize方法进行扩容。原因应该是要转成树了，数组长度还这么短，那么说明可能是数组太小了，导致碰撞的概率很高，所以要扩容。
- 如果中途找到了，那么同样是持有找到的这个节点对象 e，跳出循环
- 最后判断 e 是否非空，非空代表找到已有节点/插入新节点成功了，这时候将put 传入的value 赋值给 e.value，然后将旧值返回。
- 如果数据为Null，说明当前put的数据，是这个 index 的第一个数据，直接 new 一个新的节点，并将值赋给新的这个节点。
- 至此，完成put的流程
-
删除
- remove(Object key)
- 再次看代码：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 如果table不为空并且根据hash值计算出来的索引位置不为空, 将该位置的节点赋值给p
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 如果p的hash值和key都与入参的相同, 则p即为目标节点, 赋值给node
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) // 如果p是TreeNode则调用红黑树的方法查找节点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do { // 遍历链表查找符合条件的节点
// 当节点的hash值和key与传入的相同,则该节点即为目标节点
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e; // 赋值给node, 并跳出循环
break;
}
p = e; // p节点赋值为本次结束的e
} while ((e = e.next) != null); // 指向像一个节点
}
}
// 如果node不为空(即根据传入key和hash值查找到目标节点)，则进行移除操作
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) // 如果是TreeNode则调用红黑树的移除方法
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 走到这代表节点是普通链表节点
// 如果node是该索引位置的头结点则直接将该索引位置的值赋值为node的next节点
else if (node == p)
tab[index] = node.next;
// 否则将node的上一个节点的next属性设置为node的next节点,
// 即将node节点移除, 将node的上下节点进行关联(链表的移除)
else
p.next = node.next;
++modCount; // 修改次数+1
--size; // table的总节点数-1
afterNodeRemoval(node); // 供LinkedHashMap使用
return node; // 返回被移除的节点
}
}
return null;
}
- 步骤解析如下：
- 首先还是算出传入的Key的hash值
- 然后判断数组是否为空，hash值对应的数组元素是否为空
- 很明显，为空就结束了，因为Map不存在该Key
- 将hash值对应的数组元素赋值给 P，判断 P 的 Key 是否和传入的 Key 相等
- 如果相等，那么需要移除的元素就直接找到了，赋值给 node
- 如果不相等，那么要查找一下了：
- 如果P是TreeNode，那么证明链表已经转成红黑树了，调用红黑树的查找方法，将返回值赋值给node
- 如果不是，则当前结构是链表，遍历链表查找符合的元素，将找到的值赋值给node
- 完成上述查找流程之后，判断node的属性
- 如果node为空，那么当前map中没有对应元素，直接返回null，方法结束
- 如果node是TreeNode，那么调用红黑树的remove方法，把这个节点remove掉。
- 要维持红黑树的特性，各种左旋右旋什么的。
需要注意，这里也包含一个红黑树长度判断，是否要转成链表，看下面这段代码- 上面这个得说明，这里看起来只是一个兜底的判断，实际触发概率应该很小
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
// 链表的处理start
// ...代码省略...
// 如果root的父节点不为空, 则将root赋值为根结点
// (root在上面被赋值为索引位置的头结点, 索引位置的头节点并不一定为红黑树的根结点)
if (root.parent != null)
root = root.root();
// 通过root节点来判断此红黑树是否太小, 如果是则调用untreeify方法转为链表节点并返回
// (转链表后就无需再进行下面的红黑树处理)
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
// 链表的处理end
// 以下代码为红黑树的处理, 上面的代码已经将链表的部分处理完成
// 上面已经说了this为要被移除的node节点,
// 将p赋值为node节点,pl赋值为node的左节点,pr赋值为node的右节点
// ...代码省略...
}
- 红黑树不是节点数量小于8就立马又变成链表的，这个应该很好理解，等于是有个缓冲区！
- 如果node不是TreeNode，那么就用链表的删除方法即可，这个是很简单的，直接改指针的指向就行。
- 最后结束流程，返回被删除的节点node的value值。
-
修改：这个应该不用说了，HashMap里面存的是对象的引用。
- 通过get方法拿到对象的引用之后，直接修改对象就行了。
- 或者通过put方法修改对应的Value值也可以。
四、总结
- HashMap，底层实现就是数组，不过数组的元素，是链表或者红黑树，因此如概述中所说，它是数组+链表/红黑树的结合体。
- HashMap的 hash算法：
- 计算Key对应的hash值
- 定位hash值对应的数组元素的index
- HashMap 判断数组中元素的属性
- 链表 --> 走链表的相关 增、删、查 方法
- 注意新加入值保存在链表的尾部（JDK1.7保存在首部）
- 红黑树 --> 走红黑树相关的 增、删、查 方法
- 链表 --> 走链表的相关 增、删、查 方法
- HashMap 增、删、扩容时，链表和红黑树要处理相互转换的情况：
- 链表长度 >8 --> 转成红黑树
- 如果转成红黑树时候，数组长度 <64，会触发扩容
- 红黑树节点数过少
- 看源码，remove是通过判断根节点的左右子树情况来判断的，应该是<4，（来自8.16的yyj：这个应该只是兜底判断吧，实际几率是很小的。
- 而扩容的时候，是通过阈值来判断的，<=6
- –> 转成链表
- 链表长度 >8 --> 转成红黑树
- HashMap 的数组的初始化，实际是在第一次 put 之后实现的。
- 初始化时会将此时的threshold值（构造方法传入的 capacity值）作为新表的capacity值。
- 然后用capacity和loadFactor计算新表的真正threshold值。
- HashMap 的扩容方法：
- 扩容其实就是把 tabel 中的元素，分散映射到大小为 n*2 的 newTabel 的过程
- 判断是否需要移动，就是判断：元素的 hash值 & n == 0
- 如果等于0，则不用移动，保持原位置
- 如果不等于0，那么就要移动到 oldIndex + n 的位置上去
- 当然，如果达到最大容量了，也就是 Integer.MAX 了，那就不能扩容了，这个也是很显然的。