为什么用HashMap
- HashMap是一个Hash桶(数组+链表)，桶存储的内容是键值对(Key-value)映射
- HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改
- HashMap是非synchronized，所以HashMap很快(哈哈哈)
与HashTable的区别？
HashTable:线程安全，效率低，不允许Null键Null值
HashMap:非线程安全，效率高，允许Null键Null值存储
为什么HashMap允许为空 Hashtable不允许为空
Hashtable中put时如果Value为空，会引出空指针异常
而Key为空时，在调用hashCode()时，也会报空指针
以下是Hashtable put方法片段
if (value == null) {throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
复制代码而HashMap的没有对value进行空判断，而且hashMap内部实现的hash()方法，当key为null时，返回0
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码HashMap工作原理是什么？
HashMap是基于hashing的原理，储对象通过使用put(key, value)存到hash桶中，获取对象通过get(key)从hash桶中检索。
HashMap通常会用一个Hash桶(table[])来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出对应这个数组的下标i，然后就把该键值对插到table[ i ]中，如果有两个不同的key被算在了同一个i下标，那么就叫Hash冲突，又叫 Hash碰撞，那么在同一个位子上的元素将以链表的形式存放，先加入的在链头，后加入的放在链尾，这样会在table[i]上形成一个链表。最坏的情况下，所有的key都映射到同一个下标位置，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)
Hash表这个容器当有数据要插入时，都会检查容量有没有超过当前的threshold(阈值)，如果超过，则扩容，但是这样，整个Hash桶里元素需要重新算一遍新的位置。这叫rehash，这个成本相当的大，因此《码出高效》中也推荐在集合创建时，可以根据实际情况，指定集合初始值大小。
put()实现
当我们给put(K,V)方法传递键和值时，我们先对键(Key)调用hashCode()方法，返回的hashCode用于找到bucket位置(Hash桶数组下标)来储存对象。
探索源码:HashMap底层put探索
get()实现
当调用get(K)获取value时，我们也会先对键(K)调用hashCode()方法，返回的hashCode用于找到bucket位置中的Entry对象，相当于索引，他的时间复杂度是O(1)
探索源码:HashMap底层get探索
resize() / 扩容实现 / rehash
当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍长度的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，扩容相对来说是个耗资源的操作
探索源码:HashMap底层扩容实现
Hash碰撞
再说Hash碰撞之前，先了解一下hashCode()和equals()两个方法的区别
// hashCode()返回值相同的两个对象 两个对象equals()结果不一定为true
// equals()结果为true的两个对象，hashcode()返回值一定相同
复制代码明明两个Key是不同的，但hashCode相同，导致的Hash碰撞(Hash冲突),hashCode是存储地址索引，如果该地址已经存在对象元素了，是返回错误，还是覆盖现有对象元素呢？在Java中，这时候链表结构就有意义了，单链表的头指针存在Hash桶的(hashCode索引下标)对应位置中，但此时检索的时间复杂度也变成了O(n)
Hash碰撞解决方法
为什么String, Interger这样的封装类适合作为键？
String,Interger这些封装类内部的值都是不可变的(final关键字修饰)，
并且内部重写了equals()和hashCode()方法，其他的封装类也有这个特点，因为存取对象的时候要用到equals()和hashCode()方法。
不可变性是必要的，为了计算hashCode()，就要防止键值改变，否则检索就没有意义了。
不可变性还有其他的优点如线程安全
为什么HashMap的桶数组长度一定是2的次幂？
HashMap内部定义了每次扩容是原本长度的两倍，也就是每次扩容，左移一位，那么这样做的的好处呢？
合理存放元素
桶长度为16扩容后变成32,(二进制)10000-->100000
(length-1) 也从 1111 变成 11111 # 对于什么是length-1请先看完源码
2的n次方就是1后面n个0，2的n次方-1 实际就是n个1；
h&1111 和 h&11111
假设h为21（10101）
我们会发现, 因为'0 1111'低位都是'1', 进行'&'(位与)操作, 就能成功保留'10101'对应的低位, 将高位的都丢弃, 低位是多少, 最后结果就是多少 . 刚好低位的范围是'0~15', 刚好是长度为16的所有索引 ,扩容后也是同理
均匀分布,减少碰撞
例如长度为9时候，3&(9-1) = 0 ; 2&(9-1) = 0，那么索引位置都在0上，发生碰撞
例如长度为8时候，3&(8-1)=3 ; 2&(8-1)=2 ，元素均匀存入不同位置上
总结
所以hash桶数组长度为2次幂，是为了能够合理放入有效数组索引中以及防止hash发生太多碰撞，对于HashMap检索是有利的
参考文档
How HashMap works in Java
HashMap实现原理及源码分析
