前言
本文的目的是阅读理解HashMap的源码，作为集合中重要的一个角色，平时用到十分多的一个类，深入理解它，知其所以然很重要。本文基于Jdk1.7，因为Jdk1.8改变了HashMap的数据结构，进行了优化，我们先从基础阅读，之后再阅读理解Jdk1.8的内容
HashMap的特性
1.通过key-value的形式快速的存取元素
2.允许键为Null，但只允许有一个键的值为Null
3.线程不安全
4.底层结构是Hash表，元素是无序的
5.再不考虑Hash冲突的时候，插入和查询的复杂度是可以达到O（1）的
HashMap的数据结构
底层数据结构是一个Hash表，基于数组和链表，数组里面保存着一个单向链表的头节点，单项链表保存着具有相同Hash值的不同元素，再不发生Hash冲突的情况下，链表应该只有一个元素，这是最理想的状态。
链表的数据结构代码
`
static class Entry<K, V> implements Map.Entry<K, V> {final K key;V value;Entry<K, V> next; // 下一个Entry对象的引用int hash; // 其实就是key的hash值 } HashMap的常量结构
// 默认初始化容量 16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // HashMap允许的最大容量 2^30static final int MAXIMUM_CAPACITY = 1 << 30; // 默认的负载率 75%static final float DEFAULT_LOAD_FACTOR = 0.75f; // 空的哈希表static final Entry<?, ?>[] EMPTY_TABLE = {}; // 实际使用的哈希表transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE; // HashMap的大小,即存储的key-value的数量transient int size; // 扩容的阀值，当HashMap的size达到阀值时，就开始扩容 threshold=length*threshold int threshold; // 负载率final float loadFactor; // 修改次数, 用于fail-fast机制transient int modCount; // 替代哈希使用的默认扩容阀值static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; // 随机的哈希种子, 有助于减少发生哈希碰撞的几率transient int hashSeed = 0;HashMap的初始化
HashMap的初始化涉及到上面的多个常量，在了解完常量的作用之后，我们就可以理解HashMap的初始化思想，首先，HashMap并不是通过构造函数来初始化的，构造函数只是初始化HashMap的初始化参数，包括DEFAULT_INITIAL_CAPACITY ，loadFactor等，再初始化参数之后，真正的调用Put方法时，会判断table 是否已经初始化，没有的话再根据参数进行初始化。
put方法的流程我们这边也要先理解：
（1）检查哈希表是否是个空表，如果是空表就调用inflateTable方法进行初始化
（2）判断key是否为null，如果为null，就调用putForNullKey方法, 将key为null的key-value存储在哈希表的第一个位置中
如果key不为null，则调用hash方法计算key的hash值
（3）根据hash值和Entry数组的长度定位到Entry数组的指定槽位
（4）判断Entry数组指定槽位的值e是否为null, 如果e不为null, 则遍历e指向的单链表, 如果传入的key在单链表中已经存在了, 就进行替换操作, 否则就新建一个Entry并添加到单链表的表头位置
（5）如果e为null, 就新建一个Entry并添加到指定槽位
下面是代码：
构造方法
public HashMap(int initialCapacity, float loadFactor) { // 如果初始容量小于0，则抛出异常 if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); } // 如果初始容量大于容量最大值，则使用最大值作为初始容量 if (initialCapacity > MAXIMUM_CAPACITY) { initialCapacity = MAXIMUM_CAPACITY; } // 如果负载率小于等于0或负载率不是浮点数，则抛出异常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) { throw new IllegalArgumentException("Illegal load factor: " + loadFactor); } // 设置负载率 this.loadFactor = loadFactor; // 设置阀值为初始容量 threshold = initialCapacity; // 空实现, 交由子类实现 init();}//初始化数组方法
private void inflateTable(int toSize) { // 寻找大于toSize的,最小的,2的n次方作为新的容量 int capacity = roundUpToPowerOf2(toSize); // 阀值=容量*负载因子, 如果容量*负载因子>最大容量时, 阀值=最大容量 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 按新的容量创建一个新的数组 table = new Entry[capacity]; // 重新初始化hashSeed initHashSeedAsNeeded(capacity);}put方法
public V put(K key, V value) { // 如果哈希表没有初始化就进行初始化 if (table == EMPTY_TABLE) { // 初始化哈希表 inflateTable(threshold); } // 当key为null时，调用putForNullKey方法，保存null于table的第一个位置中，这是HashMap允许为null的原因 if (key == null) { return putForNullKey(value); } // 计算key的hash值 int hash = hash(key); // 根据key的hash值和数组的长度定位到entry数组的指定槽位 int i = indexFor(hash, table.length); // 获取存放位置上的entry，如果该entry不为空，则遍历该entry所在的链表 for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; // 通过key的hashCode和equals方法判断，key是否存在， 如果存在则用新的value取代旧的value，并返回旧的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 修改次数增加1 modCount++; // 如果找不到链表 或者 遍历完链表后，发现key不存在，则创建一个新的Entry，并添加到HashMap中 addEntry(hash, key, value, i); return null;} void addEntry(int hash, K key, V value, int bucketIndex) { //添加key到table[bucketIndex]位置，新的元素总是在table[bucketIndex]的第一个元素，原来的元素后移 Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //判断元素个数是否达到了临界值，若已达到临界值则扩容，table长度翻倍 if (size++ >= threshold) resize(2 * table.length); }HashMap的查
当key值为Null的时候会进行特殊处理，在table[0]的链表上查找Key为null的元素，get的过程是：
（1）计算hash与table.length取模计算index值
（2）遍历table[index]上的链表，直到找到key
void addEntry(int hash, K key, V value, int bucketIndex) {//添加key到table[bucketIndex]位置，新的元素总是在table[bucketIndex]的第一个元素，原来的元素后移Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//判断元素个数是否达到了临界值，若已达到临界值则扩容，table长度翻倍 if (size++ >= threshold) resize(2 * table.length);}#HashMap的删
remove方法同样也是，先计算hash,在计算index，遍历查找，找到之后删除节点
/** * 根据key删除元素 */ public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e. value); } /** * 根据key删除链表节点 */ final Entry<K,V> removeEntryForKey(Object key) { // 计算key的hash值 int hash = (key == null) ? 0 : hash(key.hashCode()); // 根据hash值计算key在数组的索引位置 int i = indexFor(hash, table.length ); // 找到该索引出的第一个节点 Entry<K,V> prev = table[i]; Entry<K,V> e = prev; // 遍历链表（从链表第一个节点开始next），找出相同的key， while (e != null) { Entry<K,V> next = e. next; Object k; // 如果hash值和key都相等，则认为相等 if (e.hash == hash && ((k = e. key) == key || (key != null && key.equals(k)))) { // 修改版本+1 modCount++; // 计数器减1 size--; // 如果第一个就是要删除的节点（第一个节点没有上一个节点，所以要分开判断） if (prev == e) // 则将下一个节点放到table[i]位置（要删除的节点被覆盖） table[i] = next; else // 否则将上一个节点的next指向当要删除节点下一个（要删除节点被忽略，没有指向了） prev. next = next; e.recordRemoval( this); // 返回删除的节点内容 return e; } // 保存当前节点为下次循环的上一个节点 prev = e; // 下次循环 e = next; } return e;}HashMap的扩容
resize扩容是HashMap中非常重要的一个操作，在容器里的元素达到一个临界值时，HashMap会自动进行扩容，扩容的具体流程是；
1.在put的时候检查是否需要扩容，根据两个参数：初始容量和装载因子
2.创建一个容量为table.length*2的table，修改临界值
3.重新计算所有元素的hash值，并放入新的table，使用的是头插法
4.用新的table替换旧的table
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) {//最大容量为 1 << 30 threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity];//新建一个新表 boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing;//是否再hash transfer(newTable, rehash);//完成旧表到新表的转移 table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }--------------------- void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) {//遍历同桶数组中的每一个桶 while(null != e) {//顺序遍历某个桶的外挂链表 Entry<K,V> next = e.next;//引用next if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity);//找到新表的桶位置;原桶数组中的某个桶上的同一链表中的Entry此刻可能被分散到不同的桶中去了，有效的缓解了哈希冲突。 e.next = newTable[i];//头插法插入新表中 newTable[i] = e; e = next; } } }扩容的整体操作如上，但是有一些十分精妙的细节十分厉害
为什么扩容的容量一定是2的幂？
这么设计当然是为了性能，而且是十分显著的性能提升，涉及到了位操作，我觉得非常有意思，会在下一篇专门讲这样计算进行提升性能的例子。