HashMap 和 ConcurrentHashMap
HashMap 和 ConcurrentHashMap
HashMap
众所周知HashMap底层是基于数组和链表组成的。在JDK1.7和JDK1.8中具体实现稍有不同。
1.7
数据结构采用的是数组 + 链表
默认容量为16，负载因子为0.75。Map在使用过程中不断的往里面存放数据，当数量size达到16 * 0.75 = 12的时候，就需要将当前的容器（16）进行扩容，扩容至之前的两倍(newCap = oldCap << 1)。在扩容过程中涉及到了rehash，复制数据等操作。所以非常消耗性能。因此，通常在知道数据大小的情况下，尽量固定HashMap的大小，以此减少扩容带来的性能消耗。
通过源码可以看出数据是存储在
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是HashMap中的一个内部类，Key和Value值可以为空。
put方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
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++;
addEntry(hash, key, value, i);
return null;
}
- 判断当前数组是否需要初始化。
- 如果key为空，则put一个空值进去
- 根据key计算出hashcode。
- 根据计算出的hashcode定位出所在的桶。
- 如果桶是一个链表则需要遍历链表里面的hashcode,key是否和传入key相等。如果相等则进行覆盖，并返回原值。如果桶是空的，则表示当前位置没有数据存入，新增一个entry对象写入当前位置。（当调用addEntry写入Entry时，需要判断是否需要扩容，如果需要就进行两倍扩容，并将当前的key重新hash并定位。）
1.8
在1.7的实现中有个问题，当Hash冲突很严重的情况下，在桶上形成的链表会变得越来越长，这样在查询时效率就会越来越低。时间复杂度为O(N)。在1.8中对此进行了优化
1.8的数据结构 （数组 + 链表 + 红黑树）
和1.7不同的是：增加了一个判断是否将链表转换成红黑树的阈值。
put方法
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的hashcode定位到具体的桶中并判断是否为空，为空表示没有Hash冲突就直接在当前的位置创建一个新的数据链表。如果当前桶有值（Hash冲突），那么就要比较当前桶中的key、hashcode是否和传入的值相等。相等则赋值。
- 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
- 如果是链表，则将当前的key、value封装成新的节点写入当前链表的最后。
- 之后判断当前链表是否大于预设的阈值，大于时就要转化成红黑树。
- 最后判断是否需要进行扩容。
从put的核心方法可以看出1.8中对链表做了优化，修改了红黑树之后查询效率直接提高到了O(log N).
遍历方式
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
Map.Entry<String, Integer> next = entryIterator.next();
System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
String key = iterator.next();
System.out.println("key=" + key + " value=" + map.get(key));
}
建议使用第一种EntrySet进行遍历，这样可以同时获取Kay 和 Value。
线程安全
HashMap是非线程安全的，所以在多线程环境的情况下，建议使用ConcurrentHashMap。该类位于java.util.concurrent包下面。专门用于解决并发问题。
ConcurrentHashMap
结构图
如图所示，是由Segment数组、HashEntry组成，和HashMap一样，仍然是数组加链表。和HashMap非常类似，唯一的区别就是其中的核心数据如value，以及链表都是volatile修饰的，保证了获取时的可见性。
原理上来说，ConcurrentHashMap采用了分段锁结束，其中Segment继承于ReentrantLock。不会像HashTable那样不管是put还是get操作都是需要做同步处理，理论上ConcurrentHashMap支持CurrencyLevel（Segment数组数量）的线程并发。每当一个线程占用锁访问一个Segment时，不会影响到其他的Segment。首先是通过Key定位到Segment，之后在对应的Segment中进行具体的put。
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;
HashEntry<K,V> first = entryAt(tab, index);
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 {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
虽然HashEntry 中的value是用volatile关键词修饰的。但是并不能保证并发的原子性，所以put操作时仍然需要加锁处理。首先会尝试获取锁，如果获取失败则利用scanAndLockForPut()自旋获取锁。如果重试的次数达到MAX_SCAN_RETRIES则改为阻塞锁获取，保证能获取成功。
1.8
和1.7相比，1.8采用了1.8HashMap的结构，其中抛弃了原有的分段锁，采用了CAS + synchronized来保证并发安全性。 并将Node中的 next ， value 使用volatile修饰，保证了可见性。
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
- 根据Key计算出hashcode
- 判断是否需要进行初始化
- f则是当前key定位出的node,如果为空标示当前位置可以写入数据，利用CAS尝试写入，失败则自旋保证成功
- 如果当前位置的hashcode == MOVED == -1 则需要扩容
- 如果都不满足，则利用synchronized锁写入数据。
- 如果数据大于TREEIFY_THRESHOLD则要转换成红黑树。
Hashcode均匀分布
计算hashcode、高位运算和取模运算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}