HashMap源码解析

源码解读

1、概述：是Map接口的非同步实现，允许使用null值和null健，对象是无序排列的这点和list接口相反。HashMap中有且只有一个key为null(key不能重复)。HashMap用到了几个类？Entry，keySet，entrySet，HashIterator(keyIterator和valueIterator都是继承了这个类)。Hashmap1.8用到了红黑树，当数组一个位置的链表长度大于8，就由链表变为红黑树

2、数据结构：java编程语言中最基本的结构是两种，数组和模拟指针(引用)，所有的数据结构都可以用这两个基本结构来构造，HashMap是一个链表散列的数据结构，即数组和链表的结合体。HashMap底层是一个数组，数组中每一项是个链表。当新建HashMap时，就会初始化一个数组

源码如上：可以看出，Entry就是数组中的元素，每个Map.Entry就是一个key-value对，它持有指向下一个元素的引用，这就构成了链表。 

3、HashMap的存储实现：

如果key是null的话，则把该entry放到table[0]中，如果找到了key为null的entry，则覆盖，没找到，则把entry加到链表的表头。

我们往HashMap中put元素的时候，先根据key的hashcode重新计算hash值，根据hash值得到这个元素在数组中的位置(下标)，如果数组该位置上已经存放有其他元素，那么在这个位置上的元素将以链表的形式存放，新加入的放在链表头，最先加入的放在链表尾。如果数组该位置没有元素，就直接把该元素放在数组中的该位置上。addEntry根据计算出的hash值，将k-v对放在数组table的i索引处，addEntry是HashMap提供的一个包访问权限方法。代码如下

当系统决定存储HashMap中的k-v对时，没有考虑Entry中的value，仅仅根据key来计算并决定每个Entry的存储位置，我们完全可以把Map集合中的value当成key的附属，当系统决定了key的存储位置之后，value随之保存在那里即可。

 hash(int h)方法根据key的hashcode重新计算一次散列。hashcode()函数返回int型散列值，int范围-2^31~2^31-1(-2147483648-2147483647)，加起来有40亿个值，如果直接拿散列值为下标访问HashMap主数组，40亿长度的数组内存放不下。所以这个散列值不能直接用。而要如下处理

这样处理之后，达到的效果如下：

右移16位，正好是32bit的一半，自己的高半区和低半区异或，就是混合原始hashcode的高低位，加大低位随机性。

在HashMap中要找到某个元素，需要根据key的hash值求得对应数组中的位置。Hash算法就是计算这个位置。我们希望HashMap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的而不用再去遍历链表，这样就大大优化了查询的效率。对于给定的对象，只要他们的hashCode()返回值相同，那么程序调用hash(int h)方法锁计算得到的hash码总是相同的。在HashMap中，调用indexFor(int h, int length)计算该对象应该保存在table数组的哪个索引处，indexFor()如下所示：

这个方法很巧妙，用h&(table.length-1)来得到该对象的保存位，而HashMap底层数组长度总是2的n次方，这是HashMap在速度上的优化。在HashMap构造器中有如下代码

这段代码保证初始化时HashMap的容量是2的n次方，即底层数组的长度是2的n次方。h&(length-1)相当于对length取摸，也就是h%length，&运算的效率更高。假设数组长度分别是15和16，hash码分别是8和9，&运算后结果如下

当数组长度为15，8和9产生了相同的结果，也就是会定位到数组中同一个位置上，会产生碰撞，两者形成链表，查询时候要遍历这个链表这就降低了查询效率。数组长度为15时，hash会与15-1(1110)&运算，最后一位永远是0，像0001,0011等位置永远不能放元素，浪费空间。当数组长度是16，2^n-1每个位上都是1，所以和hash&时得到的和原hash相同，不同key得到相同index的几率较小，数据在数组上分布更均匀。查询效率更高。根据put方法源码，如果两个Entry的key的hashCode()返回值相同，则它们的存储位置相同。如果两个Entry的value通过equals比较返回true，新Entry的value会覆盖原有Entry的value。如果两个Entry的key通过equals比较返回false，新添加的Entry会与原有Entry形成Entry链，而且新添加的Entry位于Entry链的头部。

4、HashMap的读取实现

 首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

 5、简单归纳：HashMap在底层把k-v当成一个整体处理，这个整体就是一个Entry对象。HashMap底层采用一个Entry[]数组保存所有的k-v对，当需要存储一个Entry对象时，根据hash算法决定其在数组中的位置，再根据equals方法决定其在该数组位置上的存储位置。当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

 6、HashMap的resize:

当HashMap中元素越来越多，hash冲突的几率越来越高，为了提高查询效率，就要对HashMap的数组扩容，原数组中的数据必须重新计算其在新数组中的位置，并放进去。这个操作很消耗性能。

什么时候resize呢？当HashMap中键值对数量超过数组大小*loadFactor时，就会扩容。loadFactor默认是0.75，默认情况下，数组大小16，那么当HashMap中元素超过16*0.75=12时，就把数组大小扩展为32。如果已知元素个数，那么预设元素个数以提高HashMap的性能。

 7、HashMap性能参数：

HashMap()构建一个初始容量16，负载因子0.75的HashMap

HashMap(int initialCapacity)，负载因子0.75的HashMap，如果initialCapacity为6，则初始容量是8

HashMap(int initialCapacity,float loadFactor)自己定义两者大小。

loadFactor衡量的是散列表空间使用程度，越大则HashMap装填程度越高，空间利用充分然而查找效率低。如果负载因子小，HashMap会过于稀疏。

8、Fail-Fast机制：

  HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map那么将抛出ConcurrentModificationException，这就是所谓的Fail-Fast策略。在源码中声明了modCount变量，用volatile修饰，代表多线程环境下访问modCount时，只要modCount改变了，其他线程将读到最新的值。使用Iterator开始迭代时，会把modCount赋值给expectedModCount,在迭代过程中通过比较两者是否相等来判断HashMap是否在内部被其他线程修改。如果不一样说明有其他线程在修改HashMap的结构。HashMap的put,remove操作都有modCount++的计算。因此面对并发的修改，迭代器很快就会完全失败。在初始化迭代器的时候，会把modCount赋值给expectedModCount