HashMap源码解读总结

这篇文章是自己想去了解HashMap(jdk1.8)的原理和数据结构，通过各大博客和书籍整理出来的，所以可能会没有节奏感。

HashMap的定义

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

HashMap()是一个默认的构造器，初始容量16，负载因子为0.75.
HashMap(int initialCapacity)是一个指定初始容量为initialCapacity，负载因子为0.75的空的hashmap。
HashMap(int initialCapacity, float loadFactor)是一个指定初始容量为initialCapacity，负载因子为loadFactor的空的HashMap。

HashMap的特点

HashMap是哈希表(根据键（Key）而直接访问在内存存储位置的数据结构, 也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。)
HashMap不是同步的(即线程不安全的), 如果多个线程同时对一HashMap的集合试图做迭代时有结构的上改变（添加、删除entry，只改变entry的value的值不算结构改变），那么会报ConcurrentModificationException，专业术语叫fail-fast，尽早报错对于多线程程序来说是很有必要的。
不保证其内部元素的顺序，而且随着时间的推移，同一元素的位置也可能改变（resize的情况）
HashMap的key、value都可以为null(null得key存放在table[0])

HashMap的一些属性

    /**
     * HashMap默认的初始化大小 - 大小必须是2的次方.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * HashMap的最大值
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认的负载因子的值
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * table在首次使用时初始化，并根据需要调整大小。分配时，长度始终是2的幂
     */
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * 当前HashMap大小
     */
    transient int size;

    /**
     * fail-fast 机制
     *
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;

    /**
     *  下次扩容的临界值,HashMap大小(size)超过threshold大小, HashMap会自动扩容(capacity * load factor)
     */
    int threshold;

    /**
     * 负载因子
     */
    final float loadFactor;

负载因子: 当负载因子较大时，去给table数组扩容的可能性就会少，所以相对占用内存较少（空间上较少），但是每条entry链上的元素会相对较多，查询的时间也会增长（时间上较多）。反之就是，负载因子较少的时候，给table数组扩容的可能性就高，那么内存空间占用就多，但是entry链上的元素就会相对较少，查出的时间也会减少。所以才有了负载因子是时间和空间上的一种折中的说法。
Entry是HashMap的内部类，它继承了Map中的Entry接口，它定义了键(key)，值(value)，和下一个节点的引用(next)，以及hash值。很明确的可以看出Entry是什么结构，它是单线链表的一个节点。也就是说HashMap的底层结构是一个数组，而数组的元素是一个单向链表。

Entry结构

hash碰撞

至于为什么要这样设计?我们来谈谈hash碰撞

哈希表定义
Hash ，一般翻译做“散列” ，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。
这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH 主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码, 这些编码值叫做sHASH值

上图HashMap里面的bucket出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题(两个不同的key但是hash出来的值是相同的)，通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表。

put函数的实现

对key的hashCode()做hash，然后再计算index
如果没碰撞直接放到bucket里
如果碰撞了，以链表的形式存在buckets后
如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树
如果节点已经存在就替换old value(保证key的唯一性)
如果bucket满了(超过load_factor * capacity)，就要resize

get函数的实现

bucket里的第一个节点，直接命中；
如果有冲突，则通过key.equals(k)去查找对应的entry
- 若为树，则在树中通过key.equals(k)查找，O(logn)
- 若为链表，则在链表中通过key.equals(k)查找，O(n)

一些概念

以Entry[]数组实现的哈希桶数组，用Key的哈希值取模桶数组的大小可得到数组下标。
插入元素时，如果两条Key落在同一个桶（比如哈希值1和17取模16后都属于第一个哈希桶），我们称之为哈希冲突。
JDK的做法是链表法，Entry用一个next属性实现多个Entry以单向链表存放。查找哈希值为17的key时，先定位到哈希桶，然后链表遍历桶里所有元素，逐个比较其Hash值然后key值。
在JDK8里，新增默认为8的阈值，当一个桶里的Entry超过閥值，就不以单向链表而以红黑树来存放以加快Key的查找速度。
当然，最好还是桶里只有一个元素，不用去比较。所以默认当Entry数量达到桶数量的75%时，哈希冲突已比较严重，就会成倍扩容桶数组，并重新分配所有原来的Entry。扩容成本不低，所以也最好有个预估值。
取模用与操作（hash & （arrayLength-1））会比较快，所以数组的大小永远是2的N次方，你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。
iterator（）时顺着哈希桶数组来遍历，看起来是个乱序。

引用: