HashMap 实现
initialCapacity 是其中构造方法一个参数，用于开发者初始化容器大小，此值会被加工为 2 的幂
size 变量指的是容器目前存在的 (key, value) 对总和
threshold 变量指的是容器最大可以容纳的 (key, value) 对
table.length 指的是底层实现数组的真正长度
loadFactor 变量是一个浮点数类型被称为 加载因子
HashMap 实例创建后并不会立刻创建 table 数组占用空间。
通过
table.length和loadFactor计算最大容纳（threshold = table.length * Load factor）结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
HashMap 为什么需要扩容
因为 Map 接口在长度上设计是可变，HashMap 可以在构造方法上指定初始大小和扩容因子，初始大小会被通过位运算选取最近2的幂。
为什么 initialCapacity 需要为 2 的幂
尽量希望减少 Hash 碰撞，使内部元素在数组中分配均匀。
hash(Object key)这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
在什么时候扩容
当 Table 为空会立即扩容。当元素被插入后，如果容器内实际元素大小大于 threshold 则按照 loadFactor进行扩容 ，默认的扩容因子为 0.75 也就是当实际容量达到 75% 的时候进行扩容。
扩容因子的目的的是什么
HashMap 此处设计希望开发者针对特殊场景可以灵活实现，而不是像 ArrayList 一样扩容 50%
同样，越大的数组碰撞的几率越低，不必要再去遍历链表或者查询红黑树。
HashMap 长度的无限的吗
Map 接口定义 size() 方法返回为 int 类型，理论上应最大支持 Integer.MAX_VALUE 个元素，HashMap中有定义最大可容纳元素 MAXIMUM_CAPACITY = 1 << 30 这个值也是 2 的幂，同 ArrayList 一样超过这个值则设定为 Integer.MAX_VALUE 防止 int 溢出。
HashMap Put 方法分析
HashMap 和 ArrayList 一样都没有在构造方法中初始化容器大小，可有效减少空 HashMap 带来的空间浪费。
- 在
put方法中如果 table 没有创建则进行创建。 - 计算 hash 确定元素下标，如果下标位置为空直接放入并返回。
- 如果当前下标存在元素则进行比较是否“相等”
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))如果两元素hash值相等并且key引用相等，或者两keyequals 方法返回true则认为找到目标元素，则进行原地覆盖。 - 如果当前下标元素未能确认相等，则判断当前下标下元素
Node是否为红黑树，若为红黑树则进行红黑树插入逻辑（这里不进行展开） - 如果当前下标未能确认相等，并且，当前下标节点也不是红黑树则进行链表逻辑操作，遍历链表到末尾并计算总长度，如果长度大于
8则立即进行红黑树转换，同时遍历过程中进行Key的比较如果相同进行原地覆盖。 - 根据 threshold 判断 size 是否溢出，如果溢出则立即进行扩容。
- 返回（注意，如果以上流程存在替换 Value 行为则返回
oldValue）
以上操作都必须经历 6 - 7 操作
扩容大小永远是原大小的两倍oldCap << 1
如何计算 Hash和确定位置？
如果 key 为 null 则返回 null 其他情况直接获取对象的 hashCode() 方法无符号右移 16 位并与原 hashCode() 进行 ^ （按位异或，同为 1 则为 0）运算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
例如字符串 xxx 计算结果为 119161 二进制为 11101000101111001 当前HashMap数组长度为 16 下标总长为 15 将 15 & 119161（与运算，同为 1 则为 1）即 1111 & 11101000101111001 结果为 1001 下标为 9 将 Key 与 Value 包装成 Node 放入下标位置执行上方 2-7逻辑。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
扩容是如何转移元素的？
需要 rehash 吗
JDK 1.7 可能需要 rehash 在 JDK 1.8 对 rehash 进行了优化，因为 table 长度恒定 2 的幂，例如扩容前为 16 - 1 （0000 1111）扩容后为 32 - 1（0001 1111），某元素 hash 为 1100 0101 在经过扩容后重新进行下标计算 0000 1111 & 1100 0101 == 0001 1111 & 0001 1111 与 16 是一致的，如果某元素为 hash 1101 0101 结果为 0001 0101 其下标新增 16 所以仅需要判断高位是 1 还是 0 如果是 0 位置保持不变，如果为 1 则为 原索引+oldCap
红黑树相关
UNTREEIFY_THRESHOLD = 6 注意当红黑树长度小于此值时，当退化为链表。
总结
- 非线程安全的
- HashMap 严重依赖对象的
hashCode()和equals() 方法重写equals需要注意 - HashMap 存在空间浪费，如果可以则尽量指定容器大小
- 同 ArrayList / LinkedList 一样存在快速失败机制
modCount主要应用场景在迭代器上 - Key 值的 HashCode 需要足够分散
