java.util.HashMap底层实现原理

解决哈希冲突的方案有多种：

1. 开放定址法：发生冲突，继续寻找下一块未被占用的存储地址；
2. 再散列函数法；
3. 链地址法（HashMap就是采用了链地址法，也就是数组+链表的方式）；

       HashMap的主干是一个Entry数组（源码中叫做table）。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。

HashMap对象中其他几个重要字段：

// 实际存储key-value键值对的个数
transient int size;

// 阈值，当table（上文中的Entry数组）为空时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为capacity*loadFactroy（capacity即table容量）；HashMap在扩容时需要参考threshold，后面会详细谈到。
int threshold;

// 负载因子，代表了table的填充度有多少，默认是0.75
final int loadFactory;

//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException（foreach时）
transient int modCount;

构造器

       在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组。
       在构造器中对传入的初始容量进行校验，最大不能超过MAXIMUM_CAPACITY = 1<<30(2³⁰)，且数组的长度一定为2的次幂。

int capacity = 1;  
// initialCapacity即为构造器中可以传入的自定义HashMap初始容量参数
while (capacity < initialCapacity)  
  capacity <<= 1;  

       这段代码保证初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方（具体原因后文会有介绍）。

扩容resize()

       当发生哈希冲突并且size大于阈值（threshold=capacity*loadFactory）的时候，需要进行数组扩容（resize），扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去（遍历，重新计算索引位置，将老数组数据复制到新数组中去），扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。如果capacity已经达到最大（2³⁰），则threshold变为Integer.MAX_VALUE。
       如果loadFactory（负载因子）取得太大，threshold与capacity太接近，当容量增大时，冲突会增加，造成同一地址链表过大（当size大于threshold时才扩容）；如果太小，哈希表太稀疏，浪费存储空间。负载因子可以大于1（即threshold大于数组长度，因为是链地址法）。

PUT存入元素

       Put时如果key为null，存储位置为table[0]或table[0]的冲突链上。如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value，如果对应数据不存在，则添加到链表的头上（保证插入O（1））
       put流程：首先判断key是否为null，若为null，则直接调用putForNullKey方法。若不为空则先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，循环遍历链表，比较是否存在相同的key，若存在则覆盖原来key的value，否则将该元素保存在链头（最先保存的元素放在链尾）。若table在该处没有元素，则直接保存。

       最终存储位置的确定流程是这样的：

1. hashCode()

       由 Object 类定义的 hashCode()方法确实会针对不同的对象返回不同的整数。（这一般是通过将该对象的内部地址转换成一个整数来实现的）。
       返回的整数（散列值）是一个int类型，此时如果直接拿该散列值作为下标访问HashMap数组的话，考虑到2进制32位带符号的int值范围从-2147483648到2147483648。前后加起来有40亿的映射空间，只要哈希函数映射得比较松散，一般应用是很难出现碰撞的。
       但问题是一个40亿长度的数组，内存是放不下的。HashMap的初始数组大小才只有16。所以这个散列值是不能直接用的，需要进行一系列的运算。

2. hash() 摘自JKD1.8

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

       上面这段代码称为“扰动函数”（后面会讲到为什么需要这一步）。

3. indexFor()

static int indexFor(int h, int length) {
  return h & (length - 1);
}

       h即为hash()函数的返回值，indexFor()函数就是将散列值和数组长度做了一个“与”操作。
       这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示为00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

       但此时问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，冲突也会很严重。而此时便体现了“扰动函数”（hash()）的作用。

       右移16位，正好是32bit（java中int占4字节，32位）的一半，将自己的高半区和低半区做异或，就是为了混合原始哈希吗的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

GET取出元素

       get方法的实现相对简单，key(hashcode-返回int)-->hash-->indexFor-->最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。（&length-1也将范围较大的hash值缩小到了length内）。

modCount字段

       我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map。

HashMap的存放自定义类时，需要重写自定义类的hashCode()和equals()方法

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  //如果对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
  Object k;
  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
  }
}

       上面的代码摘自Put()方法中，已经找到对应的table[i]后，遍历链表时。其中hash都是经过hashCode()和hash()函数的。

       如果不重写equals()方法，HashMap没有判断两个对象相等的标准。如果不重写hashCode()，将对用object默认的hashCode()方法（根据对象地址生成hashCode），如果new了两个对象，它们的属性均相同，但由于是两个对象，所以object生成的hashCode不同，但在HashMap中这两个key应该当做相同的key，但不重写hashCode()则无法实现。
       Get和put方法通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals()方法却没有重写hashCode()，而恰巧此对象定位到这个数组位置，如果仅仅用equals()判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null（规定，相等的对象，hashcode必须相同）。

多线程同时操作hashmap时

       会产生死循环，如果多个线程同时扩容，产生两个新的table，形成一个闭环。

以上内容基于旧版本的jdk，jdk1.8中对HashMap的优化，请看下篇文章。
JDK1.8中对HashMap的优化

参考文献

http://www.cnblogs.com/chengxiao/p/6059914.html
https://www.zhihu.com/question/20733617
http://blog.csdn.net/richard_jason/article/details/53887222
http://ifeve.com/hashmap-infinite-loop/