1.1 HashMap概述
相信大家在大学的时候都学习过散列表。
使用散列表的查找算法主要分为两步，第一步是利用散列函数将被查找的键转化为一个索引，理想情况下，所有不同的key都会被散列为不同的索引值，但是由于散列函数无法达到完美的散列，所以，我们通常还需要处理碰撞的情况。
处理碰撞的方法主要有两种，一种是拉链法，另一种是线性探测法。
在HashMap中，使用的是拉链法，也就是一个桶，由数组构成，数组的索引代表了散列值，每个数组后接了一个链表。当出现冲突碰撞的情况时，我们将判断这个key是否已经存在，如果存在，那么，替换value值，如果不存在，那么，将这个Entry链接到链表上。
//HashMap中的桶 transient Node<K,V>[] table;
那么，当我们查找时，先找到对应的索引值，然后，遍历链表，找到所需的内容。
这里，我们需要注意，如果大量数据的散列值相同，就会导致链表很长，查找效率也就变低了。因此，在JDK1.8中，当链表的长度超出阈值，我们会将链表进行树化，形成红黑树，让查找效率提高。
还有就是，关于Map的resize。Map中有一个参数叫做负载因子loadFactor，当桶中的数据量达到桶的长度乘上负载因子时，就会进行扩容。扩容过程中，会把桶的大小变为原来的2倍，并且，将原来Map中的内容进行重新散列，这部分内容也是HashMap中的一个难点，而且，这个算法十分巧妙。
下面是HashMap中节点的数据结构，是单链表结点
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true;
