每个 java 程序员都知道,HashMap 是 java 中最重要的集合类之一,也是找工作面试中非常常见的考点,因为 HashMap 的实现本身确实蕴含了很多精妙的代码设计。
对于普通的程序员,可能仅仅能说出 HashMap 线程不安全,允许 key、value 为 null,以及不要求线程安全时,效率上比 HashTable 要快一些。稍微好一些的,会对具体实现有过大概了解,能说出 HashMap 由数组 + 链表 + RBT 实现,并了解 HashMap 的扩容机制。但如果你真的有一个刨根问题的热情,那么你肯定会想知道具体是如何一步步实现的。HashMap 的源码一共 2000 多行,很难在这里每一句都说明,但这篇文章会让你透彻的理解到我们平时常用的几个操作下,HashMap 是如何工作的。
要先提一下的是,我看过很多讲解 HashMap 原理的文章,有一些讲的非常好,但这些文章习惯于把源代码和逻辑分析分开,导致出现了大段的文字讲解代码,阅读起来有些吃力和枯燥。所以我想尝试另一种风格,将更多的内容写进注释里,可能看起来有些啰嗦,但对于一些新手的理解,应该会有好的效果。
首先是了解 HashMap 的几个核心成员变量(以下均为 jdk 源码):
- 1 transient Node[] table; //HashMap的哈希桶数组,非常重要的存储结构,用于存放表示键值对数据的Node元素。
- 2
- 3 transient Set> entrySet; //HashMap将数据转换成set的另一种存储形式,这个变量主要用于迭代功能。
- 4
- 5 transient int size;//HashMap中实际存在的Node数量,注意这个数量不等于table的长度,甚至可能大于它,因为在table的每个节点上是一个链表(或RBT)结构,可能不止有一个Node元素存在。
- 6
- 7 transient int modCount; //HashMap的数据被修改的次数,这个变量用于迭代过程中的Fail-Fast机制,其存在的意义在于保证发生了线程安全问题时,能及时的发现(操作前备份的count和当前modCount不相等)并抛出异常终止操作。
- 8
- 9 int threshold;//HashMap的扩容阈值,在HashMap中存储的Node键值对超过这个数量时,自动扩容容量为原来的二倍。
- 10
- 11 final float loadFactor;//HashMap的负载因子,可计算出当前table长度下的扩容阈值:threshold = loadFactor * table.length。
显然,HashMap 的底层实现是基于一个 Node 的数组,那么 Node 是什么呢?在 HashMap 的内部可以看见定义了这样一个内部类:
- 1 static class Node implements Map.Entry {
- 2final int hash;
- 3final K key;
- 4 V value;
- 5 Node next;
- 6 7 Node(int hash, K key, V value, Node next) {
- 8 this.hash = hash;
- 9 this.key = key;
- 10 this.value = value;
- 11 this.next = next;
- 12
- }
- 13 14 public final K getKey() {
- return key;
- }
- 15 public final V getValue() {
- return value;
- }
- 16 public final String toString() {
- return key + "=" + value;
- }
- 17 18 public final int hashCode() {
- 19
- return Objects.hashCode(key) ^ Objects.hashCode(value);
- 20
- }
- 21 22 public final V setValue(V newValue) {
- 23 V oldValue = value;
- 24 value = newValue;
- 25
- return oldValue;
- 26
- }
- 27 28 public final boolean equals(Object o) {
- 29
- if (o == this) 30
- return true;
- 31
- if (o instanceof Map.Entry) {
- 32 Map.Entry e = (Map.Entry) o;
- 33
- if (Objects.equals(key, e.getKey()) && 34 Objects.equals(value, e.getValue())) 35
- return true;
- 36
- }
- 37
- return false;
- 38
- }
- 39
- }
我们大体看一下这个内部类就可以知道,它实现了 Map.Entry 接口。其内部的变量含义也很明确,hash 值、key\value 对和实现链表和红黑树所需要的指针索引。
既然知道了 HashMap 的基本结构,那么这些变量的默认值都是多少呢?我们再看一下 HashMap 定义的一些常量:
- 1 //默认的初始容量为16,必须是2的幂次
- 2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
- 3
- 4 //最大容量即2的30次方
- 5 static final int MAXIMUM_CAPACITY = 1 << 30;
- 6
- 7 //默认加载因子
- 8 static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 9
- 10 //当put一个元素时,其链表长度达到8时将链表转换为红黑树
- 11 static final int TREEIFY_THRESHOLD = 8;
- 12
- 13 //链表长度小于6时,解散红黑树
- 14 static final int UNTREEIFY_THRESHOLD = 6;
- 15
- 16 //默认的最小的扩容量64,为避免重新扩容冲突,至少为4 * TREEIFY_THRESHOLD=32,即默认初始容量的2倍
- 17 static final int MIN_TREEIFY_CAPACITY = 64;
以上就是我们对 HashMap 的初步认识,下面进入正题,看看 HashMap 是如何添加、查找与删除数据的。
首先来看 put 方法,我尽量在每行都加注释阐明这一行的含义,让阅读起来更容易理解。
- 1 public V put(K key, V value) {
- 2
- return putVal(hash(key), key, value, false, true);
- 3
- }
- 4 5final V putVal(int hash, K key, V value, boolean onlyIfAbsent, //这里onlyIfAbsent表示只有在该key对应原来的value为null的时候才插入,也就是说如果value之前存在了,就不会被新put的元素覆盖。
- 6 boolean evict) { //evict参数用于LinkedHashMap中的尾部操作,这里没有实际意义。
- 7 Node[] tab;
- Node p;
- int n,
- i; //定义变量tab是将要操作的Node数组引用,p表示tab上的某Node节点,n为tab的长度,i为tab的下标。
- 8
- if ((tab = table) == null || (n = tab.length) == 0) //判断当table为null或者tab的长度为0时,即table尚未初始化,此时通过resize()方法得到初始化的table。
- 9 n = (tab = resize()).length; //这种情况是可能发生的,HashMap的注释中提到:The table, initialized on first use, and resized as necessary。
- 10
- if ((p = tab[i = (n - 1) & hash]) == null) //此处通过(n - 1) & hash 计算出的值作为tab的下标i,并另p表示tab[i],也就是该链表第一个节点的位置。并判断p是否为null。
- 11 tab[i] = newNode(hash, key, value, null); //当p为null时,表明tab[i]上没有任何元素,那么接下来就new第一个Node节点,调用newNode方法返回新节点赋值给tab[i]。
- 12
- else { //下面进入p不为null的情况,有三种情况:p为链表节点;p为红黑树节点;p是链表节点但长度为临界长度TREEIFY_THRESHOLD,再插入任何元素就要变成红黑树了。
- 13 Node e;
- K k; //定义e引用即将插入的Node节点,并且下文可以看出 k = p.key。
- 14
- if (p.hash == hash && //HashMap中判断key相同的条件是key的hash相同,并且符合equals方法。这里判断了p.key是否和插入的key相等,如果相等,则将p的引用赋给e。
- 15((k = p.key) == key || (key != null && key.equals(k)))) //这一步的判断其实是属于一种特殊情况,即HashMap中已经存在了key,于是插入操作就不需要了,只要把原来的value覆盖就可以了。
- 16 e = p; //这里为什么要把p赋值给e,而不是直接覆盖原值呢?答案很简单,现在我们只判断了第一个节点,后面还可能出现key相同,所以需要在最后一并处理。
- 17
- else if (p instanceof TreeNode) //现在开始了第一种情况,p是红黑树节点,那么肯定插入后仍然是红黑树节点,所以我们直接强制转型p后调用TreeNode.putTreeVal方法,返回的引用赋给e。
- 18 e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value); //你可能好奇,这里怎么不遍历tree看看有没有key相同的节点呢?其实,putTreeVal内部进行了遍历,存在相同hash时返回被覆盖的TreeNode,否则返回null。
- 19
- else { //接下里就是p为链表节点的情形,也就是上述说的另外两类情况:插入后还是链表/插入后转红黑树。另外,上行转型代码也说明了TreeNode是Node的一个子类。
- 20
- for (int binCount = 0;; ++binCount) { //我们需要一个计数器来计算当前链表的元素个数,并遍历链表,binCount就是这个计数器。
- 21
- if ((e = p.next) == null) { //遍历过程中当发现p.next为null时,说明链表到头了,直接在p的后面插入新的链表节点,即把新节点的引用赋给p.next,插入操作就完成了。注意此时e赋给p。
- 22 p.next = newNode(hash, key, value, null); //最后一个参数为新节点的next,这里传入null,保证了新节点继续为该链表的末端。
- 23
- if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //插入成功后,要判断是否需要转换为红黑树,因为插入后链表长度加1,而binCount并不包含新节点,所以判断时要将临界阈值减1。
- 24 treeifyBin(tab, hash); //当新长度满足转换条件时,调用treeifyBin方法,将该链表转换为红黑树。
- 25
- break; //当然如果不满足转换条件,那么插入数据后结构也无需变动,所有插入操作也到此结束了,break退出即可。
- 26
- }
- 27
- if (e.hash == hash && //在遍历链表的过程中,我之前提到了,有可能遍历到与插入的key相同的节点,此时只要将这个节点引用赋值给e,最后通过e去把新的value覆盖掉就可以了。
- 28((k = e.key) == key || (key != null && key.equals(k)))) //老样子判断当前遍历的节点的key是否相同。
- 29
- break; //找到了相同key的节点,那么插入操作也不需要了,直接break退出循环进行最后的value覆盖操作。
- 30 p = e; //在第21行我提到过,e是当前遍历的节点p的下一个节点,p = e 就是依次遍历链表的核心语句。每次循环时p都是下一个node节点。
- 31
- }
- 32
- }
- 33
- if (e != null) { // existing mapping for key//左边注释为jdk自带注释,说的很明白了,针对已经存在key的情况做处理。
- 34 V oldValue = e.value; //定义oldValue,即原存在的节点e的value值。
- 35
- if (!onlyIfAbsent || oldValue == null) //前面提到,onlyIfAbsent表示存在key相同时不做覆盖处理,这里作为判断条件,可以看出当onlyIfAbsent为false或者oldValue为null时,进行覆盖操作。
- 36 e.value = value; //覆盖操作,将原节点e上的value设置为插入的新value。
- 37 afterNodeAccess(e); //这个函数在hashmap中没有任何操作,是个空函数,他存在主要是为了linkedHashMap的一些后续处理工作。
- 38
- return oldValue; //这里很有意思,他返回的是被覆盖的oldValue。我们在使用put方法时很少用他的返回值,甚至忘了它的存在,这里我们知道,他返回的是被覆盖的oldValue。
- 39
- }
- 40
- }41++modCount; //收尾工作,值得一提的是,对key相同而覆盖oldValue的情况,在前面已经return,不会执行这里,所以那一类情况不算数据结构变化,并不改变modCount值。
- 42
- if (++size > threshold) //同理,覆盖oldValue时显然没有新元素添加,除此之外都新增了一个元素,这里++size并与threshold判断是否达到了扩容标准。
- 43 resize(); //当HashMap中存在的node节点大于threshold时,hashmap进行扩容。
- 44 afterNodeInsertion(evict); //这里与前面的afterNodeAccess同理,是用于linkedHashMap的尾部操作,HashMap中并无实际意义。1
- 45
- return null; //最终,对于真正进行插入元素的情况,put函数一律返回null。
- 46
- }
在上述代码中的第十行,HashMap 根据 (n - 1) & hash 求出了元素在 node 数组的下标。这个操作非常精妙,下面我们仔细分析一下计算下标的过程,主要分三个阶段:计算 hashcode、高位运算和取模运算。
首先,传进来的 hash 值是由 put 方法中的 hash(key) 产生的(上述第 2 行),我们来看一下 hash() 方法的源码:
- 1 static final int hash(Object key) {
- 2 int h;
- 3
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- 4
- }
这里通过 key.hashCode() 计算出 key 的哈希值,然后将哈希值 h 右移 16 位,再与原来的 h 做异或 ^ 运算——这一步是高位运算。设想一下,如果没有高位运算,那么 hash 值将是一个 int 型的 32 位数。而从 2 的 - 31 次幂到 2 的 31 次幂之间,有将近几十亿的空间,如果我们的 HashMap 的 table 有这么长,内存早就爆了。所以这个散列值不能直接用来最终的取模运算,而需要先加入高位运算,将高 16 位和低 16 位的信息" 融合 "到一起,也称为" 扰动函数 "。这样才能保证 hash 值所有位的数值特征都保存下来而没有遗漏,从而使映射结果尽可能的松散。最后,根据 n-1 做与操作的取模运算。这里也能看出为什么 HashMap 要限制 table 的长度为 2 的 n 次幂,因为这样,n-1 可以保证二进制展示形式是(以 16 为例)0000 0000 0000 0000 0000 0000 0000 1111。在做" 与 "操作时,就等同于截取 hash 二进制值得后四位数据作为下标。这里也可以看出" 扰动函数 " 的重要性了,如果高位不参与运算,那么高 16 位的 hash 特征几乎永远得不到展现,发生 hash 碰撞的几率就会增大,从而影响性能。
HashMap 的 put 方法的源码实现就是这样了,整理思路非常连贯。这里面有几个函数的源码(比如 resize、putTreeValue、newNode、treeifyBin)限于篇幅原因,就不贴了,后面应该还会更新在其他博客里,有兴趣的同学也可以自己挖掘一下。
读完了 put 的源码,其实已经可以很清晰的理清 HashMap 的工作原理了。接下来再看 get 方法的源码,就非常的简单:
- 1 public V get(Object key) {
- 2 Node e;
- 3
- return (e = getNode(hash(key), key)) == null ? null: e.value; //根据key及其hash值查询node节点,如果存在,则返回该节点的value值。
- 4
- }
- 5 6 final Node getNode(int hash, Object key) { //根据key搜索节点的方法。记住判断key相等的条件:hash值相同 并且 符合equals方法。
- 7 Node[] tab;
- Node first,
- e;
- int n;
- K k;
- 8
- if ((tab = table) != null && (n = tab.length) > 0 && //根据输入的hash值,可以直接计算出对应的下标(n - 1)& hash,缩小查询范围,如果存在结果,则必定在table的这个位置上。
- 9(first = tab[(n - 1) & hash]) != null) {
- 10
- if (first.hash == hash && // always check first node
- 11((k = first.key) == key || (key != null && key.equals(k)))) //判断第一个存在的节点的key是否和查询的key相等。如果相等,直接返回该节点。
- 12
- return first;
- 13
- if ((e = first.next) != null) { //遍历该链表/红黑树直到next为null。
- 14
- if (first instanceof TreeNode) //当这个table节点上存储的是红黑树结构时,在根节点first上调用getTreeNode方法,在内部遍历红黑树节点,查看是否有匹配的TreeNode。
- 15
- return ((TreeNode) first).getTreeNode(hash, key);
- 16 do {
- 17
- if (e.hash == hash && //当这个table节点上存储的是链表结构时,用跟第11行同样的方式去判断key是否相同。
- 18((k = e.key) == key || (key != null && key.equals(k)))) 19
- return e;
- 20
- } while (( e = e . next ) != null); //如果key不同,一直遍历下去直到链表尽头,e.next == null。
- 21
- }
- 22
- }
- 23
- return null;
- 24
- }
因为查询过程不涉及到 HashMap 的结构变动,所以 get 方法的源码显得很简洁。核心逻辑就是遍历 table 某特定位置上的所有节点,分别与 key 进行比较看是否相等。
以上便是 HashMap 最常用 API 的源码分析,除此之外,HashMap 还有一些知识需要重点学习:扩容机制、并发安全问题、内部红黑树的实现。这些内容我也会在之后陆续发文分析,希望可以帮读者彻底理解 HashMap 的原理。
来源: http://www.cnblogs.com/jzb-blog/p/6637823.html