HashMap深度历险

一个面试题：
往HashMap中存100个元素，问：HashMap的初始化大小是多少最合适？

HashMap概述：
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null键和null值。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构：
在java编程语言中，最基本的数据结构就只有两种，一种是数组，另一种是模拟指针（地址引用），其他的复杂数据结构，如二叉树、图，我目前是没见过相应实现。在java中，所有的高级数据结构都可以通过这两种基本结构来构造。HashMap也不例外。

HashMap实际上是一个数组和链表构成的散列表，如图：

HashMap深度历险

从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。
但HashMap为什么需要链表呢？这是为了解决哈希冲突。什么是哈希冲突？我们知道，不同的Object的hashCode可能相同，这就会出现同义词，同义词会竞争同一个存储位置。常用的哈希冲突解决方法有开放地址法、重哈希、拉链法。
HashMap在这里所采用的就是拉链法。简单地说，拉链法就是将同义词（产生哈希冲突的元素）连接在同一个单链表中。

HashMap初始化源码：

public class HashMap {
Entry[] table;
…
public HashMap(int initialCapacity, float loadFactor) {
… .
table = new Entry[capacity];
}
…
static class Entry{
final K key;
V value;
Entry next;
final int hash;
…
}
}

从源码可以看出，Entry就是数组中的元素，每个Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用next，这就是解决哈希冲突的关键。由它生成一张单链表。
下面说说最重要的方法put与get方法：
先看源码：

public V put(K key, V value) {
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
addEntry(hash, key, value, i);
}

void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
}

Entry构造函数：

Entry ( int h, K k, V v, Entry n) {
value = v; next = n; key = k; hash = h;
}

不难看出，put做了两件事：
1，遍历Entry链表，如果找到跟key“相同”的旧key，则覆盖旧值。这里的“相同”指hash值相同、内容相同（即equals返回true）
2，若没有找到“相同”的旧key，则用key、value构造新的Entry插入到链表的表头，让其next指向原来的Entry。

public V get(Object key) {
int hash = hash(key.hashCode());
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
}

从上面的代码可以看出，从HashMap中get元素时，首先计算key的hasCode，找到数组中对应位置的Entry，然后遍历Entry链表，直到找到key.equals(k)返回true的元素，完成。
而我们知道，链表的查询是相当耗时的(大小同为n的数组和链表，时间复杂度分别为1和(n+1)/2 ) ，所以我们希望HashMap的元素尽可能的分布均匀些，尽可能少的产生哈希冲突，这样就不必构造单链表。怎样达到“均匀分布”呢？我们首相想到的是把hash值对数组长度取模运算，这样，元素的分布相对来说是比较均匀的。但是模运算比较耗性能，HashMap是这样做的：int i = indexFor(hash, table.length);
i 就是元素的下标，indexFor的实现：

static int indexFor(int h, int length) {
return h & (length-1);
}

所以，为了让下标i均匀地分布，我们必须让h & (length-1)尽可能少地产生哈希冲突。所以，我们初始化HashMap的大小直接影响着HashMap的性能。
举个例子：假如数组的长度为15，两个元素的hash值分别为8、9，计算h & (length-1)的结果，
8：1000 & 1110 = 1000
9：1001 & 1110 = 1000
所以，8、9产生哈希冲突，成为同义词，他们将利用拉链法生成单链表，影响性能，而更糟的是，0001、0011、0101、1001、1011、0111、1101这几个位置永远无法利用，空间浪费相当大，可使用的位置非常少，进一步增加了冲突的几率。
而如果数组的长度为16， h & (length-1)情况如下：
8：1000 & 1111 = 1000
9：1001 & 1111 = 1001
不同的hash值将产生不同的数组下标，有效地避免了hash冲突。这就是我们为什么要将HashMap的初始化大小设置为2的n次方的缘故。即使我们不指定大小或指定大小为非2的n次方，HasMap也会暗中帮我们转化为2的n次方：

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1

所以，100个元素，new HashMap（？）

HashMap的扩容
当HashMap中的元素越来越多时，哈希冲突的机遇就越来越高（因为数组的长度是固定的，大部分位置已经被占有），所以为了提高查询效率，就要对HashMap的数组进行扩容。可能有人怀疑其性能，因为HashMap扩容之后，会发生resize操作，即：原数组中的元素必须重新计算其在新数组中的位置，并且放进去。但考虑到链表查询的时间复杂度和resize的时间复杂度，不难做出选择。

那HashMap什么时候进行扩容？在HashMap中有一个loadFactor（加载因子），当元素个数超过数组大小loadFactor时，就会进行扩容。loadFactor的默认值为0.75（对空间和时间效率的一个平衡选择），也就是说，默认情况下，数组大小为16，当HashMap中元素个数超过160.75=12时，就会把数组的大小扩展为162=32，然后重新计算每个元素在新数组中的位置。这是一个耗性能的操作，也要尽量避免。所以如果我们已经知道元素的个数，初始化时设置相应的大小能有效地提高HashMap的性能。
回到本文开头，现在有100个元素，new HashMap时，首先考虑避免哈希冲突，我们会new HashMap(128)，但这还不是最合适的大小，因为0.75128=96<100，即，put第96个元素时，会自动进行扩容，所以，为了避免扩容的resize带来的影响，我们最好设置new HashMap(256)。