参考：https://www.cnblogs.com/skywang12345/p/3310835.html
哈希表 HashMap 是一个散列表（也叫哈希表），它存储的内容是键值对(key-value)映射。 HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。 Warming：HashMap将“key为null”的元素都放在table的位置0处，即table[0]中；“key不为null”的放在table的其余位置！
HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。 容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。 加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。 当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。 通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
从图中可以看出： (01) HashMap继承于AbstractMap类，实现了Map接口。Map是"key-value键值对"接口，AbstractMap实现了"键值对"的通用函数接口。 (02) HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。 table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。 size是HashMap的大小，它是HashMap保存的键值对的数量。 threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值=“容量✖加载因子”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。 loadFactor就是加载因子。 modCount是用来实现fail-fast机制的。
比如：数组的长度是5。这时有一个数据是6。那么如何把这个6存放到长度只有5的数组中呢。按照取模法，计算6％5，结果是1，那么就把6放到数组下标是1的位置。那么，7就应该放到2这个位置。到此位置，哈斯冲突还没有出现。这时，有个数据是11，按照取模法，11％5＝1，也等于1。那么 原来数组下标是1的地方已经有数了，是6。这时又计算出1这个位置，那么数组1这个位置，就必须储存两个数了。这时，就叫哈希冲突。冲突之后就要按照顺序来存放了。 HashMap就是一个散列表，它是通过“拉链法”解决哈希冲突的
拉链法又叫链地址法，Java中的HashMap在存储数据的时候就是用的拉链法来实现的，拉链发就是把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0…m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针(来自百度知道)。简单来说拉链发就是数组加链表。
1、HashMap数据存储数组
transient Entry[] table;2、数据节点Entry的数据结构
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; // 指向下一个节点 Entry<K,V> next; final int hash; // 构造函数。 // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 判断两个Entry是否相等 // 若两个Entry的“key”和“value”都相等，则返回true。 // 否则，返回false public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } // 实现hashCode() public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } // 当向HashMap中添加元素时，绘调用recordAccess()。 // 这里不做任何处理 void recordAccess(HashMap<K,V> m) { } // 当从HashMap中删除元素时，绘调用recordRemoval()。 // 这里不做任何处理 void recordRemoval(HashMap<K,V> m) { } }从中，我们可以看出 Entry 实际上就是一个单向链表。这也是为什么我们说HashMap是通过拉链法解决哈希冲突的。 Entry 实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数。这些都是基本的读取/修改key、value值的函数。
HashMap是通过拉链法实现的散列表。表现在HashMap包括许多的Entry，而每一个Entry本质上又是一个单向链表。 当我们通过entrySet()获取到的Iterator的next()方法去遍历HashMap时，实际上调用的是 nextEntry() 。而nextEntry()的实现方式，先遍历Entry(根据Entry在table中的序号，从小到大的遍历)；然后对每个Entry(即每个单向链表)，逐个遍历。
计算key的hashCode，然后定位Entry[]位置，然后在获取迭代器去遍历Entry[i]的单向链表
public V get(Object key) { if (key == null) return getForNullKey(); // 获取key的hash值 int hash = hash(key.hashCode()); // 在“该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.equals(k))) return e.value; } return null; }若要添加到HashMap中的键值对对应的key已经存在HashMap中，则找到该键值对；然后新的value取代旧的value，并退出！ 若要添加到HashMap中的键值对对应的key不在HashMap中，则将其添加到该哈希值对应的链表中，并调用addEntry()。
public V put(K key, V value) { // 若“key为null”，则将该键值对添加到table[0]中。 if (key == null) return putForNullKey(value); // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。 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; // 若“该key”对应的键值对已经存在，则用新的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; } } // 若“该key”对应的键值对不存在，则将“key-value”添加到table中 modCount++; addEntry(hash, key, value, i); return null; }addEntry() 找到table[bucketIndex]的Entry<K,V>，将key-value设置进去，判断
void addEntry(int hash, K key, V value, int bucketIndex) { // 保存“bucketIndex”位置的值到“e”中 Entry<K,V> e = table[bucketIndex]; // 设置“bucketIndex”位置的元素为“新Entry”， // 设置“e”为“新Entry的下一个节点” table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小 if (size++ >= threshold) resize(2 * table.length); }(01) **addEntry()**一般用在 新增Entry可能导致“HashMap的实际容量”超过“阈值”的情况下。 例如，我们新建一个HashMap，然后不断通过put()向HashMap中添加元素；put()是通过addEntry()新增Entry的。 在这种情况下，我们不知道何时“HashMap的实际容量”会超过“阈值”； 因此，需要调用addEntry() (02) createEntry() 一般用在 新增Entry不会导致“HashMap的实际容量”超过“阈值”的情况下。 例如，我们调用HashMap“带有Map”的构造函数，它绘将Map的全部元素添加到HashMap中； 但在添加之前，我们已经计算好“HashMap的容量和阈值”。也就是，可以确定“即使将Map中的全部元素添加到HashMap中，都不会超过HashMap的阈值”。 此时，调用createEntry()即可。
