文章目录
HashMap 是一个最通用的利用哈希表存储元素的集合,将元素放入 HashMap 时,将key的哈希值转换为数组的索引下标确定存放位置,查找时,根据key的哈希地址转换成数组的索引下标确定查找位置。
HashMap 底层是用数组 + 链表 + 红黑树这三种数据结构实现,它是非线程安全的集合。
整体架构
HashMap 底层的数据结构主要是:数组 + 链表 + 红黑树。其中当
链表的长度大于等于 8 并且数组的大小大于64时,链表会转化成红黑树,当红黑树的大小小于等于 6 时,红黑树会转化成链表
,整体的数据结构如下:
图中左边竖着的是 HashMap 的数组结构,数组的元素可能是单个 Node,也可能是个链表,也可能是个红黑树,比如数组下标索引为 1 的位置就是一个链表,下标索引为 8 的位置对应的就是红黑树。
源码类注释
通过类注释可以获取一下信息:
- 允许 null 值,不同于 HashTable ,是线程不安全的;
-
load factor(负载因子) 默认值是 0.75, 是均衡了时间和空间损耗算出来的值,较高的值会减少空间开销(扩容减少,数组大小增长速度变慢),但增加了查找成本(hash 冲突增加,链表长度变长),不扩容的条件:数组容量 > 需要的数组大小 /load factor,可以查看
散列表
这种数据结构。 - 建议 HashMap 的容量一开始就设置成足够的大小,这样可以防止在其过程中不断的扩容,影响性能;
- HashMap 是非线程安全的,我们可以自己在外部加锁,或者通过 Collections#synchronizedMap 来实现线程安全,Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁;
- 在迭代过程中,如果 HashMap 的结构被修改,会快速失败。
常见的属性
/**
* The default initial capacity - MUST be a power of two.
* 初始容量是16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
* 负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* 链表长度大于等于8时,链表转化成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
* 红黑树大小小于等于6时,红黑树转化成链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
* 数组容量大于 64 时,链表才会转化成红黑树
*/
static final int MIN_TREEIFY_CAPACITY = 64;
//记录迭代过程中 HashMap 结构是否发生变化,如果有变化,迭代时会 fail-fast
transient int modCount;
//HashMap 的实际大小,可能不准(因为当你拿到这个值的时候,可能又发生了变化)
transient int size;
//存放数据的数组
transient Node<K,V>[] table;
// 扩容的门槛,有两种情况
// 如果初始化时,给定数组大小的话,通过 tableSizeFor 方法计算,数组大小永远接近于 2 的幂次方,比如你给定初始化大小 19,实际上初始化大小为 32,为 2 的 5 次方。
// 如果是通过 resize 方法进行扩容,大小 = 数组容量 * 0.75
int threshold;
//链表的节点
static class Node<K,V> implements Map.Entry<K,V> {
//红黑树的节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
HashMap的主要操作
// 初始化方法一(第二个参数负载因子是单精度浮点型)
Map<String, String> kvHashMap = new HashMap<>(16, 0.7f);
//初始化方法二
HashMap<Object, Object> objectObjectHashMap = new HashMap<>();
// 初始化方法三
HashMap<String, String> hashMap1 = new HashMap<>(kvHashMap);
// 初始化方法四
Map<String, Double> hashMap = new HashMap<>(16);
hashMap.put("k1", 0.1);
hashMap.put("k2", 0.2);
hashMap.put("k3", 0.3);
hashMap.put("k4", 0.4);
Double aDouble = hashMap.putIfAbsent("k5", 1.2);
for (String s : hashMap.keySet()) {
System.out.println(hashMap.get(s));
}
新增
新增 entry 大概的步骤如下:
1:空数组有无初始化,没有的话初始化;
2:如果通过 key 的 hash 能够直接找到值,跳转到 6,否则到 3;
3:如果 hash 冲突,两种解决方案:链表 or 红黑树;
4:如果是链表,递归循环,把新元素追加到队尾;
5:如果是红黑树,调用红黑树新增的方法;
6:通过 2、4、5 将新元素追加成功,再根据 onlyIfAbsent 判断是否需要覆盖;
7:判断是否需要扩容,需要扩容进行扩容,结束。
代码如下:
/**
* Implements Map.put and related methods.
*
* @param hash hash for key:通过hash算法计算出来的值
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value:false表示即使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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;// n:数组长度,i:数组索引下标,p:i下标位置的node值
if ((tab = table) == null || (n = tab.length) == 0)// 如果数组为空,使用resize方法初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)// 如果当前索引位置是空的,直接生成新的节点在当前索引上
tab[i] = newNode(hash, key, value, null);
else { //如果当前索引位置有值的处理方法,需要解决 hash 冲突
Node<K,V> e; K k; // e 当前节点的临时变量,临时存储位置
if (p.hash == hash && // 如果 key 的 hash 和值都相等,直接把当前下标位置的 Node 值赋值给临时变量
((k = p.key) == key || (key != null && key.equals(k))))
e = 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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);// 当链表的长度大于等于 8 时,链表转红黑树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;// 链表遍历过程中,发现有元素和新增的元素相等,结束循环
p = e;//更改循环的当前元素,使 p 在遍历过程中,一直往后移动。
}
}// 说明新节点的新增位置已经找到了
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)// 当 onlyIfAbsent 为 false 时,才会覆盖值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)//如果 HashMap 的实际大小大于扩容的门槛,开始扩容
resize();
afterNodeInsertion(evict);
return null;
}
链表的新增节点过程
链表的新增比较简单,就是把当前节点追加到链表的尾部,和 LinkedList 的追加实现一样的。当链表长度大于等于 8 时,此时的链表就会转化成红黑树,转化的方法是:treeifyBin,此方法有一个判断,
当链表长度大于等于 8,并且整个数组大小大于 64 时,才会转成红黑树,当数组大小小于 64 时,只会触发扩容,不会转化成红黑树。
为什么当链表长度大于等于 8 时,链表才会转化成红黑树?
链表查询的时间复杂度是 O (n),红黑树的查询复杂度是 O (log (n))。在链表数据不多的时候,使用链表进行遍历也比较快,只有当链表数据比较多的时候,才会转化成红黑树,但红黑树需要的占用空间是链表的 2 倍,考虑到转化时间和空间损耗,所以需要定义出转化的边界值。
红黑树的新增节点过程
红黑树新增节点的过程大概分为以下几个步骤:
1:判断新增节点是否在红黑是中已经存在,判断手段有两种:
-
如果节点没有实现 Comparable 接口,使用
equals
进行判断; -
如果节点自己实现了 Comparable 接口,使用
compareTo
进行判断。
2:如果新增节点已经在红黑树中,直接返回,不在的话判断新增节点是在当前节点的左边还是右边,左边小右边大。
3:自旋递归 1 和 2 步,
直到当前节点的左边或者右边的节点为空时
,停止自旋,
当前节点即为我们新增节点的父节点
;
4:
把新增节点放到当前节点的左边或右边为空的地方
,并于当前节点建立父子节点关系;
5:进行
着色和旋转
,结束。
源代码如下:
/**
* Tree version of putVal. 红黑树的新增节点过程
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
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) {
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;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
查找
HashMap 的查找主要分为以下三步:
1:根据 hash 算法定位数组的索引位置,equals 判断当前节点是否是我们需要寻找的 key,是的话直接返回,不是的话往下。
2:判断当前节点有无 next 节点,有的话判断是链表类型,还是红黑树类型。
4:分别走链表和红黑树不同类型的查找方法。
主要代码如下:
// 采用自旋方式从链表中查找 key,e 初始为为链表的头节点
do {
// 如果当前节点 hash 等于 key 的 hash,并且 equals 相等,当前节点就是我们要找的节点
// 当 hash 冲突时,同一个 hash 值上是一个链表的时候,我们是通过 equals 方法来比较 key 是否相等的
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
// 否则,把当前节点的下一个节点拿出来继续寻找
} while ((e = e.next) != null);