面试的时候经常问到。这里对jdk1.7的HashMap和ConcurrentHashMap原理进行分析。下篇将详细分析jdk1.8的实现。
1 HashMap
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变（扩容的时候会变，后面会详细说明）。
1.1 成员结构
-
数组
采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1);通过给定值进行查找，需要对数组进行全部遍历，时间复杂度为O(n)；对一般的插入操作，涉及到数组元素的移动，平均复杂度为O(n)。
-
线性链表
对于链表的新增、删除操作(在找到指定操作位置后)，仅需要处理节点之间的引用即可，时间复杂度为O(1);查找的时候需要遍历整个链表。
-
二叉树
对一颗平衡的有序二叉树，插入、查找、删除。时间复杂度为O(logn)
-
哈希表
相比上诉几种数据结构，在哈希表中进行添加、删除、查找、性能十分的高，在不考虑hash冲突的情况下仅需要一次定位即可，时间复杂度为O(1)。
数据结构的物理存储结构只有两种：顺序存储和链式存储(像栈、队列、树、图等是从逻辑结构去抽象的，映射到内存中只有两种结构)。上面提到根据下标去查找数据，一次定位就可以找到，哈希表就是利用了这种特性。因此哈希表的主干就是数组。
hash冲突
两个数据可能取hash之后是相同的值，这样存储的时候就产生了hash碰撞。对于解决hash碰撞有多种方案：开放地址法(发生冲突，继续寻找下一块未被占用的存储地址)、再散列法、链地址法。HashMap就是采用了链地址法。
HashMap的主干就是一个数组(Entry),每一个Entry是一个(key,value)的键值对
//初始化一个Entry数组，数组的长度一定是2的次幂。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是HashMap的一个静态内部类，代码如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
HashMap结构图
如图，HashMap主干是Entry数组，纵向是链表结构。
其他几个重要字段：
//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;
1.2 构造函数
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;
threshold = initialCapacity;
init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}
1.3 put()原理
通过上面的构造函数发现，在初始化的时候没有个table分配内存，而是在put的时候才初始化分配内存。
public V put(K key, V value) {
//如果table数组为空数组，进行数组填充(为table分配实际内存空间)，
//入参为threshold，此时threshold为initialCapacity 默认是1<<4(16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
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++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}
先来看看inflateTable这个方法
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
//此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，
//capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
保证数组的长度是2的次幂
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
对key进行hash尽量让key分散，避免hash碰撞
//这是一个神奇的函数，用了很多的异或，移位等运算，
//对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();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
计算新插入数据的数组下标
/**
* 返回数组下标
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
我们可以想到的是取模运算就能分散到数组中，这里使用与运算(&)，因为与运算比取模快。
为什么他们会相等？
如下，假设数组长度是16，当前的hash(k)=17，取模计算后是index=1。这时候length-1=15,二进制运算如下，算出来的也是index=1。
0001 0001
& 0000 1111
---------------------
0000 0001 = 1
这就是HashMap在put的时候下标确定流程
put时数组下标确定
再来看看addEntry的实现：
void addEntry(int hash, K key, V value, int bucketIndex) {
//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
1.4 扩容原理
继续看看resize方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//把旧数据移入新的table中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
继续看transfer方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//for循环中的代码，逐个遍历链表，重新计算索引位置,
//将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//将当前entry的next链指向新的索引位置,newTable[i]有可能为空，
//有可能也是个entry链，如果是entry链，直接在链表头部插入。
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
transfer方法是在扩容的时候执行，把旧的table中的数据拷贝到新的table中。
为何HashMap的数组长度一定是2的次幂？
indexFor的时候是使用h&(length-1),这时候数组的长度是2的次幂。假如是16，这时候二进制是0001 0000，length-1后就是 0000 1111，做与运算的时候就只与低位有关。扩容后是32，length-1后是0001 1111，这样与
h求与运算就不会改变原来数据在数组中的位置。
总结就三个原因：
- 在计算数组下标的时候更快速
- h的高位对数组位置计算不产生影响
- 扩容的时候，不会改变原来已经散列好的数据在数组中的位置
1.5 get()原理
public V get(Object key) {
//如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
可以看出get方法是很简单的，具体流程就是先计算key的hash值，然后找到对应的table[i],然后遍历链表找到hash值相同的Entry,返回e.value()。
2 ConcurrentHashMap
在理解了HashMap的原理之后再来理解ConcurrentHashMap就简单很多。
1.1 成员结构
由 segment数组和多个HashEntry组成，如下图所示
数据结构
segment数组的意义是将一个大的table分割成多个小的table,使用的是锁分离技术。每个segment存储的是HashEntry数组+链表，这个就和HashMap的数据存储一样
初始化
int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
初始化的时候需要初始化segment的容量
1.2 put()原理
ConcurrentHashMap在进行数据插入的时候需要两次hash去定位数据的存储位置
/**
* map的put方法,定位segment
*/
public V put(K key, V value) {
Segment<K,V> s;
// value不能为空
if (value == null)
throw new NullPointerException();
// 获取hash
int hash = hash(key);
// 定位segments 数组的位置
int j = (hash >>> segmentShift) & segmentMask;
// 获取这个segment
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
// 为null 初始化当前位置的segment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
/**
* put到table方法
*/
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 是否获取锁,失败自旋获取锁(直到成功)
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
// 定义位置
int index = (tab.length - 1) & hash;
// 获取第一个桶的第一个元素
// entryAt 底层调用getObjectVolatile 具有volatile读语义
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) { // 证明链式结构有数据 遍历节点数据替换,直到e=null
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) { // 找到了相同的key
oldValue = e.value;
if (!onlyIfAbsent) { // 默认值false
e.value = value; // 替换value
++modCount;
}
break; // 结束循环
}
e = e.next;
}
else { // e=null (1) 之前没有数据 (2) 没有找到替换的元素
// node是否为空,这个获取锁的是有关系的
// (1) node不为null,设置node的next为first
// (2) node为null,创建头节点,指定next为first
if (node != null)
// 底层使用 putOrderedObject 方法 具有volatile写语义
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 扩容条件 (1)entry数量大于阈值 (2) 当前table的数量小于最大容量 满足以上条件就扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
// 扩容方法,方法里面具体讲
rehash(node);
else
// 给table的index位置设置为node,
// node为头结点,原来的头结点first为node的next节点
// 底层也是调用的 putOrderedObject 方法 具有volatile写语义
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
segment继承自ReentrantLock，因此带有锁的功能，当在put数据的时候，
1：先获取对应segment的位置(第一次hash)
2：获取segment的锁，如果获取到锁，再计算在HashEntry数组中的位置(第二次hash)，添加到链表的尾部。
1.3 get()原理
ConcurrentHashMap的get操作跟HashMap类似，只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回null
/**
* get 方法
*/
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; // 获取segment的位置
// getObjectVolatile getObjectVolatile语义读取最新的segment,获取table
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
// getObjectVolatile getObjectVolatile语义读取最新的hashEntry,并遍历
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
// 找到相同的key 返回
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
1.4 扩容原理
/**
*扩容方法
*/
private void rehash(HashEntry<K,V> node) {
// 旧的table
HashEntry<K,V>[] oldTable = table;
// 旧的table的长度
int oldCapacity = oldTable.length;
// 扩容原来capacity的一倍
int newCapacity = oldCapacity << 1;
// 新的阈值
threshold = (int)(newCapacity * loadFactor);
// 新的table
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
// 新的掩码
int sizeMask = newCapacity - 1;
// 遍历旧的table
for (int i = 0; i < oldCapacity ; i++) {
// table中的每一个链表元素
HashEntry<K,V> e = oldTable[i];
if (e != null) { // e不等于null
HashEntry<K,V> next = e.next; // 下一个元素
int idx = e.hash & sizeMask; // 重新计算位置,计算在新的table的位置
if (next == null) // Single node on list 证明只有一个元素
newTable[idx] = e; // 把当前的e设置给新的table
else { // Reuse consecutive sequence at same slot
HashEntry<K,V> lastRun = e; // 当前e
int lastIdx = idx; // 在新table的位置
for (HashEntry<K,V> last = next;
last != null;
last = last.next) { // 遍历链表
int k = last.hash & sizeMask; // 确定在新table的位置
if (k != lastIdx) { // 头结点和头结点的next元素的节点发生了变化
lastIdx = k; // 记录变化位置
lastRun = last; // 记录变化节点
}
}
// 以下把链表设置到新table分为两种情况
// (1) lastRun 和 lastIdx 没有发生变化,也就是整个链表的每个元素位置和一样,都没有发生变化
// (2) lastRun 和 lastIdx 发生了变化,记录变化位置和变化节点,然后把变化的这个节点设置到新table
// ,但是整个链表的位置只有变化节点和它后面关联的节点是对的
// 下面的这个遍历就是处理这个问题,遍历当前头节点e,找出不等于变化节点(lastRun)的节点重新处理
newTable[lastIdx] = lastRun;
// Clone remaining nodes
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
// 处理扩容时那个添加的节点
// 计算位置
int nodeIndex = node.hash & sizeMask; // add the new node
// 设置next节点,此时已经扩容完成,要从新table里面去当前位置的头结点为next节点
node.setNext(newTable[nodeIndex]);
// 设置位置
newTable[nodeIndex] = node;
// 新table替换旧的table
table = newTable;
}
