声明：原创文章，转载请注明出处。http://www.jianshu.com/u/e02df63eaa87
Java集合系列
Java集合1-Map总结
Java集合2-HashMap详解（含源码分析）
1、数据结构
从上图可以看到，HashMap是由数组、链表和红黑树（JDK1.8）实现的。
- Node<K, V> table
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
HashMap的table是一个Node数组，Node是HashMap的内部类，实现了Map.Entry<K, V>，也就是说，Node可以理解为是一个包含Key, Value组合的桶。
-
冲突解决
常见的Hash冲突解决的方法有：开放地址法（线性探查法、线性补偿探测法、伪随机探测）、拉链法、再散列（双重散列，多重散列）等。JDK中的HashMap采用了拉链法解决冲突。
2、HashMap的几个重要字段
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
DEFAULT_INITIAL_CAPACITY: 初始容量，也就是默认会创建 16 个桶，桶的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。MAXIMUM_CAPACITY: 哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题。DEFAULT_LOAD_FACTOR: 默认的填充因子。TREEIFY_THRESHOLD: 这个值表示当某个桶中，链表长度大于 8 时，会转化成红黑树。UNTREEIFY_THRESHOLD: 在哈希表扩容时，如果发现链表长度小于 6，则会由红黑树重新退化为链表。MIN_TREEIFY_CAPACITY: 在转变成红黑树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。table：存储元素的数组（桶），总是2的倍数。entrySet: HashMap的视图。HashMap的entrySet()方法返回一个特殊的Set，这个Set使用EntryIterator遍历，而这个Iterator则直接操作于HashMap的内部存储结构table上。通过这种方式实现了“视图”的功能。整个过程不需要任何辅助存储空间。从这一点也可以看出为什么entrySet()是遍历HashMap最高效的方法，原因很简单，因为这种方式和HashMap内部的存储方式是一致的。size：此HashMap中 K-V 对的个数。modCount: 每次修改或者扩容map结构的计数器，主要用于fail-fast。
我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。
threshold：阈值。即该HashMap所能容纳的最大Node的个数。其大小为this.threshold = tableSizeFor(initialCapacity);，也就是初始容量的向上一个2^n。举个栗子，如果初始值为16，则该阈值为16；如果初始值为17-32则该阈值为32。但是在执行一次put后，该值的大小则变成(capacity × loadFactor )，有待考证。
而在Java7中，该值的初始化大小为threshold = (int)(capacity * loadFactor)，是由初始容量和填充因子共同决定的，当实际大小超过临界值时，HashMap会进行扩容。也就是说，默认情况下，当实际大小size大于threshold（16 * 0.75=12）时，会进行扩容。loadFactor：填充因子。默认值0.75是时间和空间的一个权衡。极端情况下，若对时间要求很高，对内存要求相对较低，可以降低此值；若内存要求很高，对时间要求相对较低，可以增加此值，甚至可以大于1。
本质上讲，这个参数主要是调整table大小与链表大小的关系。
下面通过一个例子分析下loadFactor和threshold的关系：
public static void main(String[] args) throws Exception {
Map<Integer, Integer> map = new HashMap<>(4, 0.75f);
map.put(0, 1);
/* 打印table的大小 */
Field field = map.getClass().getDeclaredField("table");
field.setAccessible(true);
Object table = field.get(map);
if (table!= null && table.getClass().isArray()) {
Object[] tables = (Object[]) table;
System.out.println(tables.length); // output: 4
}
/* 打印threshold的大小 */
Field t = map.getClass().getDeclaredField("threshold");
t.setAccessible(true);
int threshold = t.getInt(map);
System.out.println("threshold:" + threshold); // output: 3
map.put(1, 2);
map.put(2, 3);
map.put(3, 4);
/* 再次打印table的大小 */
table = field.get(map);
if (table!= null && table.getClass().isArray()) {
Object[] tables = (Object[]) table;
System.out.println(tables.length); // output: 8
}
}
从上述代码可以看出：
- 首先生成了一个初始容量为4，填充因子为0.75f的hashMap，此时，tableSize=4，threshold=4；
- 执行一次put操作，tableSize = 4, threshold=（4 × 0.75=3）；这时hashMap的最大容量为3；
- 再次执行3次put操作，超出了阈值(3)，因此会进行一次扩容，此时tableSize=8，threshold=(8 × 0.75=6)
3、方法
3.1 构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) // 容量判断
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 填充因子判断
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); // 不保留初始值，仅用来生成阈值
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
3.2 索引方法
对HashMap的操作，首先需要定位到哈希桶上。下面是具体的hash代码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看出，要确定具体桶的位置，需要三步运算：
- 第一步：取得key的hash码。即取key的hashCode值。
- 第二步：高位运算，为了避免hash碰撞(hash collisons)将高位分散到低位上，这是综合考虑了速度，性能等各方面因素之后做出的。
- 第三步：取模运算。
h & (length - 1)，这一步在put和get方法中，即在使用时才进行取模运算。
3.3 Put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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)
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) // -1 for 1st
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;
}
从代码看，插入的逻辑还是比较清晰的。首先判断表中没有空间，其次是根据索引值找到具体的位置。存在该Key的话就覆盖，如果是红黑树就直接插入，否则插入链表（判断重复Key值和红黑树转换）。具体的流程图如下：
3.4 Get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof HashMap.TreeNode)
return ((HashMap.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;
}
从代码来看，查找的逻辑同样比较清晰。具体流程图如下：
3.5 扩容方法
final HashMap.Node<K,V>[] resize() {
HashMap.Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { // 容量超过最大值，不再扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 扩容为原来的两倍
newThr = oldThr << 1; // double threshold
}
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);
}
if (newThr == 0) { // 计算新的threshold值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { // 将旧的bucket移动到新的bucket中
HashMap.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 HashMap.TreeNode) // 红黑树分裂，如果高度<=6，会退化为链表
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order，链表处理hash冲突
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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;
}
4、综述
- HashMap初始化的时候估算map大小并指定容量，这是因为频繁的扩容是非常耗资源的。
- HashMap线程不安全，并发环境下建议使用ConcurrentHashMap。
- JDK1.8 采用数组、链表+红黑树的存储结构，优化了HashMap的性能，具体对比不再阐释。
