HashMap

参考

红黑树

HashMap——讲解的很棒

说明

  • 线程不安全
  • 线程安全用 Hashtable
  • 与 Hashtable 的主要区别是 HashMap 不支持同步以及允许 null 作为键或值。

与 ConcurrentHashMap 与 Collections.synchronizedMap() 对比…

介绍

按自己思路大概讲一下。

HashMap 是面向查找的存储结构,避免了其余存储结构查找时的「比较」步骤(比如遍历线性表,会从头到尾一个一个地比较元素是否是想要查询的元素)。

  • 构造方法
  • 碰撞处理

通过键值来匹配元素。一个键对应一个值,所以就能达到类似数组的查找效率。一个 index 对应一个值,然后用近似 O(1) 的效率就能查找到某个元素。

散列函数

用到了一个方法(散列函数)。对应每一个 key,生成一个唯一的 hash 值。这个值对应这个 key 的存储地址。想象一下,查找时通过 key 获得存储地址,然后直接通过地址获得存储的元素对象。效率应该是比较高的…

HashMap 的 hash 函数

1
2
3
4
5
6
7
8
static final int hash(Object key) {
int h;
//h >>> 16 表示对 h 无符号右移 16 位,高位补 0,然后 h 与h >>> 16 按位异或
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

hash 函数的其他实现方式

数字分析法、平方取中法、分段叠加法、 除留余数法、 伪随机数法…

散列冲突

有可能多个 key 生成的 hash 值是一样的,那么就涉及到了碰撞处理。

在 HashMap 中,用拉链法 (链地址法)处理碰撞问题。

原理:把具有相同 hash 值的各个元素用一个链表维护。

HashMap 用链表数组实现。每个列表称为桶(bucket),(HashMap 里用 Entry 来维护)对元素进行相关操作时,先计算对象的散列码,然后与桶的总数取余,所得到的结果就是保存这个元素的索引。

比如进行元素插入操作时,通过计算找到了这个桶,然后发现在这个桶里已经有元素了,那么新插入的元素首先先与已经存在的元素作比较,查看是否存在相同的键值对。若存在就替换之(Map 不允许存储重复的 key),若不存在就插入到链表尾部。

因为有了链表,如果有多个 key 对应了相同的 hash 值,那么查找效率就变成了 O(n+a),a 是一个常数,就是链表的大小。

不过 jdk 1.8 在 HashMap 引入了红黑树。当链表长度大于 8 时,就把链表转化为红黑树。(在源码中体现为一个常量 static final int TREEIFY_THRESHOLD = 8

红黑树的理解查看二叉搜索树,2-3 搜索树…

可以想象,只有当元素非常多的时候才会触发这个转换操作。但是也并非元素多了就必定会触发这样的操作。

看源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 默认装填因子0.75,如果当前键值对个数 >= HashMap最大容量*装填因子,进行rehash操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* JDK1.8 新加,Entry链表最大长度,当桶中节点数目大于该长度时,将链表转成红黑树存储;
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* JDK1.8 新加,当桶中节点数小于该长度,将红黑树转为链表存储;
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶可能被转化为树形结构的最小容量.当哈希表的大小超过这个阈值,才会把链式结构转化成树型结构,否则仅采取
* 扩容来尝试减少冲突.
* 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突.
*/
static final int MIN_TREEIFY_CAPACITY = 64;

定义了 MIN_TREEIFY_CAPACITY 保证 当哈希表的大小超过这个阈值,才会把链式结构转化成树型结构,否则仅采取扩容来尝试减少冲突。

装填因子 DEFAULT_LOAD_FACTOR 决定何时对散列表进行扩容,默认 0.75 表示表中超过 75% 的位置已经填入元素,这个表就会以双倍的桶数自动地进行再散列。

解决哈希冲突的其他方法

拉链法

开放定址法 -> 冲突,查找下个内存单元

再散列 -> 重新散列直到不冲突

建立一个公共溢出区

红黑树

红黑树是什么呢?

红黑树是为了解决二叉排序树插入,删除导致的不平衡而产生的。

红黑树仍然是一个二叉搜索树。

二叉排序树的查询效率是 O(log n)。如果大量删除,二叉排序树就有可能变为一个单叶的树,此时查询效率就成了 O(n)。

而红黑树给某些节点分配了红黑两种颜色。每次插入、删除,都会进行一定的变换,维持红黑树的性质,重新上色。(变色,旋转…)使得 n 个节点始终保持 log n 的高度,让查询效率保持在 O(log n)。

1
2
3
4
public class HashMap<K, V> extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable {

}

实现 Map 接口。

成员常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 默认的初始容量(容量为HashMap中槽的数目)是16,且实际容量必须是2的整数次幂.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 --为什么不直接写 16?

/**
* 最大容量(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换)
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 默认装填因子0.75,如果当前键值对个数 >= HashMap最大容量*装填因子,进行rehash操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* JDK1.8 新加,Entry链表最大长度,当桶中节点数目大于该长度时,将链表转成红黑树存储;
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* JDK1.8 新加,当桶中节点数小于该长度,将红黑树转为链表存储;
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 桶可能被转化为树形结构的最小容量.当哈希表的大小超过这个阈值,才会把链式结构转化成树型结构,否则仅采取扩容来尝试减少冲突.
* 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突.
*/
static final int MIN_TREEIFY_CAPACITY = 64;

实际存储数据

HashMap 维护了一个内部类.

1
2
3
4
5
6
7
8
9
10
static class Node<K, V> implements Map.Entry<K, V> {
// hash存储key的hashCode
final int hash;
// final:一个键值对的key不可改变
final K key;
V value;
//指向下个节点的引用
Node<K, V> next;
...
}

这个类就是 HashMap 维护的节点(一个链表),准确来说是刚开始维护的节点,因为在一定情况下,该节点会由红黑树来维护。

它实现 Map 接口中的一个内部接口 Map.Entry。

put()

1
2
3
4
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
}

hash:key 计算得到的 hash 值。

key:键。

value:值。

onlyIfAbsent:key 在 map 中是否已经存在。

evict:…啥玩意?

过程

  1. 首先,对 key 计算出 hash 值。
  2. 然后判断。哈希表如果为空,创建一个哈希表,并用一个变量记录哈希表长度。
  3. 如果指定参数 hash 在表中没有对应的桶,说明未产生碰撞,直接将键值对插入 map。
  4. 如果桶已经存在元素,首先判断桶是否为红黑树结构。若是,按照红黑树结构插入键值对,如果是链表结构,就按照链表结构插入。
  5. 如果是链表结构,对链表从头到尾进行遍历。如果发现存在 key 相同的节点(通过 hash 判断),记录这个节点,跳出遍历。
  6. 如果参数 onlyIfAbsent 为 false,或者 oldValue 为 null,替换 value;否则不替换。
  7. 如果桶里没发现钙该元素的话,将键值对插入链表尾,size 相应 ++。如果链表长度达到阀值,将链表转换为红黑树维护。

get()

1
2
3
4
5
public V get(Object key) {
Node<K, V> e;
//根据key及其hash值查询node节点,如果存在,则返回该节点的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

用 hash() 计算出 key 的 hashCode,然后调用 getNode() 获取桶,再在桶里去获取元素。

在 getNode() 中,通过判断 key 和 hashCode,如果桶的第一个元素就匹配上了,那么直接返回该节点,如果没匹配上,就要对桶进行遍历。

如果桶是红黑树,那就用红黑树的查找方式。

如果桶是链表,就遍历链表…

没找到就返回 null。

rehash

1
2
3
4
/**
* 默认装填因子0.75,如果当前键值对个数 >= HashMap最大容量*装填因子,进行rehash操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

也就是说当键值对个数达到负载因子对应的个数,HashMap 就需要进行扩容 resize(),扩容后需要把原有的键值对放到新的 HashMap 中,这便是 rehash。

rehash 是发生在 resize() 中的一个过程。

而 resize() 是发生在 put() 操作中的。

在 put() 时判断 HashMap 的容量是否达到负载因子的要求,达到了就进行 resize()。resize() 的过程中进行 rehash。

JDK1.8 的 HashMap 为什么是链表长度大于 8 之后转为红黑树?

一个思路 :

只有长度 N >= 7 的时候,红黑树的平均查找长度 lgN 才会小于链表的平均查找长度 N/2。这个可以画函数图来确定,lgN 与 N/2 的交点处 N 约为 6.64。

为什么设置为 8 而不是 7 呢?一个原因是为了防止出现频繁的链表与树的转换,当大于8的时候链表转红黑树,小于6的时候红黑树转链表,中间这段作为缓冲。

loadDisqus