HashMap源码分析

数据结构

• JDK1.7：数组+链表
• JDK1.8：hash表=数组+链表+红黑树

什么是哈希表？

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

HashMap添加元素分析

在HashMap中，当添加元素时，会通过哈希值和数组的长度来计算得出一个计算下标，用它来准确的定位该元素应该put的位置。通常，我们为了使元素分布均匀会使用取模运算，用一个值去模上总长度，例如：

index = hashCode % arr.length   //实际并非这样，后面讲解

计算出index后，就会将该元素添加进去，理想状态下是将每个值都均匀的添加到数组中，但问题是不可能达到这样的理想状态，这时候就会产生哈希冲突。例如：大狂神通过计算添加到了数组3号位置；

但是，此时佩雨这个元素通过计算产生了一个与大狂神相同的索引位置，这是就产生了哈希冲突；于是此时，就产生了第二种数据结构——链表，冲突的元素会在该索引处以链表的形式保存；

了解：解决Hash冲突四个方法

1、开放定址法（以冲突的下标为基础再次记算hash，直到不冲突）

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。

2、重Hash法（多个hash函数，一个hash函数计算出来的索引冲突了就换一个函数记算，直到不冲突）

这种方法是同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

3、链地址法

这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

4、建立公共溢出区

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

红黑树

之前的情况，当链表的长度过长时，其固有弊端就显现出来了，即查询效率较低，链表查询的时间复杂度是O(n),数组的查询时间复杂度是O(1)，链表查询效率非常低，所以就引出了第三种数据结构——红黑树，链表长度>=8时链表转为红黑树，红黑树是一棵接近于平衡的二叉树，其查询时间复杂度为O(logn)，远远比链表的查询效率高。

思考：那为什么要在链表长度大于等于8的时候变成红黑树呢？

如果链表的长度没有达到这个长度的话，因为红黑树它自身的这种维护，插入的这种维护的开销也是非常大的，因为每次一去插入一个元素的时候很有可能会破坏掉他的平衡。也就是说hashmap的 put 操作非常多的时候，极有可能会影响插入的性能，因为插入一个元素的话，极有可能会打破它原有的平衡，那么每时每刻它都需要再恢复平衡（也就是红黑树的再平衡，需要左旋右旋，以及重新着色），就非常影响性能；

为什么数组的长度必须是2的指数次幂

hashmap中数组的初始长度（如果不传参，默认为16）

/**
 * The default initial capacity - MUST be a power of two.
 * 秦疆翻译：默认初始容量-必须是2的幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

**最大容量：**如果具有参数的任一构造函数隐式指定，则使用最大容量。必须是2的幂且 <= 1 << 30。

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

如果我们传入的初始容量不是2的指数次幂，他就会将这个数改成大于该数且最接近这个数的2的指数次幂

比如以下这段代码：

HashMap<Object, Object> map = new HashMap<>(13);
map.put("秦疆","Java");

传入的初始容量是13，他就会将13转换为大于13且最接近13的2的指数次幂的一个数：

13----->16
再比如：
7 ----->8
5 ----->8
3 ----->4

源码分析

当我们使用构造方法传进来一个初始容量的值initialCapacity，默认会传入一个加载因子0.75；

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 */
public HashMap(int initialCapacity) {
    //默认的加载因子仍是0.75，其通过this关键字调用了本类的另外一个重载方法
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

继续追踪分析代码：

public HashMap(int initialCapacity, float loadFactor) {
    //1.这里会先判断传来的初始容量是不是小于零的数字。如果是直接抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    
    //2.再判断是不是超过了hash定义的最大容量2的30次幂，如果超过了则让其等于最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    
    //3.再接着判断传来的加载因子,如果小于零或者不是一个数字直接抛出异常。
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    this.loadFactor = loadFactor;
    
    //4.然后调用了一个tableSizeFor()方法去处理传进来的初始容量
    this.threshold = tableSizeFor(initialCapacity);
}

继续追踪分析代码：进入到tableSizeFor()方法 ： 这个处理初始容量的方法；

/**
 * Returns a power of two size for the given target capacity.
 * 它的作用是返回一个大于输入参数,且最接近的2的整数次幂的数
 */
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;
}
/* 解释下这个算法 ： 需要先了解： 右移 和 位或
这里使用的是位运算：假设n的二进01xxx…xxx；
先对n右移1位则结果为：001xx…xxx，再进行位或结果为：011xx…xxx；
再对n右移2位则结果为：00011…xxx，再进行位或结果为：01111…xxx；
此时前面已经有四个1了，再右移4位，然后进行位或可得8个1；
同理，有8个1，再右移8位，然后进行位或肯定会让后八位也为1；
综上可得，该算法让最高位的1后面的位全变为1。最后再让结果n+1，即得到了2的整数次幂的值了。
而最开始：cap-1再赋值给n的目的是：让找到的目标值 >= 原值
*/

解释：HashMap为了实现存取高效，要尽量减少碰撞，就是要尽量做到：把数据分配均匀，保证每个链表长度大致相同，我们就需要一个算法来实现：将存入的数据保存到那个链表中的算法；而这个算法实际就是取模：hash%length

但是，大家都知道这种运算不如位移运算快。因此，源码中做了优化 hash&(length-1)。

也就是说 hash%length==hash&(length-1)

那为什么是2的n次方呢？

因为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”，结果才为“1”，否则为0

那么为什么要把初始容量转成2的指数次幂呢？不转成2的指数次幂也是可以存储的啊，为什么要转？

首先看HashMap的put方法

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

其中的hash方法用于计算key的哈希值；

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

关于这个Hash的思考

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

hashmap这么做，只是为了降低hash冲突的几率。

打个比方，当我们的length为16的时候，哈希码(字符串“abcabcabcabcabc”的key对应的哈希码) 和 (16-1)进行与操作，对于多个key生成的hashCode，只要哈希码的后4位为0，不论不论高位怎么变化，最终的结果均为0。因为与运算中两位同时为“1”，结果才为“1”，否则为0; 如下：

而加上高16位异或低16位的“扰动函数”后，结果如下

可以看到: 扰动函数优化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0 扰动函数优化后：1955003654 % 16 = 1955003654 & (16 - 1) = 6 很显然，减少了碰撞的几率。

我们一开始提到过，添加元素时索引的下标可以通过取模运算获得，但是我们知道计算机的运行效率：加法(减法)>乘法>除法>取模，取模的效率是最低的。所以我们要在HashMap中避免频繁的取模运算，又因为在我们HashMap中他要通过取模去定位我们的索引，并且HashMap是在不停的扩容，数组一旦达到容量的阈值的时候就需要对数组进行扩容。那么扩容就意味着要进行数组的移动，数组一旦移动，每移动一次就要重回记算索引，这个过程中牵扯大量元素的迁移，就会大大影响效率。那么如果说我们直接使用与运算，这个效率是远远高于取模运算的！

putVal方法，它是实现具体的put操作的方法

再来看putVal方法，它是实现具体的put操作的方法,来看一下源码；

//实现put操作
//返回值: @return 之前的value
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //1. 如果当前table为空，新建默认大小的table
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //2. 获取当前key对应的节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        //3. 如果不存在，新建节点
        tab[i] = newNode(hash, key, value, null);
    else {
        //4. 存在节点
        Node<K,V> e; K k;
        //5. key的hash相同，key的引用相同或者key equals，则覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //6. 如果当前节点是一个红黑树树节点，则添加树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //7. 不是红黑树节点，也不是相同节点，则表示为链表结构
        else {
            for (int binCount = 0; ; ++binCount) {
                //8. 找到最后那个节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //9. 如果链表长度超过8转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //10.如果链表中有相同的节点，则覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //是否替换掉value值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //记录修改次数
    ++modCount;
    //是否超过容量，超过需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

由以上源码第2步，tab[i = (n - 1) & hash]中tab就是HashMap的实体数组，其下边通过i = (n - 1) & hash来获取（n表示数组长度，hash表示hashCode值），但是这必须保证数组长度为2的整数次幂，我们继续往下看

现在我们可以使用与运算(n-1) & hash取代取模运算hash%length，因为这两种方式记算出来的结果是一致的（n就是length），也就是(length-1)&hash = hash%length，例如：假设数组长度为4，哈希值为10

(n-1) & hash = (4-1) & 10 = 00000011 & 00001010 = 00000010 = 2
hash % length = 10 % 4 = 2

但是当数组的长=长度不为2的指数次幂时，两种方式计算的结果不一样，即（length-1)&hash ≠ hash&length

例如：再假设数组长度为5，哈希值10

(n-1) & hash = (5-1) & 10 = 00000100 & 00001010 = 00000000 = 0
hash % length = 10 % 5 = 2

显然，当数组长度不为2的整数次幂时二者是不相等的！

但最重要的一点，是要保证定位出来的值是在数组的长度之内的，不能超出数组长度，并且减少哈希碰撞，让每个位都可能被取到，我们来看下面例子：

例如：(16-1) & hash
二进制的15：  0000 0000 0000 1111
hash(随机)   1101 0111 1011 0000
hash(随机)   1101 0111 1011 1111
结果         0000 0000 0000 0001 ~ 0000 0000 0000 1111
即得出的索引下标只能在0~15之间，保证了所有索引都在数组长度的范围内而不会越界
并且由于2的指数次幂-1都是...1111的形式的，即最后一位是1
这样，由于hash是随机的，进行与运算后每一位都是能取到的
========================================================================
反例：(7-1) & hash
二进制6： 0000 0000 0000 0110
hash     1011 1001 0101 0000
hash     1001 0001 0000 1111
结果      0000 0000 0000 0000 ~ 0000 0000 0000 0110
即得出的索引范围在0~6，虽然不会越界，但最后一位是0
即现在无论hash为何值，0001，0011，0101这几个值是不可能取到的
这就加剧了hash碰撞，并且浪费了大量数组空间，显然是我们不想看到的

总结：首先使用位运算来加快计算的效率，而要使用位运算，就需要数组-1然后与hash值保证其在数组范围内，只有当数组长度为2的指数次幂时，其计算得出的值才能和取模算法的值相等，并且保证能取到数组的每一位，减少哈希碰撞，不浪费大量的数组资源！