JDK1.8的HashMap源码分析

JDK1.8之前的HashMap

在JDK1.8之前，HashMap通过散列表(哈希表)实现，并且散列表冲突解决方案是链地址法(拉链法)，也可理解为数组+链表实现。

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

什么是散列表？
一块连续的存储空间中，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。
重温数据结构_散列表/哈希表的查找

向HashMap存储元素：
向HashMap中存储某元素时候，首先hash算法根据元素的key值得到一个hash值，这个hash值就可以确定元素在数组中的位置。如果此位置没有元素，直接存；如果已经存在元素，就要与它们的key进行比较，有以下两种情况：1.key相同的，覆盖旧值；2.key都不同，形成一个以新元素为头部的链表。

从HashMap获取元素：
先根据key的hash算法得到hash值，找到该元素在数组中的位置；再通过key的equals方法，在链表中找到对应的元素，也就找到了key对应的value。

HashMap结构图

JDK1.8的HashMap

HashMap通过数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，并且再次之后都用红黑树来存储冲突的元素。

为什么JDK1.8HashMap要做如此改变？
我们都知道在链表中查找节点时，会花费O（n）的查找时间。为了防止拉链过长，导致严重影响HashMap的性能，当链表长度超过阈值（8）时，不再采用单链表形式存储，而是采用红黑树存储，利用红黑树快速增删改查的特点提高HashMap的性能。

jdk1.8 hashmap结构图

JDK1.8 HashMap源码分析

重要的字段

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K, V>[] table;

    /**
     * The number of key-value mappings contained in this map.
     * 包含在map中键-值对的数量
     */
    transient int size;

    /**
     * hashmap被结构化改变的次数
     */
    transient int modCount;

    /**
     * The next size value at which to resize (capacity * load factor).
     * 扩容的阈值，当size大于这个值时，table数组进行扩容
     */
    int threshold;

    /**
     * The load factor for the hash table.
     * 
     */
    float loadFactor;

对这些重要字段的解释：

• table：Node[] table的初始化长度length默认值是16；
• loadFactor ：负载因子默认值是0.75；
• threshold ：是HashMap所能容纳的最大数量的Node(键值对)个数。

负载因子的定义公式：threshold = length * loadFactor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
当size超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

• size：包含在map中键-值对的实际数量。注意和table的长度length、容纳最大键值对数量threshold的区别。
• modCount：主要用来记录HashMap内部结构发生变化的次数。需要注意的是内部结构发生变化真正意义是元素的key从来没有被put过。

如何确定key对应哈希桶数组索引位置？
通过这个Java方法运算来获取hash码值：

    static final int hash(Object key) {
        int h;
        //取key的hashCode值、高位运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

通过hash方法得到的hash码值，还不是数组的下标编号，还差一步，这一步就是hash码值对数组长度进行取模运算，具体代码如下图红框。

下图是得到key在数组具体位置索引号的过程：

图来源于网络

### 重要方法分析
#### 静态内部类Node
Node是HashMap的一个静态内部类，实现了Map.Entry接口，表示一个映射条目或者说是键值对。

static class Node<K,V> implements Map.Entry<K,V> {
//根据hash方法计算出来的值，作为定位数组位置的索引
final int hash;
final K key;
V value;
Node<K,V> next;//该Node指向的下一个Node

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    ...

}

HashMap的put方法实现

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }