HashMap是基于哈希表对Map接口的一个实现。这个实现类提供类Map的所有可选的操作，同时允许储存null值和null键。和HashTable差不多，不同的是，HashMap是线程不安全的并且允许空的键值对。这个类不保证map的顺序。
HashMap的主干是一个数组，每个元素可能是一个链表，也可能是一个红黑树，这要视这个元素所储存的键值对多少来决定。在jdk1.8以前是是一个链表的数组，但是在jdk1.8以后，加入了红黑树的概念。把key的哈希值根据数组长度取模以后得到的位置就是这个k-v要存放的位置，这个位置可以是一个链表，也可以是一棵红黑树。HashMap寻找键值对时，使用key的hash值对数组取模获取存储位置，如果存储位置的长度为1，则说明之前没有发生hash碰撞，这个节点即为要查找的节点，这个时候时间复杂度仅仅是O(1)。如果发生了hash碰撞，当碰撞节点是个链表时，说明这个链表的元素最多8个（源码中可以看出），通过循环遍历键值对，对比key.equals来确定地址；如果碰撞点是个红黑树，那说明这个树节点最少6个，通过红黑树确定地址，红黑树的时间复杂度是O(logN)。这么看来，HashMap的时间复杂度最多也就是O(logN)，这就是为什么它会如此高效。接下来我们走一遍HashMap的生命周期。
创建HashMap的时候并没有初始化table，而是在put操作的时候才会初始化table。
1 HashMap有四个构造方法：
1.1 public HashMap(int initialCapacity, float loadFactor);
参数中的initialCapacity和loadFactor分别是HashMap的初始容量和负载因子。
1.2 public HashMap(int initialCapacity)；
1.3 public HashMap()；
1.4 public HashMap(Map<? extends K, ? extends V> m)；(初始化table)
2 HashMap的几个变量：
2.1 transient int size;
map中的容纳的键值对总数。
2.2 transient int modCount;
map结构被修改的次数，这个变量在使用迭代器遍历元素的时候会用到。举个例子：
public static void main(String[] args) { Map<String,Object> map = new HashMap(1 << 2, 0.75f) {{ put("a", 1); put("b", 1); put("c", 1); put("d", 1); }}; Iterator<Map.Entry<String,Object>> iterator = map.entrySet().iterator(); int i = 0; while (iterator.hasNext()){ Map.Entry<String,Object> next = iterator.next(); do { map.remove("a"); }while (i==1); i++; } } 控制台： Exception in thread "main" java.util.ConcurrentModificationException at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429) at java.util.HashMap$EntryIterator.next(HashMap.java:1463) at java.util.HashMap$EntryIterator.next(HashMap.java:1461) at HashMapPractice.main(HashMapPractice.java:17)抛出异常的地方在这里：
final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); } return e; }当modCount与期望的expectedModCount不一致时，便会抛出ConcurrentModificationException。所以在使用map元素的迭代器时，一定要注意不能随意修改map的结构。
2.3 int threshold;
The next size value at which to resize (capacity * loadFactor).下一次重新扩充map容量的标志，这个值由capacity和load factor决定。当创建HashMap没有指定initialCapacity时，capacity默认为8（static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;），当没有指定loadFactor时，loadFactor默认为0.75f（static final float DEFAULT_LOAD_FACTOR = 0.75f;）。
2.4 final float loadFactor;
这个在2.3中已经提过，负载因子，代表map的容量达到某个值时，重新扩充容量。
2.5 transient Set<Map.Entry<K,V>> entrySet;
Map子类Entry的set集合，可用来获取所有的键值对。
2.6 transient Node<K,V>[] table;
HashMap子类Node的集合，可用来获取当前所有的节点。在实例第一次运行put操作时初始化，并且在必要时重新扩容，这个数组的长度永远是2的次方。
3 HashMap的几个内部类：
3.1 Node
3.2 KeySet
3.3 Values
3.4 EntrySet
3.5 TreeNode
4 HashMap的主要方法源码分析
4.1 返回一个给定对象的类型（仅限可比较类型的对象）。
/** * Returns x's Class if it is of the form "class C implements * Comparable<C>", else null. */ static Class<?> comparableClassFor(Object x) { //如果给定对象x不是Comparable实例，则返回null。 if (x instanceof Comparable) { //定义一个类型变量c;两个Type数组ts,as;一个Type t;一个ParameterizedType p; Class<?> c; Type[] ts, as; Type t; ParameterizedType p; //如果x的类型为String,则直接返回String.class。 if ((c = x.getClass()) == String.class) // bypass checks return c; //如果获取该类型的实现接口信息的Type数组，包含泛型信息 if ((ts = c.getGenericInterfaces()) != null) { for (int i = 0; i < ts.length; ++i) { //遍历Type数组，如果某个Type是ParameterizedType实例同时 if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; }4.2 比较给定的两个参数k,x，返回比较值
static int compareComparables(Class<?> kc, Object k, Object x) { //如果x为空或者x不是kc类型，那么返回0；否则返回k和x的比较值 return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x)); }4.1 添加键值对 put
1.put方法直接调用 putVal方法，并没有做其他操作。由此可见，真正的put操作是putVal 添加并替换key-value，返回旧值。 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 2. /** * 实现Map.put和相关的方法 * * @param hash key的hash值 * @param key 要储存的key * @param value 对应的value * @param onlyIfAbsent 是否不替换已存在的value，当为true时，不替换；当为false时，替换。 * @param evict if false, the table is in creation mode. * @return 返回key对应的旧值 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict){ Node<K,V>[] tab; Node<K,V> p; int n, i; //判断table是否初始化，如果没有初始化则调用resize()进行初始化，resize()方法在下面讲解 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 计算这个key在链表中的位置，如果这个位置为空，则新建一个链表 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 如果这个位置不为空，那说明出现哈希碰撞的情况，将这个键值对追加到这个位置的链表或者红黑树中 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 3. /** * 初始化或者增倍table的容量，Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //获取此时的table容量，扩容阈值，如果容量大于0且大于等于最大容量，那么将扩容阈值置为int //最大临界值，并返回旧的table，不进行扩容。 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //如果旧容量没有达到最大容量，且满足容量阔倍后未达到最大容量，同时旧容量大于等于默认容量，那么将容量阔倍。 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //如果旧的扩容阈值大于0，则说明扩容阈值已经被定义，直接使用旧值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { //否则，使用默认容量和默认负载因子获取默认的扩容阈值。 // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果最新的扩容阈值为0，那么重新获取扩容阈值，保证最新阈值不得超过最大容量值 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //重新定义数组table @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //如果旧数组不为空，则填充到新的数组中 if (oldTab != null) { //遍历旧的数组 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //获取旧数组的节点，如果不为空，且该节点只有一个，那么重新计算旧节点在新数组中的位置，放入新数组中。 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //如果该节点不只有一个，且该节点是个红黑树，那么将该节点重新加入到新的数组中 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order //否则，该节点是个容量大于1的链表，此时定义两个链表lo,hi Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; //遍历旧链表e do { //获取e下一个节点，如果下一个节点在旧数组中是第一个节点,那么将该节点追加到链表lo中 next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //如果下一个节点在旧数组中不是首节点，那么将该节点追加到链表hi中 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //遍历完以后，如果loTail存在且没有后续节点，那么将新数组的该节点指向这个链表的头部 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //如果hiTail存在且没有后续节点，那么将该节点向后移动旧容量大小的位置，添加到新的数组中 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
