从多个角度了解HashMap。
转载一个关于HashMap不错的讲解，作者通过图形的方式很生动的把hashmap的源码解释出来。
http://www.cnblogs.com/ITtangtang/p/3948406.html
下面是本人对HashMap源码的理解：
一、HashTable与HashMap的区别：
1.1 历史
HashMap的出现时间要晚于HashTable。
HashTable在JDK1.1 版本时就已经出现，之后在JDK1.2 才出现了HashMap。
1.2 实现的接口
从图中可以看出，
- 两者都实现了Map、Cloneable、Seriallizable接口
- 但继承的抽象类是不一样的， HashMap 继承了AbstractMap 而 HashTable 继承的是已经 废弃 的 Dictionary 类
- 从两者提供的方法可以看出，这两个类的功能是一样的，都可以对键值对进行增删改查，遍历，序列化和拷贝。
1.2.1 关于空的键值对
//HashTable关于put的源码及注释
public synchronized V put(K key, V value) {
// 如果value为null，抛出NullPointerException
if (value == null) {
throw new NullPointerException();
}
// 如果key为null，在调用key.hashCode()时抛出NullPointerException
// ...
}
//HasMap关于put的源码及注释
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 当key为null时，调用putForNullKey特殊处理
if (key == null)
return putForNullKey(value);
// ...
}
private V putForNullKey(V value) {
// key为null时，放到table[0]也就是第0个bucket中
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}通过源码我们看出， HashMap 是支持 空的（null）键值对 的，当遇到null时将null转化成hashCode值0，而 HashTable 在遇到null时，会抛出 NullPointerException 异常。
1.3 实现的原理
下面我们深入到数据结构和算法层来分析一下两者间的区别。
1.3.1 数据结构
HashTable 和 HashMap 在数据结构上两者是相同的，都使用哈希表来存储键值对，继承自Map.Entry中的Entry类，每一个Entry对象对应哈希表中的一个键值对。
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
//Map.Entry源码
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}可以说有多少的 键值对 就有多少的 Entry对象
下图说明HashTable 和 HashMap 如何存储键值对。
上图可以看出，哈希值相等的话，entry对象就以链表（HashMap在JDK1.8之后优化为红黑树）的形式进行存储。
//HashTable
private transient Entry<K,V>[] table;
//HashMap
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;得出结论HashTable 和 HashMap 内部使用 Entry数组 进行 键值对 的存储。
1.3.2 算法
下面一部分我们研究一下 HashTable 和 HashMap 在底层初始化和将给定的key映射到对应hash值上的算法，从而发现两者之间的异同。
初始化与扩容：
// HashTable
// 哈希表默认初始大小为11
public Hashtable() {
this(11, 0.75f);
}
protected void rehash() {
int oldCapacity = table.length;
Entry<K,V>[] oldMap = table;
// 每次扩容为原来的2n+1
int newCapacity = (oldCapacity << 1) + 1;
// ...
}
// HashMap
// 哈希表默认初始大小为2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
void addEntry(int hash, K key, V value, int bucketIndex) {
// 每次扩充为原来的2n
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
}从源码我们发现，HashTable 每次初始化为11，每次扩容为2n+1。而 HashMap 初始化为16，每次扩容为原来的2倍。还有一点就是，HashTable 如果你给定大小，那么其初始化时将按照你 给定的大小 来确定容量，但是HashMap 的大小为你给定大小的 2的幂次方。
在效率上HashMap 的方式直接使用位运算来得到结果更高效，但会因此造成hash表分布的不均匀，
如何定位到 hash桶：
// HashTable
// hash 不能超过Integer.MAX_VALUE 所以要取其最小的31个bit
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
// 直接计算key.hashCode()
private int hash(Object k) {
// hashSeed will be zero if alternative hashing is disabled.
return hashSeed ^ k.hashCode();
}
// HashMap
int hash = hash(key);
int i = indexFor(hash, table.length);
// 在计算了key.hashCode()之后，做了一些位运算来减少哈希冲突
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 取模不再需要做除法
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 :
// "length must be a non-zero power of 2";
return h & (length-1);
}1.4 线程安全
//HashTable
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
public Set<K> keySet() {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}通过上面关于 HashTable 的源码我们发现，HashTable公开的方法，比如get都使用了 synchronized 描述符。而遍历视图，比如keySet都使用了Collections.synchronizedXXX 进行了同步包装。在多线程状态下是同步的，而 HashMap 是不同步的。
1.5 HashTable已经被淘汰
以下描述来自于HashTable的类注释：
If a thread-safe implementation is not needed, it is recommended to
use HashMap in place of Hashtable. If a thread-safe highly-concurrent
implementation is desired, then it is recommended to use
java.util.concurrent.ConcurrentHashMap in place of Hashtable
在不考虑线程安全的情况下，就使用HashMap，反之使用ConcurrentHashMap。HashTable已经被淘汰了，不要在新的代码中再使用它。
二、ConcurrentHashMap与HashMap的区别：
2.1 ConcurrentHashMap
对于一般的增删改查，ConcurrentHashMap 的设计思路和 HashMap 是基本相同的，只是，ConcurrentHashMap 由一个个 segment（部分/一段） 也可以叫做 分段锁 。可以这么理解，ConcurrentHashMap 由一个 segment数组 组成，每一个 segment 继承了 ReentrantLock锁 ，这样可以确保每一个 segment 都是加锁的，以保证线程安全。
2.2 ConcurrentHashMap的初始化
ConcurrentHashMap 在默认初始化的时候就拥有有 16 个 Segments，也就是说默认情况下，支持最多16 个线程并发写入，如果初始化设置为其他值之后，便不可以扩容了。
//initialCapacity：初始容量，这个值指的是整个 ConcurrentHashMap
//的初始容量，实际操作的时候需要平均分给每个 Segment。
//loadFactor：负载因子，由于Segment 数组不可以扩容，
//所以这个负载因子是给每个 Segment 内部使用的。
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0;
int ssize = 1;
// 计算并行级别 ssize，因为要保持并行级别是 2 的 n 次方
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
// 我们这里先不要那么烧脑，用默认值，concurrencyLevel 为 16，sshift 为 4
// 那么计算出 segmentShift 为 28，segmentMask 为 15，后面会用到这两个值
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// initialCapacity 是设置整个 map 初始的大小，
// 这里根据 initialCapacity 计算 Segment 数组中每个位置可以分到的大小
// 如 initialCapacity 为 64，那么每个 Segment 或称之为"槽"可以分到 4 个
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
// 默认 MIN_SEGMENT_TABLE_CAPACITY 是 2，这个值也是有讲究的，因为这样的话，对于具体的槽上，
// 插入一个元素不至于扩容，插入第二个的时候才会扩容
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// 创建 Segment 数组，
// 并创建数组的第一个元素 segment[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
// 往数组写入 segment[0]
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}这样 ConcurrentHashMap 便算是完成了初始化。
2.3 ConcurrentHashMap 和 HashMap 的 put 和 get 方法对比
2.3.1 ConcurrentHashMap的put方法过程
- put的第一步：
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
// 1. 计算 key 的 hash 值
int hash = hash(key);
// 2. 根据 hash 值找到 Segment 数组中的位置 j
// hash 是 32 位，无符号右移 segmentShift(28) 位，剩下低 4 位，
// 然后和 segmentMask(15) 做一次与操作，
// 也就是说 j 是 hash 值的最后 4 位，也就是槽的数组下标
int j = (hash >>> segmentShift) & segmentMask;
// 刚刚说了，初始化的时候初始化了 segment[0]，但是其他位置还是 null，
// ensureSegment(j) 对 segment[j] 进行初始化
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
// 3. 插入新值到 槽 s 中
return s.put(key, hash, value, false);
}- Segment内部初始化，由数组+链表组成
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 在往该 segment 写入前，需要先获取该 segment 的独占锁
// 先看主流程，后面还会具体介绍这部分内容
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
// 这个是 segment 内部的数组
HashEntry<K,V>[] tab = table;
// 再利用 hash 值，求应该放置的数组下标
int index = (tab.length - 1) & hash;
// first 是数组该位置处的链表的表头
HashEntry<K,V> first = entryAt(tab, index);
// 下面这串 for 循环虽然很长，不过也很好理解，想想该位置没有任何元素和已经存在一个链表这两种情况
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
// 覆盖旧值
e.value = value;
++modCount;
}
break;
}
// 继续顺着链表走
e = e.next;
}
else {
// node 到底是不是 null，这个要看获取锁的过程，不过和这里都没有关系。
// 如果不为 null，那就直接将它设置为链表表头；如果是null，初始化并设置为链表表头。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 如果超过了该 segment 的阈值，这个 segment 需要扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node); // 扩容后面也会具体分析
else
// 没有达到阈值，将 node 放到数组 tab 的 index 位置，
// 其实就是将新的节点设置成原链表的表头
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 解锁
unlock();
}
return oldValue;
}- ensureSegment：初始化segment
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
// 这里看到为什么之前要初始化 segment[0] 了，
// 使用当前 segment[0] 处的数组长度和负载因子来初始化 segment[k]
// 为什么要用“当前”，因为 segment[0] 可能早就扩容过了
Segment<K,V> proto = ss[0];
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
// 初始化 segment[k] 内部的数组
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // 再次检查一遍该槽是否被其他线程初始化了。
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
// 使用 while 循环，内部用 CAS，当前线程成功设值或其他线程成功设值后，退出
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}- scanAndLockForPut：获取写入锁
前面 segment 的 put 方法中，第一步就调用 node = tryLock() ? null : scanAndLockForPut(key, hash, value)，
也就是说先进行一次 tryLock() 快速获取该 segment 的独占锁，如果失败，那么进入到 scanAndLockForPut 这个方法来获取锁。
scanAndLockForPut如何加锁
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
int retries = -1; // negative while locating node
// 循环获取锁
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
if (retries < 0) {
if (e == null) {
if (node == null) // speculatively create node
// 进到这里说明数组该位置的链表是空的，没有任何元素
// 当然，进到这里的另一个原因是 tryLock() 失败，所以该槽存在并发，不一定是该位置
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))
retries = 0;
else
// 顺着链表往下走
e = e.next;
}
// 重试次数如果超过 MAX_SCAN_RETRIES（单核1多核64），那么不抢了，进入到阻塞队列等待锁
// lock() 是阻塞方法，直到获取锁后返回
else if (++retries > MAX_SCAN_RETRIES) {
lock();
break;
}
else if ((retries & 1) == 0 &&
// 这个时候是有大问题了，那就是有新的元素进到了链表，成为了新的表头
// 所以这边的策略是，相当于重新走一遍这个 scanAndLockForPut 方法
(f = entryForHash(this, hash)) != first) {
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}这个方法有两个出口，一个是 tryLock() 成功了，循环终止，另一个就是重试次数超过了 MAX_SCAN_RETRIES，进到 lock() 方法，此方法会阻塞等待，直到成功拿到独占锁。