1.概述
HashMap是JDK集合(collection)的重要类。它和Hashtable都是利用散列(Hash)算法实现在内存快速查找元素的功能（实现Key -> value的映射）。理论上，在HashMap的查找效率是O(1)，但这是在理想情况下效率,实际的效率跟怎么处理散列冲突的算法有关系。HashMap和Hashtable的区别这里就不阐述了。
2.影响hash算法效率的关键点
实现Hash算法，主要有几个关键点：
2.1 散列函数的选择
最理想的散列函数是把每个key均匀分布在每个桶(bucket)上，不产生冲突，这样能够保证查找的效率是O(1)。不过这是不可能的，只能尽可能的均匀分布。
2.2 装填因子 (Load factor)
装填因子 = key的个数 / 散列表的长度(桶的个数)
理论上，装填因子越小，出现冲突的可能性越小。但是也要考虑到空间的影响，因为这个散列是存放在内存的，装填因子越小，对空间的浪费越大。而且还记得学概率的时候那个经典的同班同学必然有2个同一天生日的问题吗？靠减小装填因子是没办法解决冲突的。
根据经验值，装填因子是0.7左右是比较合适的，HashMap的实现采用的是0.75
2.3 冲突解决 (Collision Resolution)
冲突是指当不同的key通过散列函数计算得到同样的值。
既然冲突不可避免，怎么解决冲突是关键。常见的解决办法有分离链接(separate chaning)，开放定址(open addressing), 合并散列(Coalesced hashing)等。
HashMap使用的是分离链接。分离链接是最容易实现的一种算法，大体的思路就是把产生冲突的Key都放到一个链表里面。插入和查找的时候，如果发现对应桶的链表的长度大于1，需要遍历该链表。
2.4 再散列(rehashing)
当散列的key越来越多的时候，装填因子越来越大，整体性能会下降，这时候会涉及到再散列的问题。再散列的目的是为了让装填因子保持在一个限额。再散列的算法跟所使用的冲突解决办法有关系。因为HashMap使用了分离链接解决冲突，再散列的实现也相对比较简单。
3. HashMap的源码分析
这里针对上面提到的几个关键点，来分析HashMap的具体实现。
3.1 散列函数的选择
虽然java里面每个对象都有hashcode方法返回一个hash的整型值。但是HashMap不是直接用key对象的hashcode，而是首先做了一次补充的散列处理：
int hash = hash(key.hashCode());
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
补从散列的目的是避免key对象的hashcode方法可能是一个很烂的hash质量（因为不同类的hashcode方法可能会被重写），减少冲突。而HashMap的长度总是2的p次幂，这样的处理也有助于减少冲突的可能性。
这个文章讨论了JDK1.4 hash方法的一些问题，http://www.javaspecialists.co.za/archive/Issue054.html
通过hash函数获得hash过的值之后，还需要根据这个值映射到对应的桶上：
static int indexFor(int h, int length) {
return h & (length-1);
}
这方法相当于对length取模，也就是 h % 2^p。
通过这两步的处理，实现了HashMap的散列函数
3.2 冲突解决 (Collision Resolution)
前面提到HashMap的冲突解决是通过分离链接(separate chaning)。也就是每个桶是一个单向链表。
下面是put方法处理冲突的代码：
/*
for循环的目的是遍历桶的链表，如果当前的key已经存在，就替换value
*/
for (Entry<K,V> 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;
}
}
/*
modCount是为了使用迭代器的过程中有其他线程修改了map
那么将抛出oncurrentModificationException
*/
modCount++;
/*
addEntry是把key,value插入到桶中
*/
addEntry(hash, key, value, i);
taible[i]就是hash过后的桶，Entry就是链表的元素，一个典型的单向链表的定义：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
.....
}
3.3 再散列
不像开放地址法，基于分离链接的HashMap的再散列比较简单。只要元素的个数大于阀值，就把桶的size增加一倍，保证装载因子保持在0.75以下。
if (size++ >= threshold)
resize(2 * table.length);
