HashMap底层分析
HashMap初始化参数
//初始化容量大小,如果没有指定容量大小,则会在初始化HashMap时使用
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//定义了HashMap最大的内存容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当我们进行存放键值对时,如果对应哈希桶中的元素个数大于该值时,我们将该哈希桶改为一个二叉树
static final int TREEIFY_THRESHOLD = 8;
//当二叉树的容量大小小于该值时,我们将二叉树转换为对应的链表使用
static final int UNTREEIFY_THRESHOLD = 6;
//最小的树容量
static final int MIN_TREEIFY_CAPACITY = 64;
//节点类
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//返回节点的hashCode,是通过将键的hashCode和值的hashCode取异或
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
// 判断传入的o是否为当前对象的引用
if (o == this)
return true;
// 判断传入的o是否为Map.Entry的实例
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
HashMap静态方法分析
//获取key的hashCode
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//返回大于指定容量的第一个2的整次幂
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
HashMap使用变量(动态参数)
//节点数组,用于存放节点,可以理解为哈希桶
transient Node<K,V>[] table;
//用于保存缓存中的entrySet<>
transient Set<Map.Entry<K,V>> entrySet;
//键值对的数量
transient int size;
//hashmap结构更改次数
transient int modCount;
//当需要进行结构map结构更改时,进行判断,下一个容量大小值
int threshold;
//负载因子
final float loadFactor;
put方法
当我们在代码中调用到put方法时,默认调用请求的是Map接口中的方法,由于HashMap是实现了Map接口,所以,具体实现还是在HashMap中,下面是其中的源码并加以分析:
/**
* 将指定的值放入到指定的键值,构成一一对应的映射关系
*
* @param key 传入的键值
* @param value 键值所对应的值
* @return 返回与之前key关联的值
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Map.put()方法的具体实现
*
* @param hash 键对应的hash
* @param key 键值
* @param value 要放入的值
* @param onlyIfAbsent 如果该选项为true,则不能更改之前的值
* @param evict 如果该选项为false,则该表处于创建模式中
* @return 前一个值,或者返回为空
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定义一个节点数组
Node<K, V>[] tab;
// 定义一个节点,该节点是需要存放的节点
Node<K, V> p;
// 实例变量
int n, i;
// 该语句判断节点数组是否为null,或者tab的长度是否为0
if ((tab = table) == null || (n = tab.length) == 0)
// 若条件成立,则进行tab重新分配大小
n = (tab = resize()).length;
// 该语句通过键的hash值和数组长度来来确定元素的存放位置
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果当前位置为空,没有其他元素,则新建节点进行存放
tab[i] = newNode(hash, key, value, null);
else {
// 若不为空,则进行插入操作
Node<K, V> e;
K k;
// 此时我们的数组的位置处已经有了节点,
// p.hash == hash判断插入节点的hash值和对应键值的hash值
// (k = p.key) == key 拿出当前节点的键值与需要插入的key对应的hash进行比较(==:这里是比较两个对象在堆内存中的首地址是否相等)
// (key != null && key.equals(k)) 当key不为空,并且二者指向的是否为同一对象
// 倘若都满足以的条件,把 p 赋值给 e ,用于后面的是否为二叉树时判断
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果 p 是一个TreeNode 的实例变量,说明,该 index 下的节点,构成了一颗二叉树
else if (p instanceof TreeNode)
// 使用二叉树中的存储值的方法进行put,将该节点添加到树中去
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 如果不是 TreeNode 的实例,说明是按照链表的结构存储键值对的
else {
// 遍历这个数组 index 下的节点,链表
for (int binCount = 0; ; ++binCount) {
// 找到尾节点,将新的key-value构建成键值对形式的node放到链表的尾部
// 尾插法插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//进行检查是否需要进行转换位二叉树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 将该tab转换为二叉树
treeifyBin(tab, hash);
//如果不需要,跳出循环
break;
}
// 倘若都满足以下的条件,直接跳出本次循环
// 再次进行判断,这就说明,已经确确实实将键值对加入链表中去了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//进行不停的递归,直到尾插法之后,满足上面if中的条件,跳出循环
p = e;
}
}
//如果上一步把新键值对放入到集合中,则可以得知,该数组 index 处现在是有值的
// 同时说明该节点已经有值,值需对应更改我们的值,不用找寻新的键的位置
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) // 跟redis中的setnx类似
// 用新值覆盖旧值
e.value = value;
// 调用LinkedHashMap中的方法
afterNodeAccess(e);
return oldValue;
}
}
//版本控制
++modCount;
if (++size > threshold)
//如果插入后,size大于阈值,就进行扩容操作
resize();
// 调用LinkedHashMap中的方法
afterNodeInsertion(evict);
return null;
}
从上面的源码中可以分析到:
1、使用的尾插法进行新键值对的插入
2、插入之后再判断是否需要扩容
3、插入非线程安全(哈希碰撞、扩容导致的旧值覆盖问题)
putTreeVal方法
当将元素放到当前位置存在 hash 碰撞时,且元素个数大于 8 个的时候,就会转换为红黑树进行存储
final TreeNode<K, V> putTreeVal(MyHashMap<K, V> map, Node<K, V>[] tab,
int h, K k, V v) {
// 定义 key 的 Class 对象
Class<?> kc = null;
// 标志位,是否已经遍历过一遍红黑树,并非是从头节点开始遍历的,但是遍历路径上已经包含了后续需要对比的节点
boolean searched = false;
// 获取红黑树的头节点
TreeNode<K, V> root = (parent != null) ? root() : this;
// 从头节点开始遍历整个红黑树节点
for (TreeNode<K, V> p = root; ; ) {
// 定义方向和目前节点的hash值
int dir = 0, ph;
// 定义键对象
K pk;
// 如果当前节点的hash值大于待插入节点的hash值,则向左进行遍历树
if ((ph = p.hash) > h)
dir = -1;
// 如果当前节点的hash值小于待插入节点的hash值,则向右进行遍历树
else if (ph < h)
dir = 1;
// 若相等,则当前节点的键对象和待插入的键对象相等,返回当前节点,外层 put 方法进行值的更新
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
/*
* 走到这一步说明当前 key 没有实现 Comparable 接口,或者实现了 Comparable 接口并且和当前节点的 key 对象相等
* @param searched 标识是否已经遍历过一遍树节点了
* 如果没有遍历过,则遍历整个树节点,找到那个与待插入的 key 对象 equals 相等的节点
*/
if (!searched) {
TreeNode<K, V> q, ch;
// 标识已经遍历过一遍
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
// 找到了对应的值
return q;
}
// 到这一步说明遍历了所有节点都没有找到与我们待插入节点 equals 相等的节点 该方法一定能比个高低
dir = tieBreakOrder(k, pk); // 再比较一下但当前节点键和我们指定 key 键的大小
}
// 定义一个指向当前节点的节点 xp
TreeNode<K, V> xp = p;
// 根据 dir 来判断是走左边还是右边,并判断是否为空,若为空则进行插入值
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 获取当前节点的 next 节点
Node<K, V> xpn = xp.next;
// 创建一个节点,同时使得 x.next = xpn
TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
// 根据 dir 的大小来判断左右子树的插入
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 链表中的 next 节点指向这个树的新节点
xp.next = x;
// 这个新的树节点的父节点和前置接点均设置为当前的树节点,
x.parent = x.prev = xp;
// 如果原来的 next 节点不为空
if (xpn != null)
((TreeNode<K, V>) xpn).prev = x;
// 重新平衡并且新节点置顶
// moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
treeify()方法
该方法是当链表满足转换为红黑树的条件之后,将当前节点数组转换为红黑树。
/**
* 红黑树的构建
* 双向链表跟红黑树创建,主要步骤分3步。
*
* 1、从该双向链表中找第一个节点为 root 节点。
* 2、每一个双向链表节点都在 root 节点为根的二叉树中找位置然后将该数据插入到红黑树中,同时要注意balance。
* 3、最终要注意将根节点跟当前table[i]对应好。
* @param tab 元素数组
*/
final void treeify(Node<K, V>[] tab) {
TreeNode<K, V> root = null;
for (TreeNode<K, V> x = this, next; x != null; x = next) {
// 找到 root 节点,开始遍历链表
next = (TreeNode<K, V>) x.next;
x.left = x.right = null;
// 如果找不到头节点,为什么要判断根节点是否为空呢
if (root == null) {
// 当前节点的父节点为空
x.parent = null;
// 当前节点的红色属性设置为空,即当前节点为黑色节点
x.red = false;
// 令当前节点指向根节点
root = x;
} else {
// 如果根节点不为空
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K, V> p = root; ; ) {
// 开始从根节点开始遍历整个链表,开始构建二叉树
// 用 dir 来标识我们的左子树还是右子树
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 走到这一步说明当前 key 没有实现 Comparable 接口,或者实现了 Comparable 接口并且和当前节点的 key 对象相等
// 再次通过我们的 tieBreakOrder 进行比较
dir = tieBreakOrder(k, pk);
// 保存当前节点
TreeNode<K, V> xp = p;
// 这里进行比较挂载链表节点到树节点,根据 dir 进行判断
// 之后重新平衡,进行下一个链表操作
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 如果左子树和右子树都为空的话,那么将当前节点的父节点指向根节点
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}