HashMap内部数据结构
HashMap内部采用数组和链表结合的方式来存取数据（见下图）。这种方式有什么好处呢? 我们知道，数组操作对于检索是O(1)的，能够很快的根据数组的下标定位对象，但是插入和删除操作不高，会引起后续节点的移动，而链表的优势是：插入和删除非常的迅速，只需要重设相应的next指针就可以了。因此HashMap是结合两者优势，这是一种折中的方案。（在java8中引入了红黑树，是对性能的更进一步优化）
放到HashMap的key-value对是如何保存的？
HashMap类内部有一个静态内部类Entry，它继承自Map.Entry接口（不要混淆了HashMap.Entry和Map.Entry）：
static class Entry <K , V> implements Map .Entry < K, V > { ... }
再看看HashMap内部有这么一个Entry数组：transient Entry[] table; 当我们向HashMap中put一个key-value时，HashMap会将它转换为Entry对象并存放到Entry数组中的某个位置（由hash函数计算hash值后用数组长度取模来决定存放位置的）。
HashMap内部几个重要的方法解析：
首先欢迎hash(int h)方法闪亮登场....
各位码农好，我是HashMap内部的hash方法，简单介绍一下自己：我是根据key.hashCode值进行重新计算的一个方法，因为我不是很相信他们，我相信我能做得更好：
static int hash( int h ) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ ( h >>> 12) ;
return h ^ (h >>> 7 ) ^ (h >>> 4);
}
说明：该hash算法的内部实现乍一看的确很晦涩难懂。参数值h是key.hashCode()，很明显，该方法的意图就是根据key.hasCode()的值进行重新计算。为什么要这么做呢？因为HashMap要求key的hashCode值分布越均匀性能就越好(见上图，若hash函数计算出的hash值越均匀，链表的长度也就越均衡，就不会造成有的链表长度很短，而有的链表长度特别长的情况，我们知道，链表长度越长，检索效率就越慢）。而put到HashMap作为key的对象的hashCode可能五花八门，有的对象的hashCode可能还进行过重写，这可能导致put到HashMap中的key的hashCode值分布可能会不均衡，所以HashMap就利用这样一个算法对hashCode进行重新计算，以期望得到更加分布均衡的hashCode值。
（上述关于均衡的hashCode值原理待详细讲解）
再欢迎我们第二个嘉宾indexFor方法：
大家好，我也简单介绍一下自己，我是根据hash值和Entry[]的长度进行取模运算的，是不是很奇怪我为什么长成这个样子，其实我也就是伪装很好的”取模“运算而已。我觉得这样比较酷一点，而且我办事效率比其他那些取模方法要快的多。
static int indexFor( int h , int length) {
return h & (length - 1 );
}
说明：在计算机数学里有这么一个法则： 当SIZE满足大小是2的幂的时候，X % SIZE（取模操作）和 X & (SIZE-1）是等价的，不信？自己动手演算一下？因此我们知道了为什么HashMap要求我们提供的capacity大小是2的幂的原因了吧？用户提供给HashMap构造函数的capacity值可能不是2的幂，所以hashmap内部进行了验证并将其重设为最接近指定capacity值的2的幂的那个值：
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
介绍了前两个重要方法，下面欢迎我们熟悉的put方法出场：
public V put ( K key , V value ) {
if ( key == null)
return putForNullKey ( value) ;
int hash = hash (key . hashCode()) ;
int i = indexFor (hash , table . length) ;
for ( Entry <K , V> e = table [ i ]; e != null ; e = e. next ) {
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 ;
}
}
modCount ++;
addEntry (hash , key , value , i ) ;
return null ;
}
说明：有了对hash和indexFor方法以及对前面介绍的HashMap内部数据结构的知识，理解put操作就变得非常容易了，首先判断key是不是null（HashMap是允许用null作为key），如果是就将它插入到table[0]处，否则，就先以key.hashCode()为基础调用HashMap#hash方法得到一个分布更好的hash值，然后对该值取模（indexFor）得到相应的数组位，然后，判断该数组位之前有没有存放过Entry对象，如果没有就创建一个Entry对象插入到该位置，如果该位置已经有Entry对象了，那么就依次从链表的头部开始查找有没有相同key的Entry对象，如果匹配到，就替换匹配项的值，否则，就将这个Entry元素插入到链表的最后面。理解了put操作，get操作就不再赘述了。
HashMap对容量的动态扩容
HashMap默认容量是16（也就是初始数组（也叫桶，bucket）大小是16），内部有一个变量DEFAULT_LOAD_FACTOR（负载因子，默认0.75）就是用来指示自动扩展大小的阀值，也就是说，当我们往数组中添加的元素个数大于capacity * 0.75（3/4)的时候，HashMap会自动调用resize方法调整bucket的大小。调整大小的过程就是新建一个更大的Entry数组，然后将之前添加过的Entry对象全部复制过去，由于每个Entry对象都保存有之前计算好的hash值，当数组容量扩大时再次取模（hash % length）得到的位置就不同了，所以原本在同一个链表中的元素就可能分开了，调整容量也就是为了实现将链表长度缩短这一目的的。具体复制操作的实现见transfer方法，这也很容易理解。
关于ConcurrentModificationException
HashMap类是非线程安全的，当一个线程正在对HashMap对象进行迭代操作，另一个线程对HashMap对象进行了更改，或者在单个线程下，用户在迭代的循环体中不正确的更改了HashMap对象元素的大小，都经常会抛出ConcurrentModificationException异常，这就是我们说的fail-fast，迭代时，其内部处理逻辑是这样的，HashMap内部有一个用以指示修改次数的计数器（modCount），当每次进行put，remove等操作时，都会引起计数器发生变化，每次迭代开始之前会取出modCount值存放到另一个exceptedModCount局部变量中，然后每个迭代过程都会检查该exceptedModCount是否和当前modCount相等，如果不等就会抛出ConcurrentModificationException异常，因此，在有多线程并发访问的情况下，建议使用ConcurrentHashMap这个线程安全类来替代HashMap的使用（题外：使用线程安全类就能确保对它的所有操作都是线程安全的吗？答案是否定的。这属于多线程原子操作等考虑的范围，不在本章详细讨论）。