资料：
HashMap和HashTable到底哪不同？
Java集合——HashMap、HashTable以及ConCurrentHashMap异同比较
简介
版本：HashTable产生于JDK 1.1，而HashMap产生于JDK 1.2
HashMap和HashTable的相同点：
HashMap和HashTable都是基于哈希表来实现键值映射的工具类，HashTable和HashMap采用相同的存储机制，二者的实现基本一致
HashMap和HashTable的区别：
（1）HashMap是非线程安全的，HashTable是线程安全的。
（2）HashMap的键和值都允许有null存在，而HashTable则都不行。
（3）因为线程安全、哈希效率的问题，HashMap效率比HashTable的要高。
扩容方式：
HashMap的扩容方式是：默认大小是16，扩容规则：2的指数倍
HashMap的哈希算法：采用位运算，比取模运算效率更高，同样能达到使其分布均匀的目的HashTable的扩容方式是：默认大小是11，扩容规则：n*2+1
即就是：hash() * (length - 1)来定位数组下标
在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；
???
HashTable和ConCurrentHashMap的对比：
ConcurrentHashMap它是线程安全的HashMap的实现。
HashTable里使用的是synchronized关键字，这其实是对对象加锁，锁住的都是对象整体，当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。ConcurrentHashMap算是对上述问题的优化。
ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的syn关键字锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。
在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，
对外的接口（API）
虽然都实现了Map、Cloneable、Serializable三个接口。但是HashMap继承自抽象类AbstractMap，而HashTable继承自抽象类Dictionary（Dictionary已经废弃使用了）。
异同比较：
从公开的方法上来看，这两个类提供的，是一样的功能。都提供键值映射的服务，可以增、删、查、改键值对，可以对建、值、键值对提供遍历视图。支持浅拷贝，支持序列化。
Null Key & Null Value
HashTable不支持null键和null值，当HashTable在遇到null时，会抛出NullPointerException异常。
##java.util.Hashtable
public synchronized V put(K key, V value) {
// 如果value为null，抛出NullPointerException
if (value == null) {
throw new NullPointerException();
}
// 如果key为null，在调用key.hashCode()时抛出NullPointerException
// ...
}
HashMap是允许key和value为空的，这是因为HashMap在实现时对null做了特殊处理，将null的hashCode值定为了0，从而将其存放在哈希表的第0个bucket中。
以下代码及注释来自java.util.HasMap
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 当key为null时，调用putForNullKey特殊处理
if (key == null)
return putForNullKey(value);
// ...
}
private V putForNullKey(V value) {
// key为null时，放到table[0]也就是第0个bucket中
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
HashMap介绍
1 HashMap数据结构
总述：
数据结构：数组+链表 数组=桶 链表存Entry(键值对)
Java中的数据存储方式有两种结构：
一种是数组：数组是空间连续，寻址迅速，但是在增删元素的时候会有较大幅度的移动，所以数组的特点是查询速度快，增删慢。
一种是链表：链表空间可以不连续，查询需要顺序查找，增删元素只需修改指针；所以链表的特点是查询速度慢、增删快。
那么有没有一种数据结构来综合一下数组和链表以便发挥他们各自的优势？答案就是哈希表。哈希表的存储结构如下图所示：
上图画出的是一个桶数量为8，存有5个键值对的HashMap/HashTable的内存布局情况。可以看到HashMap/HashTable内部创建有一个Entry类型的引用数组，用来表示哈希表，数组的长度，即是哈希桶的数量。而数组的每一个元素都是一个Entry引用，从Entry对象的属性里，也可以看出其是链表的节点，每一个Entry对象内部又含有另一个Entry对象的引用。
这样就可以得出结论，HashMap/HashTable内部用Entry数组实现哈希表，而对于映射到同一个哈希桶（数组的同一个位置）的键值对，使用Entry链表来存储(解决hash冲突)。
Entry对象源码
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash; //键对象的hash值
final K key; 键对象
V value;
Entry<K,V> next;
/*
* Entry对象唯一表示一个键值对，有四个属性
* hash ：键对象的hash值
* key： 键对象
* value：值对象
* next：指向链表中下一个Entry对象，可为null，表示当前Entry对象在链表尾部
*/
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
....
}
2 HashMap扩容方式
总述
HashMap的扩容方式是：默认大小是16，扩容规则：2的指数倍
HashMap的哈希算法：采用位运算，比取模运算效率更高，同样能达到使其分布均匀的目的
HashMap和HashTable源码
resize()
HashMap存在扩容的情况，对应的方法为HashMap中的resize方法：
//Node<K, V>[] java.util.HashMap.resize()
/**
* 该函数有2中使用情况：1.初始化哈希表；2.当前数组容量过小，需要扩容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;// 扩容前的数组（当前数组）
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 扩容前的数组容量（数组长度）
int oldThr = threshold;// 扩容前数组的阈值
int newCap, newThr = 0;
if (oldCap > 0) {
// 针对情况2：若扩容前的数组容量超过最大值，则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 针对情况2：若没有超过最大值，就扩容为原来的2倍（左移1位）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 针对情况1：初始化哈希表（采用指定或者使用默认值的方式）
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);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每一个bucket都移动到新的bucket中去
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
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
hash()函数
上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动）;
在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；
总结
简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：
- 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
- 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
- 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；
