HashMap解决了什么问题？

任何数据结构的产生总对应要解决一个实际的问题，HashMap的产生要解决问题就是：

如何有效的存取一组 key-value键值对

key-value 键值对是最常使用的数据形式，如何有效地存取他们是众多语音都需要关注的问题。注意这里有四个关键字:
1.key-value键值对
2.一组
3.存
4.取

如何表示key-value键值对

在java这种面向对象的语音中，表示一个数据结构自然要用到类，由于键值对的数据类型事先并不清楚，显而易见应该要用泛型，则表示key-value键值对最简单的形式可以是：

class Node<K,V>{
  K key;
  V value;
}

这里我们自定义一个Node类，它只有两个属性，一个key属性表示键，一个value属性表示值，则这个类就代表了一个key-value键值对。

是不是很简单？

当然，我们还需要定义一些方法来操纵这两个属性，例如get和set方法等，不过根据设计原则，我们应该面向接口编程，所以应该定义一个接口来描述需要执行的操作，这个接口就是Entry<K,V>,它只不过是对于Node<K,V>这个类的抽象，在java中，这个接口定义在Map这个接口中，所以上面的类可以改为:

class Node<K,V> implements Map.Entry<K,V>{
    K key;
    V value;
}

这里我们总结一下：

我们定义了一个Node类来表示一个键值对，为了面向接口编程，我们抽象出一个Entry接口，并使Node类实现了这个接口。

这样，到目前为止，我们完成了对于key-value键值对的表示。

如何存储key-value键值对的集合

在常见的业务逻辑中，我们常常需要处理一组键值对的集合，将一组键值对存储在一处，并根据key值取查找对应的value。
那么我们要如何存储这些键值对的集合呢？

其实换个问法可能更容易回答：

应该怎样存储一组对象？
(毕竟键值对已经被我们表示为Node对象了)

在java中，存储一个对象的集合无外乎两种方式：

1. 数组

2. 链表

关于数组和链表的优缺点大家已经耳熟能详了：

• 数组大小有限，查找性能好，插入和删除性能差
• 链表大小不限，查找性能差，插入和删除性能好

这里应该选那种形式呢？那得看实际的应用了，在使用键值对时，查找和插入，删除等操作都会用到，但是在实际的应用场景中，对于键值对的查找操作居多，所以我们当然选择数组形式。

Node<K,V> [] table;

总结:我们选择数组形式来存储key-value对象。

如何有效地根据key值查找value

前面已经讲过，我们选择数组形式来存储key-value对象，以利用其优良的查找性能，数组之所以查找迅速，是因为可以根据索引(数组下标)直接定位到对应的存储桶(数组所存储对象的位置)

但是实际应用中，我们都是通过key值来查找value值，怎么办呢？
一种方式就是遍历数组中的每一个对象, 查看它的key是不是我们要找的key, 但是很明显, 这种方式效率低下(而且这不就是链表的顺序查找方式吗?) 完全违背了我们选择数组来存储键值对的初衷.

为了利用索引来查找, 我们需要建立一个 key -> index 的映射关系, 这样每次我们要查找一个 key时, 首先根据映射关系, 计算出对应的数组下标, 然后根据数组下标, 直接找到对应的key-value对象, 这样基本能以o(1)的时间复杂度得到结果.

这里, 将key映射成index的方法称为hash算法, 我们希望它能将 key均匀的分布到数组中.

这里插一句,使用Hash算法同样补足了数组插入和删除性能差的短板, 我们知道, 数组之所以插入删除性能差是因为它是顺序存储的, 在一个位置插入节点或者删除节点需要一个个移动它的后续节点来腾出位或者覆盖位置.

使用hash算法后, 数组不再按顺序存储, 插入删除操作只需要关注一个存储桶即可, 而不需要额外的操作.

如何解决hash冲突

这个问题其实是由上一个问题引出的, 虽然我们要求hash算法能将key均匀的分布到数组中, 但是它只能尽量做到, 并不是绝对的, 更何况我们的数组大小是有限的, 保不齐我们的hash算法将就两个不同的key映射成了同一个index值, 这就产生了hash冲突, 也就是两个Node要存储在数组的同一个位置该怎么办?

解决hash冲突的方法有很多, 在HashMap中我们选择链地址法, 即在产生冲突的存储桶中改为单链表存储。

其实，最理想的效果是，Entry数组中每个位置都只有一个元素，这样查询的时候效率最高，不需要遍历单链表，也不需要通过equals取比较key，而且空间利用率最大。

链地址法使我们的数组转变成了链表的数组：

image.png

至此，我们对key-value键值对的表示变为:

class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    ...
}

链表长度过长怎么办

我们知道，链表查找只能通过顺序查找来实现，因此，时间复杂度为o(n),如果不巧，我们的key值被hash算法映射到一个存储桶上，将会导致存储桶上的链表长度越来越长，此时，数组查找退化成链表查找，则时间复杂度由原来的o(1)退化为o(n)

为了解决这一问题，在java8中，当链表长度超过8之后，将自动将链表转换为红黑树，以实现o(logn)的时间复杂度，从而提升查找性能.

image.png

什么时候扩容

前面已经说到, 数组的大小是有限的, 在新建的时候就要指定, 如果加入的节点已经到了数组容量的上限, 已经没有位置能够存储key-value键值对了, 此时就需要扩容.

但是很明显, 我们不会等到火烧眉毛了才想起来要扩容, 在实际的应用中, 数组空间已使用3/4之后, 我们就会括容.

为什么是0.75呢, 官方文档的解释是:

the default load factor (.75) offers a good tradeoff between time and space costs.

再说回扩容, 有的同学就要问了, 咱上面不是将数组的每一个元素转变成链表了吗? 就算此时节点数超过了数组大小, 新加的节点会存在数组某一个位置的链表里啊, 链表的大小不限, 可以存储任意数量的节点啊!

没错, 理论上来说这样确实是可行的, 但这又违背了我们一开始使用数组来存储一组键值对的初衷, 还记得我们选择数组的原因是什么吗? 为了利用索引快速的查找!

如果我们试图指望利用链表来扩容的话, 当一个存储桶的中的链表越来越大, 在这个链表上的查找性能就会很差(退化成顺序查找了)

为此, 在数组容量不足时, 为了继续维持利用数组索引查找的优良性能, 我们必须对数组进行扩容.

链表存在的意义只是为了解决hash冲突, 而不是为了增大容量. 事实上, 我们希望链表的长度越短越好, 或者最好不要出现链表.

每次扩容扩多大

上一节我们讨论了扩容的时机, 接下来的另一问题就是每次多增加多少空间.

我们知道, 数组的扩容是一个很耗费CPU资源的动作, 需要将原数组的内容复制到新数组中去, 因此频繁的扩容必然会导致性能降低, 所以不可能数组满了之后, 每多加一个node, 我们就扩容一次.
但是, 一次扩容太大, 导致大量的存储空间用不完, 势必又造成很大的浪费, 因此, 必须根据实际情况设定一个合理的扩容大小.

在HashMap的实现中, 每次扩容我们都会将新数组的大小设为原数组大小的两倍.

hash算法

为了利用数组索引进行快速查找，我们需要先将key值映射成数组下标。因为数组的下标是有限的集合，所以我们可以先通过hash算法将key映射成整数，在将整数映射成有限的数组下标：

Object->int->index

对于Object->int部分，使用的就是hash function，而对于int->index部分，我们可以简单的使用对数组大小取模来实现。

下面我们就来看看HashMap使用了什么hash算法。

在java中，hash函数是一个native方法，这个定义在Object类中，所以所有的对象都会继承。

public native int hashCode();

这是一个本地方法，所以我们无法看到它的具体实现，但是从函数签名上可以看出，该方法将任意对象映射成一个整型值，调用该方法，我们就完成了Object->int的映射

所以将key映射成index的方式可以是

key.hashCode() % table.length

那么hashMap是这样做的吗？事实上，HashMap定义了自己的散列方法:

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

另外，从这个函数中，我们还可以得到一个意外收获：

HashMap中key值可以为null，且null值一定存储在数组的第一个位置。

性能提升

前面我们提到，将hash值转换成数组下标我们可以采用取模运算，但是取模运算是十分耗时的，另一方面，当一个数是2^n时，任意整数对2^n 取模等效于

h % 2^n = h & (2^n -1)

这样我们就将取模操作转换成了位操作，而位操作的速度远远快于取模操作。
为此，HashMap中，table的大小都是2的n次方，即使你在构造函数中指定了table的大小，HashMap也会将该值扩大为距离它最近的2的整数次幂的值。

构造函数

HashMap中共有四个构造函数

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

    // 默认初始大小 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    // 默认负载因子 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
     
    final float loadFactor;
    
    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;
    
    transient Node<K,V>[] table;
     
    // 没有指定时, 使用默认值
    // 即默认初始大小16, 默认负载因子 0.75
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    // 指定初始大小, 但使用默认负载因子
    // 注意这里其实是调用了另一个构造函数
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    // 指定初始大小和负载因子
    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);
    }
    
    // 利用已经存在的map创建HashMap
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
        
}

不知道大家发现了没有，即使我们在构造函数中指定了initialCapacity，这个值也只被用来计算threshold

 this.threshold=tableSizeFor(initialCapacity);

通过上面的构造函数可知，table的初始化或者使用不是在构造函数中进行的，而是实际用到的时候，事实上，它是在HashMap扩容的时候实现的，即resize函数。

resize

resize用于以下两种情况之一

• 初始化table
• 在table大小超过threshold之后进行扩容

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 原table中已经有值
    if (oldCap > 0) {
    
        // 已经超过最大限制, 不再扩容, 直接返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        // 注意, 这里扩容是变成原来的两倍
        // 但是有一个条件: `oldCap >= DEFAULT_INITIAL_CAPACITY`
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    
    // 在构造函数一节中我们知道
    // 如果没有指定initialCapacity, 则不会给threshold赋值, 该值被初始化为0
    // 如果指定了initialCapacity, 该值被初始化成大于initialCapacity的最小的2的次幂
    
    // 这里是指, 如果构造时指定了initialCapacity, 则用threshold作为table的实际大小
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    
    // 如果构造时没有指定initialCapacity, 则用默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // 计算指定了initialCapacity情况下的新的 threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    
    //从以上操作我们知道, 初始化HashMap时, 
    //如果构造函数没有指定initialCapacity, 则table大小为16
    //如果构造函数指定了initialCapacity, 则table大小为threshold, 即大于指定initialCapacity的最小的2的整数次幂
    
    
    // 从下面开始, 初始化table或者扩容, 实际上都是通过新建一个table来完成的
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 下面这段就是把原来table里面的值全部搬到新的table里面
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 这里注意, table中存放的只是Node的引用, 这里将oldTab[j]=null只是清除旧表的引用, 但是真正的node节点还在, 只是现在由e指向它
                oldTab[j] = null;
                
                // 如果该存储桶里面只有一个bin, 就直接将它放到新表的目标位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                
                // 如果该存储桶里面存的是红黑树, 则拆分树
                else if (e instanceof TreeNode)
                    //红黑树的部分以后有机会再讲吧
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                
                // 下面这段代码很精妙, 我们单独分一段详细来讲
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize时的链表拆分

下面我们单独来看看这段设计的很精妙的代码

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

首先我们看源码时要抓住一个大框架，不要被它复杂的流程吓住，我们一段一段来看：

第一段

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

上面这段定义了四个Node的引用，从变量命名上，我们初步猜测，这里定义了两个链表，我们把它称为lo链表和hi链表,loHead和loTail分别指向lo链表的头节点和尾节点,hiHead和hiTail以此类推。

第二段

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

上面这段是一个do-while循环，我们先从中提取出主要框架:

do {
    next = e.next;
    ...
} while ((e = next) != null);

从上面的框架上来看，就是在按顺序遍历该存储桶位置上的链表中的节点。
我们再看if-else语句的内容：

// 插入lo链表
if (loTail == null)
    loHead = e;
else
    loTail.next = e;
loTail = e;

// 插入hi链表
if (hiTail == null)
    hiHead = e;
else
    hiTail.next = e;
hiTail = e;

上面结构类似的两段看上去就是一个将节点e插入链表的动作。

最后在加上if块，则上面这段的目的就很清晰了：

我们首先准备了两个链表lo和hi,然后我们顺序遍历该存储桶上的链表的每个节点，如果(e.hash & oldCap==0)，我们就将节点放入lo链表，否则，放入hi链表

第三段

第二段弄明白之后，我们再来看第三段:

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

这一段看上去就很简单了：

如果lo链表非空，我们就把整个lo链表放到新table的j位置上
如果hi链表非空，我们就把整个hi链表放到新table的j+oldCap位置上

综上我们知道，这段代码的意义就是将原来的链表拆分成两个链表，并将这两个链表分别放到新的table的j位置和j+oldCap上，j位置就是原链表在原table中的位置，拆分的标志就是：

(e.hash & oldCap) ==0

看下图，可以帮助大家理解：

image.png

resize总结

1.resize发生在table初始化, 或者table中的节点数超过threshold值的时候, threshold的值一般为负载因子乘以容量大小.
2.每次扩容都会新建一个table, 新建的table的大小为原大小的2倍.
3.扩容时,会将原table中的节点re-hash到新的table中, 但节点在新旧table中的位置存在一定联系: 要么下标相同, 要么相差一个oldCap(原table的大小).

put方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
    /*final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) */
}

可以看到，put方法是有返回值的，这里调用了putVal方法，这个方法很重要，我们将通过代码注释的方式进行说明。

在这之前我们先看该方法的参数:

• hash
  由上面的调用可知，该值为hash(key)，是key的hash值。

• key,value
  待存储的键值对

• onlyIfAbsent
  这个参数用于决定待存储的key已经存在的情况下,要不要用新值覆盖原有的value, 如果为true, 则保留原有值, false 则覆盖原有值, 从上面的调用看, 该值为false, 说明当key值已经存在时, 会直接覆盖原有值。

• evict
  该参数用来区分当前是否是构造模式, 我们在讲解构造函数的时候曾经提到，HashMap的第四个构造函数可以通过已经存在的Map初始化一个HashMap, 如果为 false, 说明在构造模式下, 这里我们是用在put函数而不是构造函数里面, 所以为true。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 首先判断table是否是空的
    // 我们知道, HashMap的三个构造函数中, 都不会初始Table, 因此第一次put值时, table一定是空的, 需要初始化
    // table的初始化用到了resize函数, 这个我们上一篇文章已经讲过了
    // 由此可见table的初始化是延迟到put操作中的
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
    // 这里利用 `(n-1) & hash` 方法计算 key 所对应的下标
    // 如果key所对应的桶里面没有值, 我们就新建一个Node放入桶里面
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // 到这里说明目标位置桶里已经有东西了
    else {
        Node<K,V> e; K k;
        // 这里先判断当前待存储的key值和已经存在的key值是否相等
        // key值相等必须满足两个条件
        //    1. hash值相同
        //    2. 两者 `==` 或者 `equals` 等
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // key已经存在的情况下, e保存原有的键值对
        
        // 到这里说明要保存的桶已经被占用, 且被占用的位置存放的key与待存储的key值不一致
        
        // 前面已经说过, 当链表长度超过8时, 会用红黑树存储, 这里就是判断存储桶中放的是链表还是红黑树
        else if (p instanceof TreeNode)
            // 红黑树的部分以后有机会再说吧
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        //到这里说明是链表存储, 我们需要顺序遍历链表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 如果已经找到了链表的尾节点了,还没有找到目标key, 则说明目标key不存在，那我们就新建一个节点, 把它接在尾节点的后面
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果链表的长度达到了8个, 就将链表转换成红黑数以提升查找性能
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在链表中找到了目标key则直接退出
                // 退出时e保存的是目标key的键值对
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 到这里说明要么待存储的key存在, e保存已经存在的值
        // 要么待存储的key不存在, 则已经新建了Node将key值插入, e的值为Null
        
        // 如果待存储的key值已经存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            
            // 前面已经解释过, onlyIfAbsent的意思
            // 这里是说旧值存在或者旧值为null的情况下, 用新值覆盖旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); //这个函数只在LinkedHashMap中用到, 这里是空函数
            // 返回旧值
            return oldValue;
        }
    }
    
    // 到这里说明table中不存在待存储的key, 并且我们已经将新的key插入进数组了
    
    ++modCount; // 这个暂时用不到
    
    // 因为又插入了新值, 所以我们得把数组大小加1, 并判断是否需要重新扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); //这个函数只在LinkedHashMap中用到, 这里是空函数
    return null;
}

put方法总结

1.在put之前会检查table是否为空，说明table真正的初始化并不是发生在构造函数中， 而是发生在第一次put的时候。
2.查找当前key是否存在的条件是p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
3.如果插入的key值不存在，则值会插入到链表的末尾。
4.每次插入操作结束后，都会检查当前table节点数是否大于threshold, 若超过，则扩容。
5.当链表长度超过TREEIFY_THRESHOLD（默认是8）个时，会将链表转换成红黑树以提升查找性能。