HashMap实现和源码分析

作者: cyw1227 | 来源:发表于2019-12-15 15:22 被阅读0次

一.HashMap简介

1.1 先了解下什么是hash表，

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

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

1.2 原理

原理图：

image-20191215124612391

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

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

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

Entry[] table = new Entry[capacity];

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

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 源码是怎么做的（被楼主修饰了一下）

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

image-20191215131412249

简单来说就是：

高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默认容量是多少？

    /**
     * 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的幂会怎样？

    /**
     * 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);
    }

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

    /**
     * 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)的值 &（按位与）运算。

/**
     * 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进行与运算。

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

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

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

四.HashMap如何扩容？

   /**
     * 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时就有可能死锁。
image-20191215113532801
当代码正好访问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桶里面是链表的时候，结点在桶里的数量预值是多少，它会变成红黑树？

    /**
     * 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，才转红黑树呢？

     * 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位再取模运算?

image-20191215121954442

六.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的实现?(此题频率很高)

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的实现?(此题频率很高)

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来计算，也就是放在数组的第一个位置。

    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出，如下所示

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));

输出值如下

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) 如果构造器传入的对象直接赋值给成员变量，还是可以通过对传入对象的修改进而导致改变内部变量的值。例如：

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

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

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