HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
特性
- HashMap根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。
- HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
- HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
结构
从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。
数组中的每个元素是内部类Node，其实现如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
HashMap中根据key对象的hash值计算出在数组中的索引，实现数组存储更加均匀，提高性能和效率。
我们上面可知，object对象的hashcode与对象内存地址一一对应，表示对象的唯一性。而通过hashcode计算出key对象的hash值也是唯一的，且对于同一个key对象，任何时候重复计算都会得到同样的hash值，从而定位出在数组中的位置。
hashcode计算出hash值的公式：
在JDK8中，由于使用了红黑树来处理大的链表开销，所以hash这边可以更加省力了，只用计算hashCode并移动到低位就可以了。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
根据hash值计算在table[] 数组中的位置公式：
int index = (hash & 0x7FFFFFFF) % table.length;
因为某些对象的 hashCode 可能会为负值，与 0x7FFFFFFF 进行与运算可以确保 index 为一个正数。
插入
HashMap的put()方法源码为：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//table为空则创建
if ((tab = table) == null || (n = tab.length) == 0){
n = (tab = resize()).length;
}
//计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null){
tab[i] = newNode(hash, key, value, null);
}else {
Node<K,V> e; K k;
//节点hash值同，且key值与插入key相同，直接覆盖value
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
} else if (p instanceof TreeNode){
//判断该链为红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
//已经产生碰撞，采用链地址法解决冲突
for (int binCount = 0; ; ++binCount) {
//p第一次指向链表头,以后依次后移
if ((e = p.next) == null) {
//e为空，表示已到链表尾也没有找到key值相同节点，则新建节点
p.next = newNode(hash, key, value, null);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) {
// -1 for 1st
treeifyBin(tab, hash);
}
break;
}
//容许null==null
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
//更新p指向下一个节点
p = e;
}
}
//更新hash值和key值均相同的节点Value值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
整体流程为：
- 对key的hashCode()做hash，然后再计算index;
- 如果没碰撞直接放到哈希桶数组里；
- 如果碰撞了，以链表的形式存在哈希桶数组后；
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果哈希桶数组满了(超过load factor*current capacity)，就要扩容。
在上面HashMap的插入过程中，如果出现两个key定位到同一个数组位置，表示发生了Hash碰撞。
哈希表为解决碰撞（冲突），可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。
链地址法，简单来说，就是数组加链表的结合。
取值
HashMap的get()方法源码为：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//hash & (length-1)得到对象key的存储索引
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//hash码相同且key与要get的key的相同则返回数组此处的Node，之后转化为value
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果第一个节点是TreeNode,说明采用的是数组+红黑树结构处理冲突
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;
} while ((e = e.next) != null);
}
}
return null;
}
整体流程为：
- 在哈希桶数组里的第一个节点，直接命中；
- 如果有冲突（碰撞），则通过key.equals(k)去查找
- 若为树，则在树中通过key.equals(k)查找，O(logn)；
- 若为链表，则在链表中通过key.equals(k)查找，O(n)。
小结
- 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
- 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
- HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
- JDK1.8引入红黑树大程度优化了HashMap的性能。
- 还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。
