首先，HashMap是线程不安全的，所以才有ConcurrentHashMap和HashTable。
HashMap允许key和value为null值。（HashMap和HashTable基本相同，除了HashMap是线程不安全的以及HashMap允许null值）
影响HashMap性能的两个指标：（1）数组初始长度（桶的数量）（2）负载因子
因为当键值对数量>数组长度*负载因子时，HashMap就会扩容
jdk1.8之后，当HashMap中某个桶内的链表长度大于8时，会把链表转化成红黑树，以加快元素查询的速度。（事实上，转化成红黑树的概率很小，如果哈希分布正常的话）
=====以上为官方文档关于HashMap的一些注释======
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable { //可以看到HashMap继承了AbstractHashMap，定义中利用了泛型
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;以上是HashMap默认初始化时的部分属性值。
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
DEFAULT_INITIAL_CAPACITY：初始容量为16，也就是说会创造16个桶。桶的数量过多会导致遍历哈希表较慢，过少会导致扩容频繁。注意这里用了位运算，整个源码中采用了很多位运算的特殊性质。因为计算机处理位运算的速度比普通运算要快很多。
MAXIMUM_CAPACITY: 哈希表最大容量。
DEFAULT_LOAD_FACTOR: 默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。
TREEIFY_THRESHOLD: 上文说过，如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。
UNTREEIFY_THRESHOLD: 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。因为树的结构所占内存是普通链表结构的两倍以上。
MIN_TREEIFY_CAPACITY: 在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} //put函数，调用的是putVal函数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 令tab=table，若table未初始化或者长度为0，进行扩容 if ((p = tab[i = (n - 1) & hash]) == null) // (n - 1) & hash 确定元素存放在哪个桶中，令p为桶中第一个元素 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; //比较桶中第一个元素p和被放入节点之间的数据，当hash值和key值相同且equals也返回相同时（说明键重复），并令e=p else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //当p是一个树节点时的情况 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; // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表 } } // 表示在桶中找到key值、hash值与插入元素相等的结点 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //新值替换旧值 afterNodeAccess(e); // 只有在LinkedHashMap中重写了该方法 return oldValue; } } ++modCount; //修改次数+1 if (++size > threshold) resize();//如果大于了临界值，resize afterNodeInsertion(evict); return null; }
注意：putVal中有两个方法，afterNodeAccess()和afterNodeInsertion(evict)是给继承了HashMap的LinkedHashMap预留的，用于记录元素插入顺序
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value; //调用了getNode的函数，
}
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 当第一个节点是树节点时，调用树中的查询方法 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; // 找到key值和hash值相同的节点，返回 } while ((e = e.next) != null); } } return null; }
值得学习的一些方法：
1.求哈希的方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
扰动函数：混合高位和低位的信息，加大了值的随机性，同时高位的信息也被保留了下来
Node的hashCode值：
Objects.hashCode(key) ^ Objects.hashCode(value)
2.定位存放的数组位置（散列桶）
tab[(n - 1) & hash] //其中n为数组的长度因为n始终为2的N次方，所以n-1相当于一个低位掩码上述式子的运算结果等价于hash%n，然而与运算的速度要比取余快很多3.扩容机制size总是2的N次幂，这也是HashMap对Hashtable的一个改进。【首先，若数组长度为2的N次方，则数组的长度必然为偶数，则，偶数-1必然为奇数，在2进制的表示中，奇数的最后一位为1，所以，与奇数做“&”操作，最后的结果可能为奇数，也可能为偶数。
其次，若数组长度不为偶数，则奇数-1为偶数，偶数在2进制中最后一位为0，那么与偶数做“&”操作，最后的结果只可能是偶数，不可能为奇数，所以在奇数位置的空间不会存储到元素，所以会有二分之一的空间被浪费掉。
综上所述，数组长度取2的N次方，目的是为了能让元素均匀的分布在数组中，减小发生冲突的机会。】// 从结论反推，没有太大参考意义
扩容（rehash）后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，使得重新计算的过程得到了简化。(1.8的扩容新算法）看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希值(也就是根据key1算出来的hashcode值)与高位与运算的结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
以上也是1.8的一个优化点。4.时间性能HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)如果Hash算法技术的结果碰撞非常多，假如Hash算极其差，所有的Hash算法结果得出的索引位置一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。
