HashMap底层实现原理

HashMap底层实现采用了哈希表，这是一种非常重要的数据结构，对于理解很多技术都非常有帮助(比如：redis数据库的核心技术和HashMap一样)。

数据结构中由数组和链表来实现对数据的存储，他们各有不同的特点。

(1) 数组：占用空间连续。 寻址容易，查询速度快。但增加和删除效率非常低。

(2) 链表：占用空间不连续。 寻址困难，查询速度慢。但增加和删除效率非常高。

哈希表的本质就是“数组+链表”，结合了数组和链表的优点(即查询快，增删效率高)。

HashMap基本结构

HashMap源码有如下两个核心内容：

public class HashMap<K,V> extends AbstractMap<K,V> 
   implements Map<K,V>, Cloneable, Serializable {
    /**
     * The default initial capacity - MUST be a power of two.
     * 核心数组默认初始化的大小为16（数组大小必须为2的整数幂）。
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The load factor used when none specified in constructor.、
     * 负载因子（核心数组被占用超过0.75则自动开始扩容）。
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 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.)
     * 核心数组（根据需要可以扩容）。数组长度必须始终为2的整数幂。
     */
    transient Node<K,V>[] table;
    //以下代码省略
}

其中的Node<K,V>[] table 就是HashMap的核心数组结构，也称之为“位桶数组”。Node<K,V>源码如下：

static 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;
    }
    //以下代码省略
}

一个Node<K,V>对象存储了：

(1)key：键对象 value：值对象

(2)next：下一个节点

(3)hash：键对象的hash值

每一个Node<K,V>对象都是一个单向链表结构，如下表示一个Node<K,V>对象的典型示意：

如下为Node<K,V>[]数组的结构(也是HashMap的结构)：

存储数据过程put(key,value)

HashMap存储数据的核心是如何产生hash值，该值用来对应数组的存储位置。

我们的目的是将”key-value两个对象”成对存放到HashMap的Node<K,V>[]数组中。步骤如下：

(1) 获得key对象的hashcode

​ 首先调用key对象的hashcode()方法，获得hashcode。

(2) 根据hashcode计算出hash值(要求在[0, 数组长度-1]区间)

​ hashcode是一个整数，需要将它转化成[0, 数组长度-1]的范围。我们要求转化后的hash值尽量均匀地分布在[0,数组长度-1]这个区间，减少“hash冲突”。

​ i. 一种极端简单和低下的算法是：

​ hash值 = hashcode/hashcode;

​ 也就是说hash值总是1。意味着键值对对象都会存储到数组索引1位置，这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”，HashMap也退化成了一个“链表”。

​ ii. 一种简单和常用的算法是(相除取余算法)：

​ hash值 = hashcode%数组长度

这种算法可以让hash值均匀地分布在[0,数组长度-1]的区间。 早期的HashTable就是采用这种算法。但是，这种算法由于使用了“除法”，效率低下。JDK后来改进了算法。首先约定数组长度必须为2的整数幂，这样采用位运算即可实现取余的效果：hash值 = hashcode&(数组长度-1)。

​ iii. 如下为自己测试简单的hash算法：

public class Test {
    public static void main(String[] args) {
        int h = 25760399;
        int length = 16;//length为2的整数次幂,则h&(length-1)相当于对length取模
        System.out.println(myHash(h, length));
    }
    /**
     * @param h  任意整数
     * @param length 长度必须为2的整数幂
     * @return
     */
    public static int myHash(int h,int length){
        System.out.println(h&(length-1));
        //length为2的整数幂情况下，和取余的值一样
        System.out.println(h%length);//取余数
        return h&(length-1);
    }
}

运行如上程序，就能发现直接取余(h%length)和位运算(h&(length-1))结果是一致的。事实上，为了获得更好的散列效果，JDK对hashcode进行了两次散列处理(核心目标就是为了分布更散更均匀)。

(3) 生成Node<K,V>对象

​ 如上所述，一个Node<K,V>对象包含4部分：key对象、value对象、hash值、指向下一个Node<K,V>对象的引用。我们现在算出了hash值。下一个Node<K,V>对象的引用为null。

(4) 将Node<K,V>对象放到table数组中

​ 如果本Node<K,V>对象对应的数组索引位置还没有放Node<K,V>对象，则直接将Node<K,V>对象存储进数组;如果对应索引位置已经有Node<K,V>对象，则将已有Node<K,V>对象的next指向本Node<K,V>对象，形成链表。

总结如上过程

当添加一个元素(key-value)时，首先计算key的hash值，以此确定插入数组中的位置，但可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，就形成了链表，同一个链表上的hash值是相同的，所以说数组存放的是链表。 JDK8中，当链表长度大于8时，链表就转换为红黑树，大大提高了查找的效率。

取数据过程get(key)

我们需要通过key对象获得“键值对”对象，进而返回value对象。步骤如下：

(1) 获得key的hashcode，通过hash()散列算法得到hash值，进而定位到数组的位置。

(2) 在链表上挨个比较key对象。 调用equals()方法，将key对象和链表上所有节点的key对象进行比较，直到碰到返回true的节点对象为止。

(3) 返回equals()为true的节点对象的value对象。

明白了存取数据的过程，下面再看下hashcode()和equals方法的关系：

Java中规定，两个内容相同(equals()为true)的对象必须具有相等的hashcode。因为如果equals()为true而两个对象的hashcode不同，那在整个存储过程中就发生了悖论。

扩容问题

HashMap的位桶数组，初始大小为16。实际使用时大小是可变的。如果位桶数组中的元素达到(0.75*数组 length)， 则重新调整数组大小变为原来2倍大小。

扩容很耗时，扩容的本质是定义新的更大的数组，并将旧数组内容挨个拷贝到新数组中。

JDK8将链表在大于8情况下变为红黑二叉树

JDK8中，HashMap在存储一个元素时，当对应链表长度大于8时，链表就转换为红黑树，这样又大大提高了查找的效率。