（本文的源码解析都存在与代码块的注释里面，请耐心观看）

开始之前 我们先简单了解以下HashMap。HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）

简单理解一下上面的图，假设我目前有一个数组，我想在数组中放入一个k-v结构的数据比如（“xmc”，“hansome”）它会根据数据的key也就是xmc，计算出一个hash码，根据hash码放入数组之中，这样的话，即使我以后存了成百上千的数据，只要我输入xmc，他就根据我的xmc计算出hash码从而快速定位到数组下标拿到我的“hansome”。但是hash码可能会形成冲突，比如“aaa”的hash码和我“xmc”的hash码一样，这时便可以在我数组的对应位置上加上一个结点解决冲突。

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

HashMap类如下

    static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;} 

一些重要的参数，看代码前必读。

/**实际存储的key-value键值对的个数*/
transient int size;/**阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，
threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到*/
int threshold;/**负载因子，代表了table的填充度有多少，默认是0.75
加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。
所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
*/
final float loadFactor;/**HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时，
如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），
需要抛出异常ConcurrentModificationException*/
transient int modCount;

 public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);//带参构造方法}public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
//调用默认构造方法，其中DEFAULT_INITIAL_CAPACITY=64，DEFAULT_LOAD_FACTOR=0.75}

下面看一下HashMap的构造方法

public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)//容量大小小于0抛异常throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)//大于0就设为1<<30initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))//负载因子小于0或不是float型抛异常throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;threshold = initialCapacity;//threshole等于初始容量init();//空的方法}

我们可以查看以下最常用的put方法源码，值得注意的是HashMap是在第一次放入数据的时候生成的table数组！！

 public V put(K key, V value) {if (table == EMPTY_TABLE) {//如果table为空，源码见下inflateTable(threshold);}if (key == null)return putForNullKey(value);//hashmap允许key为空的情况，会放入key为空的位置int hash = hash(key);//计算hash值，可以不用在乎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))) {//在entry数组中查找hash码相同并且key相同的位置，放入V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;//注意！ put方法是会返回原来的value值的（如果已经有的话）}}modCount++;addEntry(hash, key, value, i);return null;}

首先我们查看table为空的情况（以下两块代码段为重点，也解释了为什么HashMap在java中的长度必须是2的n次方，因为Entry数组的长度是要和key的hash码做与运算的）

private void inflateTable(int toSize) {// Find a power of 2 >= toSizeint capacity = roundUpToPowerOf2(toSize);//roundUpToPowerOf2方法为把一个数字向上转化为一个2的n次幂的数字，比如我传入7，给我转成8，传入10，转为16threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);table = new Entry[capacity];//初始化Entry数组 大小为上面的得到的capacity；initHashSeedAsNeeded(capacity);}

 static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);//这就是我们的数据存放的位置 也就是h和length-1做与运算，可以看到length必须是2的整数次幂，在上面的entry数组初始化源码中我们已经知道了是如何操作的，}

下面查看一下addEntry(hash, key, value, i);方法

    void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {//如果以及存在的数字大于了负债因子，扩容 数组长度乘2（保证一定是2的n次幂）resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);//头插法在新建结点}

当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。举个例子，假设现在entry数组长度为4，负载因子为2，此时entry头两个位置以及有了a,b两个数据，该addEntry方法会扩充entry长度至4，但是我想新放入的数据还是可能会在前两个ab的下面加入一个新节点。

可以查看下resize方法

void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//如果原来的capacity已经是最大的，则直接返回Entry[] newTable = new Entry[newCapacity];transfer(newTable, initHashSeedAsNeeded(newCapacity));//源码见下 关键点table = newTable;threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}//transfer
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {//遍历原来的entry数组，把原数组的内容放入新数组while(null != e) {Entry<K,V> next = e.next;if (rehash) {//重新计算hash，放入新的数组之中e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];//这部分就是1.7令人诟病的地方，如果是多线程，很容易成环newTable[i] = e;e = next;}}}

  public V get(Object key) {if (key == null)return getForNullKey();Entry<K,V> entry = getEntry(key);return null == entry ? null : entry.getValue();}final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;}

下面看看HashMap的get方法，由于比较简单 所以不做分析了

  public V get(Object key) {if (key == null)return getForNullKey();Entry<K,V> entry = getEntry(key);return null == entry ? null : entry.getValue();}final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;}