HashMap源码解析和实现原理

一.HashMap简介

1.1 先了解下什么是hash表，

将需要检索的元素映射成可以快速检索的hash值，hashCode = hash(key); 存储hash值（即为hash桶）底层通常是用数组实现的，因为数组的随机寻址时间是O(1)常数时间（底层是硬件电路的线形地址变换直接查找过去，速度非常快根长度无关）。如果多个元素的hash值相同，称为hash碰撞。核心是基于哈希值的桶和链表。

致命缺陷就是hash碰撞。解决碰撞比较出名的有四种 ： (1)开放定址法 (2)链地址法 (3)再哈希法 (4)公共溢出区域法

1.2 原理

原理图：

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。 只是在JDK1.8中，链表长度大于8的时候，链表会转成红黑树！ 为什么用数组+链表？ 数组是用来确定桶的位置，利用元素的key的hash值对数组长度取模得到. 链表是用来解决hash冲突问题，当出现hash值一样的情形，就在数组上的对应位置形成一条链表。

ps:这里的hash值并不是指hashcode，而是将hashcode高低十六位异或过的。至于为什么要这么做，继续往下看。

我用LinkedList代替数组结构可以么? 这里我稍微说明一下，此题的意思是，源码中是这样的

1

Entry[] table = new Entry[capacity];

ps：Entry就是一个链表节点。 那我用下面这样表示

1

List<Entry> table = new LinkedList<Entry>();

是否可行?

答案很明显，必须是可以的。 但是效率会比数组慢。

既然是可以的,为什么HashMap不用LinkedList,而选用数组?

因为用数组效率最高！ 在HashMap中，定位桶的位置是利用元素的key的哈希值对数组长度取模得到。此时，我们已得到桶的位置。显然数组的查找效率比LinkedList大。

那ArrayList，底层也是数组，查找也快啊，为啥不用ArrayList?

因为采用基本数组结构，扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率高。 而ArrayList的扩容机制是1.5倍扩容，那ArrayList为什么是1.5倍扩容这就不在本文说明了。

1.3 HashMap 中 hash 函数怎么是实现的?

我们可以看到，在 hashmap 中要找到某个元素，需要根据 key 的 hash 值来求得对应数组中的位置。如何计算这个位置就是 hash 算法。

前面说过，hashmap 的数据结构是数组和链表的结合，所以我们当然希望这个 hashmap 里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个。那么当我们用 hash 算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。所以，我们首先想到的就是把 hashcode 对数组长度取模运算。这样一来，元素的分布相对来说是比较均匀的。

但是“模”运算的消耗还是比较大的，能不能找一种更快速、消耗更小的方式？我们来看看 JDK1.8 源码是怎么做的（被楼主修饰了一下）

1
2
3
4
5
6
7
8

static final int hash(Object key) {
  if (key == null){
  	return 0;
  }
  int h;
  h = key.hashCode()；返回散列值也就是hashcode
  return (n-1)&(h ^ (h >>> 16));
}

简单来说就是：

• 高16 bit 不变，低16 bit 和高16 bit 做了一个异或（得到的 hashcode 转化为32位二进制，前16位和后16位低16 bit和高16 bit做了一个异或）
• (n·1) & hash = -> 得到下标

1.4 拉链法导致的链表过深，为什么不用二叉查找树代替而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷：二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成层次很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋、右旋、变色这些操作来保持平衡。引入红黑树就是为了查找数据快，解决链表查询深度的问题。我们知道红黑树属于平衡二叉树，为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少。所以当长度大于8的时候，会使用红黑树；如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

1.5 CocurrentHashMap

1). JDK 1.7

• CocurrentHashMap 是由 Segment 数组和 HashEntry 数组和链表组成

• Segment 是基于重入锁（ReentrantLock）：
  一个数据段竞争锁。

• 每个 HashEntry 一个链表结构的元素，利用 Hash 算法得到索引确定归属的数据段，也就是对应到在修改时需要竞争获取的锁。

• ConcurrentHashMap 支持 CurrencyLevel（Segment 数组数量）的线程并发。
  每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment

• 核心数据如 value，以及链表都是 volatile 修饰的，保证了获取时的可见性

• 首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put 操作如下：

• • 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
  • 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value
  • 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容
  • 最后会解除在 1 中所获取当前 Segment 的锁。

• 虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理

首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。

• 尝试自旋获取锁
• 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。
  最后解除当前 Segment 的锁

2) （JDK 1.8）

CocurrentHashMap 抛弃了原有的 Segment 分段锁，采用了 CAS + synchronized 来保证并发安全性。其中的 val next 都用了 volatile 修饰，保证了可见性。

二.HashMap默认容量是多少？HashMap的数组大小为什么一定要是2的幂？

2.1HashMap默认容量是多少？

1
2
3
4

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默认初始容量为16，1左移4位等于16. 因为左移等于乘于2，即为2的幂。即为hash桶的数量必须是2的n次方。

2.2 如果自定义不是2的幂会怎样？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
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);
}

看这个构造方法知道，我们是可以自定义初始容量的

1
2
3
4
5
6
7
8
9
10
11
12

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

假如我们把initialCapacity调整为17，上面代码对于给定的目标容量，返回两倍大小的幂。如果我们调整为17就大于$2^4=16$ 就会4+1的操作，设置初始值为$2^5=32$。

2.3 为什么一定要是2的幂呢？

首先，hashCode是int类型，取值范围是$-2^{31}$到$+2^{31}$之间，需要解决怎么把取值范围映射到(0～N)如0～15上，N相对很小。tab[i = (n - 1) & hash] 即 数组的长度n减去1与hash(k)的值 &（按位与）运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null) //数组的长度n减去1与hash(k)的值 &（按位与）运算
            tab[i] = newNode(hash, key, value, null);
        else {

(Length - 1) & hash这样运算的原因，即为为什么一定是2的幂的原因？

$length=2^n$ 二进制表示为100000… 最高位是1低位全是0，所有length-1就能得到全部是1的二进制。例如：$2^4$二进制位10000，减1后二进制是1111。这样对1111按位与（&）运算能非常快速的拿到数组下标，并且分布还是均匀的。

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；因为2的n次方实际就是1后面n个0，2的n次方-1，实际就是n个1。 例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞。 而长度为5的时候，3&(5-1)=0 2&(5-1)=0，都在0上，出现碰撞了。 所以，保证容积是2的n次方，是为了保证在做(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算。

三.默认负载因子是多少？为什么选择这个值？

1
2
3
4

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

是时间和空间上的综合考量。

四.HashMap如何扩容？

1
2
3
4
5
6
7

/**
  * Constructs an empty <tt>HashMap</tt> with the default initial capacity
  * (16) and the default load factor (0.75).
  */
 public HashMap() {
     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }

HashMap的构造方法，默认初始容量为16，负载因子为0.75.当put值的时候才会有一个16容量的桶，空间才会开辟出来。

当一个hash桶中的元素的数量等于16*0.75=12的时候，就会扩容。每次扩容一倍，当元素减少时也不缩容。

四.HashMap为什么是线程不安全的？

此题可以组成如下连环炮来问

• HashMap在并发编程环境下有什么问题啊?
• 在jdk1.8中还有这些问题么?
• 你一般怎么解决这些问题的？

HashMap在并发编程环境下有什么问题啊?

• (1)多线程扩容，引起的死循环问题
• (2)多线程put的时候可能导致元素丢失
• (3)put非null元素后get出来的却是null

在jdk1.8中还有这些问题么?

在jdk1.8中，死循环问题已经解决。其他两个问题还是存在。

你一般怎么解决这些问题的？

比如ConcurrentHashmap，Hashtable等线程安全等集合类。

五.Java7到Java8做了哪些改进？为什么？

5.1 Java7中

• 非常容易碰到死锁

  首先造成死锁的原因是用户使用不规范，因为hashMap不是线程安全的。多个线程访问hash时就有可能死锁。

  

  当代码正好访问key:3或key:7时，就会出现死循环。cpu会爆满，造成死机。

  死锁的详细分析：https://coolshell.cn/articles/9606.html

• 有潜在的安全问题

  • CVE-2011-4858，Tomcat邮件组的讨论

    通过精心设计的hashcode相同http请求参数，会放到同一个桶里面， 会使其退化成链表，它的查找操作复杂度是O(n),N个元素的可能上升到n方。引发DoS

5.2 Java8中

• 由数组+链表的结构改为数组+链表+红黑树。
• 优化了高位运算的hash算法：h^(h>>>16)
• 扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。

最后一条是重点，因为最后一条的变动，hashmap在1.8中，不会在出现死循环问题。

为什么在解决hash冲突的时候，不直接用红黑树?而选择先用链表，再转红黑树?

因为TreeNode的大小约为常规节点的两倍，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。 当元素小于8个当时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。是不直接用红黑树的原因。

5.2.1当hash桶里面是链表的时候，结点在桶里的数量预值是多少，它会变成红黑树？

1
2
3
4
5
6
7
8
9

/**
 * 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.
 */
static final int TREEIFY_THRESHOLD = 8;

答案是8

5.2.2 为什么选择阀值是8，才转红黑树呢？

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
31
32
33
34
35
36
37
38

     * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
        
因为TreeNode的大小约为常规节点的两倍，所以我们
仅在垃圾箱包含足以保证使用的节点时才使用它们
（请参阅TREEIFY_THRESHOLD）。 当它们变得太小时（由于
移除或调整大小），它们会转换回普通垃圾箱。 在
分布良好的用户hashCode的用法
很少使用。 理想情况下，在随机hashCodes下，
箱中的节点遵循泊松分布
（http://en.wikipedia.org/wiki/Poisson_distribution），
默认调整大小的平均参数约为0.5
阈值0.75，尽管由于
调整粒度。 忽略差异，预期
列表大小k的出现是（exp（-0.5）* pow（0.5，k）/
阶乘（k））。 第一个值是：

因为，hash桶里面的节点个数服从柏松分布（平均参数$\lambda$约为0.5）,桶里有0个的概率为0.60653066，有1个的概率为0.30326533，有8个多概率为0.00000006，小于10亿分子1，概率非常小了。

5.2.3 当链表转为红黑树后，什么时候退化为链表?

为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

5.2.4 为什么为什么要先高16位异或低16位再取模运算?

六.hashmap的get/put的过程?

6.1 知道hashmap中put元素的过程是什么样么?

对key的hashCode()做hash运算，计算index; 如果没碰撞直接放到bucket里； 如果碰撞了，以链表的形式存在buckets后； 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)； 如果节点已经存在就替换old value(保证key的唯一性) 如果bucket满了(超过load factor*current capacity)，就要resize。

6.2 知道hashmap中get元素的过程是什么样么？

对key的hashCode()做hash运算，计算index; 如果在bucket里的第一个节点里直接命中，则直接返回； 如果有冲突，则通过key.equals(k)去查找对应的Entry;

• 若为树，则在树中通过key.equals(k)查找，O(logn)；
• 若为链表，则在链表中通过key.equals(k)查找，O(n)。

6.3 你还知道哪些hash算法？

先说一下hash算法干嘛的，Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。 比较出名的有MurmurHash、MD4、MD5等等

说说String中hashcode的实现?(此题频率很高)

1
2
3
4
5
6
7
8
9
10
11
12

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。

哈希计算公式可以计为s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

那为什么以31为质数呢?

主要是因为31是一个奇质数，所以31*i=32*i-i=(i<<5)-i，这种位移与减法结合的计算相比一般的运算快很多。

6.4 说说String中hashcode的实现?(此题频率很高)

1
2
3
4
5
6
7
8
9
10
11
12

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

七. 你一般用什么作为HashMap的key?

7.1健可以为Null值么?

必须可以，key为null的时候，hash算法最后的值以0来计算，也就是放在数组的第一个位置。

1
2
3
4

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

7.2你一般用什么作为HashMap的key?

一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。

• (1)因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
• (2)因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。

7.3 我用可变类当HashMap的key有什么问题?

hashcode可能发生改变，导致put进去的值，无法get出，如下所示

1
2
3
4
5
6
7
8

HashMap<List<String>, Object> changeMap = new HashMap<>();
List<String> list = new ArrayList<>();
list.add("hello");
Object objectValue = new Object();
changeMap.put(list, objectValue);
System.out.println(changeMap.get(list));
list.add("hello world");//hashcode发生了改变
System.out.println(changeMap.get(list));

输出值如下

1
2

java.lang.Object@74a14482
null

7.4 如果让你实现一个自定义的class作为HashMap的key该如何实现？

此题考察两个知识点

• 重写hashcode和equals方法注意什么?
• 如何设计一个不变类

针对问题一，记住下面四个原则即可

(1)两个对象相等，hashcode一定相等 (2)两个对象不等，hashcode不一定不等 (3)hashcode相等，两个对象不一定相等 (4)hashcode不等，两个对象一定不等

针对问题二，记住如何写一个不可变类

(1)类添加final修饰符，保证类不被继承。 如果类可以被继承会破坏类的不可变性机制，只要继承类覆盖父类的方法并且继承类可以改变成员变量值，那么一旦子类以父类的形式出现时，不能保证当前类是否可变。

(2)保证所有成员变量必须私有，并且加上final修饰 通过这种方式保证成员变量不可改变。但只做到这一步还不够，因为如果是对象成员变量有可能再外部改变其值。所以第4点弥补这个不足。

(3)不提供改变成员变量的方法，包括setter 避免通过其他接口改变成员变量的值，破坏不可变特性。

(4)通过构造器初始化所有成员，进行深拷贝(deep copy) 如果构造器传入的对象直接赋值给成员变量，还是可以通过对传入对象的修改进而导致改变内部变量的值。例如：

1
2
3
4
5
6

public final class ImmutableDemo {  
    private final int[] myArray;  
    public ImmutableDemo(int[] array) {  
        this.myArray = array; // wrong  
    }  
}

这种方式不能保证不可变性，myArray和array指向同一块内存地址，用户可以在ImmutableDemo之外通过修改array对象的值来改变myArray内部的值。 为了保证内部的值不被修改，可以采用深度copy来创建一个新内存保存传入的值。正确做法：

1
2
3
4
5
6

public final class MyImmutableDemo {  
    private final int[] myArray;  
    public MyImmutableDemo(int[] array) {  
        this.myArray = array.clone();   
    }   
}

(5)在getter方法中，不要直接返回对象本身，而是克隆对象，并返回对象的拷贝 这种做法也是防止对象外泄，防止通过getter获得内部可变成员对象后对成员变量直接操作，导致成员变量发生改变。

6.Resize效率很低。

参考资料：

https://zhuanlan.zhihu.com/p/76735726

https://www.bilibili.com/video/av71408100?from=search&seid=15190327219708388729

• ← Previous Post
• Next Post →

欢迎访问 chenyawei 的博客, 若有问题或者有好的建议欢迎留言，笔者看到之后会及时回复。 评论点赞需要github账号登录，如果没有账号的话请点击 github 注册， 谢谢 !