Java容器系列之HashMap的存储
Java容器系列之HashMap
概要
本文将结合Java源码总结HashMap的存储结构及其扩容策略，并根据这些特点给出使用HashMap的最佳实践。
本文不再介绍HashMap的基本使用，有需要的请先学习下Java容器的基础知识。
存储结构
HashMap的核心问题是如何保证读写的速度？答案是使用Key对象的Hash值来合理存储对象。我们知道，每个java对象都有其默认的hashCode()方法，也就是每个对象都有一个int值与之对应。那么如何利用这个int值来快速存储对象呢？
1.按照hash值找坑位
假设定义了一个长度为8的HashMap，那么HashMap会创建一个长度为8的数组作为容器来存放键值对（在HashMap内部使用了Node<Key,Value>对象来存储）。也就是说，这个数组的元素是Node对象。那么，此时有8个坑位可以用来放置元素。我们按照Java的数组index标号，也就是从0到7分别标号。
Key对象的Hash值我们是能够得到的，此时如果把这个Hash值来对8取模，自然是从0到7的一个分布了。故根据Key对象的Hash值，我们可以快速找到该Key放在了数组的哪个坑位，避免的数组的轮询。
总结下，坑位的取得方式，简单的说就是先得到Key的HashCode，然后把这个值对HashMap的长度取模。
此处有一个问题，如果两个不同的Hash值，取模的结果相等怎么办？比如： 如果Key1的hash值是7，Key2的hash值是15，此时它们对8取模，都是得到7，不可能把这两个对象放在一个坑位。
2.当不同的Key得到同一个坑位后，按照链表或者红黑树存储
JDK8之前，使用了链表来存储hash取模后一样的元素。而JDK8开始使用了链表和红黑树相结合的方式来存储。
- 链表存储
查看Node的定义，可以看到它包含了一个next属性。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
......
}
正是利用这个next，实现了链表的存储。此时，从HashMap取元素的时候，首先找到坑位，然后遍历坑位中的链表，逐一判断Key对象的hashCode是否相等，而且Key对象的equals方法是否返回true。当且仅当hashCode相等，而且equals方法返回true时，才认为找到了key对应的元素，并返回该Node对象中包含的value对象。
总结下，一个坑位下挂载了若干个元素，这些元素有以下特点。
1）同一坑位下的链表中，各个元素的Key对象Hash值取模后的值都是一样的。
2）链表的先后顺序按照进入HashMap的时间顺序排列，新元素被放入坑位，并且其next指向原来在坑位中的元素。
3）这个顺序是可能变化的，比如扩容的时候。这样也就不难理解为什么HashMap无法保证元素的排序了。
显然，这样有个缺点，就是如果这个链表很长，那边取元素的性能会随着链表的拉长而变差，而且是越来越差。所以，JDK8开始，引入了红黑树的存储方式。当某个坑位下的链表的长度小于8的时候，还是链表存储；否则，变换成红黑树存储。
- 红黑树存储
红黑树能够保证存取元素的速度不会随着元素数量的增加而迅速恶化（时间复杂度为lg(n)）。具体这里不展开讲，红黑树的资料还是很多的。
查看JDK8的HashMap源码，其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;
if ((p = tab[i = (n - 1) & hash]) == null) // 取模使用的是长度减1再跟hash位与操作
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;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) //达到8则转换成树
treeifyBin(tab, hash);// 链表转换成红黑树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
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;
}
扩容策略
HashMap在使用的时候并没有人会关注其大小，看上去这个容器是无限大小的，反正有东西就往里面放，至于里面放了多少，还能放多少，没人关心。这完全得益于其自动化的扩容机制。HashMap内部定义了一套扩容的机制，以应对元素的扩张。
1.HashMap的扩容阈值
当往HashMap中放入元素的时候，如果HashMap中的元素个数达到某个阈值时，会触发扩容操作。这个阈值由loadFactor属性控制的，这个值是个小数（默认值是0.75），阈值等于map的整体容量乘以loadFactor。如此做的目的是确保坑位的量足够，让元素能够足够的分散。扩容后的容量一般是翻倍，而且容量都是2的幂，比如2，4，8，16，32，64.......这样做的目的是为了方便取模的操作（取模的操作很巧妙，会再开一文）。
2.HashMap的扩容方法
扩容的操作通常是增加容量后，重新安置各个元素。扩容后，元素的放置都重新打乱了，等于是重新生成了一次HashMap。所以，尽量减少扩容是比较明智的。
最佳实践
- 使用HashMap的时候，如果能够预估容器的大小，那么在初始化的时候就指定size的大小。这样可以尽量减少容器的扩容操作，提高程序运行效率。下例中，我们在初始化map的时候，指定了其size为100。如下所示：
Map<String, String> map = new HashMap<String, String>(100);
虽然代码中定义的长度是100，但是实际的长度是大于100的最小的2的n次方的值，有点绕口。举例如下：
如果指定了50，那么实际长度是2的6次方，64
如果指定了100，那么实际长度是2的7次方，128
以此类推。。。
2.HashMap不是线程安全的，需要注意多线程的同步问题。特别是可能导致死循环的问题（在HashMap扩容时，多线程的情况下使用HashMap可能会导致死循环）。如果需要保证线程安全，建议使用HashMap+Collections工具类的组合来做，而不是使用Hashtable。如下所示：
Map<String, Object> map = new HashMap<String, Object>();
Map<String, Object> synMap = Collections.synchronizedMap(map);
synMap.put("key1", "value1");
当然，Hashtable也是线程安全的，但是该类的同步控制粒度比较大，跟上面比性能更低些，而且该类也是逐步被废弃的态势在发展，少用吧。
线程安全是消耗性能的，所以能回避线程安全问题就尽量回避，这是上上策。
3.如果还想要保证顺序，可以考虑使用LinkedHashMap来实现。它是在HashMap的基础上增加了一组保存先后顺序的双向链表。可以按照LRU（最不常用的放到最后，越常用的越在前面），或者按照放入容器的顺序排列。
