深入并发包 ConcurrentHashMap

原文出处: pettyandydog
前言
以前写过介绍HashMap的文章,文中提到过HashMap在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。

我们来了解另一个键值存储集合HashTable,它是线程安全的,它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table,这就意味着所有的线程都在竞争一把锁,在多线程的环境下,它是安全的,但是无疑是效率低下的。

其实HashTable有很多的优化空间,锁住整个table这么粗暴的方法可以变相的柔和点,比如在多线程的环境下,对不同的数据集进行操作时其实根本就不需要去竞争一个锁,因为他们不同hash值,不会因为rehash造成线程不安全,所以互不影响,这就是锁分离技术,将锁的粒度降低,利用多个锁来控制多个小的table,这就是这篇文章的主角ConcurrentHashMap JDK1.7版本的核心思想。

ConcurrentHashMap
JDK1.7的实现
在JDK1.7版本中,ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成,如下图所示:

Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁,也就是上面的提到的锁分离技术,而每一个Segment元素存储的是HashEntry数组+链表,这个和HashMap的数据存储结构一样

初始化
ConcurrentHashMap的初始化是会通过位与运算来初始化Segment的大小,用ssize来表示,如下所示

int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}

如上所示,因为ssize用位于运算来计算(ssize <<=1),所以Segment的大小取值都是以2的N次方,无关concurrencyLevel的取值,当然concurrencyLevel最大只能用16位的二进制来表示,即65536,换句话说,Segment的大小最多65536个,没有指定concurrencyLevel元素初始化,Segment的大小ssize默认为16

每一个Segment元素下的HashEntry的初始化也是按照位于运算来计算,用cap来表示,如下所示

int cap = 1;
while (cap < c)
cap <<= 1;
如上所示,HashEntry大小的计算也是2的N次方(cap <<=1), cap的初始值为1,所以HashEntry最小的容量为2

put操作
对于ConcurrentHashMap的数据插入,这里要进行两次Hash去定位数据的存储位置

1
static class Segment extends ReentrantLock implements Serializable {
从上Segment的继承体系可以看出,Segment实现了ReentrantLock,也就带有锁的功能,当执行put操作时,会进行第一次key的hash来定位Segment的位置,如果该Segment还没有初始化,即通过CAS操作进行赋值,然后进行第二次hash操作,找到相应的HashEntry的位置,这里会利用继承过来的锁的特性,在将数据插入指定的HashEntry位置时(链表的尾端),会通过继承ReentrantLock的tryLock()方法尝试去获取锁,如果获取成功就直接插入相应的位置,如果已经有线程获取该Segment的锁,那当前线程会以自旋的方式去继续的调用tryLock()方法去获取锁,超过指定次数就挂起,等待唤醒。

get操作
ConcurrentHashMap的get操作跟HashMap类似,只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置,然后再hash定位到指定的HashEntry,遍历该HashEntry下的链表进行对比,成功就返回,不成功就返回null。

size操作
计算ConcurrentHashMap的元素大小是一个有趣的问题,因为他是并发操作的,就是在你计算size的时候,他还在并发的插入数据,可能会导致你计算出来的size和你实际的size有相差(在你return size的时候,插入了多个数据),要解决这个问题,JDK1.7版本用两种方案。

try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j) ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment seg = segmentAt(segments, j);
if (seg != null) { sum += seg.modCount; int c = seg.count; if (c < 0 || (size += c) RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size,最多三次,比较前后两次计算的结果,结果一致就认为当前没有元素加入,计算的结果是准确的;
第二种方案是如果第一种方案不符合,他就会给每个Segment加上锁,然后计算ConcurrentHashMap的size返回。
JDK1.8的实现
JDK1.8的实现已经摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap,虽然在JDK1.8中还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本。

在深入JDK1.8的put和get实现之前要知道一些常量设计和数据结构,这些是构成ConcurrentHashMap实现结构的基础,下面看一下基本属性:

// node数组最大容量:2^30=1073741824
private static final int MAXIMUM_CAPACITY = 1 < 8 链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//树转链表阀值,小于等于6(tranfer时,lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量,<=UNTREEIFY_THRESHOLD 则untreeify(lo))
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
private static final int MIN_TRANSFER_STRIDE = 16;
private static int RESIZE_STAMP_BITS = 16;
// 2^15-1,help resize的最大线程数
private static final int MAX_RESIZERS = (1 < h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir = 0) { //表示该节点是链表结构
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
//这里涉及到相同的key进行put就会覆盖原先的value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node pred = e;
if ((e = e.next) == null) { //插入链表尾部
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {//红黑树结构
Node p;
binCount = 2;
//红黑树结构旋转插入
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) { //如果链表的长度大于8时就会进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);//统计size,并且检查是否需要扩容
return null;
}
这个put的过程很清晰,对当前的table进行无条件自循环直到put成功,可以分成以下六步流程来概述。

如果没有初始化就先调用initTable()方法来进行初始化过程
如果没有hash冲突就直接CAS插入
如果还在进行扩容操作就先进行扩容
如果存在hash冲突,就加锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入,
最后一个如果该链表的数量大于阈值8,就要先转换成黑红树的结构,break再一次进入循环
如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容
现在我们来对每一步的细节进行源码分析,在第一步中,符合条件会进行初始化操作,我们来看看initTable()方法

/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node[] initTable() {
Node[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {//空的table才能进入初始化操作
if ((sc = sizeCtl) >> 2);//记录下次扩容的大小
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
在第二步中没有hash冲突就直接调用Unsafe的方法CAS插入该元素,进入第三步如果容器正在扩容,则会调用helpTransfer()方法帮助扩容,现在我们跟进helpTransfer()方法看看

/**
*帮助从旧的table的元素复制到新的table中
*/
final Node[] helpTransfer(Node[] tab, Node f) {
Node[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode)f).nextTable) != null) { //新的table nextTba已经存在前提下才能帮助扩容
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) >> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node[] nt = (Node[])new Node[n <= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) stride ?
nextIndex – stride : 0))) {
bound = nextBound;
i = nextIndex – 1;
advance = false;
}
}
if (i = n || i + n >= nextn) {
int sc;
// 已经完成所有节点复制了
if (finishing) {
nextTable = null;
table = nextTab; // table 指向nextTable
sizeCtl = (n > 1); // sizeCtl阈值为原来的1.5倍
return; // 跳出死循环,
}
// CAS 更扩容阈值,在这里面sizectl值减一,说明新加入一个线程参与到扩容操作
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc – 1)) {
if ((sc – 2) != resizeStamp(n) <= 0 ,表示为链表节点
if (fh >= 0) {
// 构造两个链表 一个是原链表 另一个是原链表的反序排列
int runBit = fh & n;
Node lastRun = f;
for (Node p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node(ph, pk, pv, ln);
else
hn = new Node(ph, pk, pv, hn);
}
// 在nextTable i 位置处插上链表
setTabAt(nextTab, i, ln);
// 在nextTable i + n 位置处插上链表
setTabAt(nextTab, i + n, hn);
// 在table i 位置处插上ForwardingNode 表示该节点已经处理过了
setTabAt(tab, i, fwd);
// advance = true 可以执行–i动作,遍历节点
advance = true;
}
// 如果是TreeBin,则按照红黑树进行处理,处理逻辑与上面一致
else if (f instanceof TreeBin) {
TreeBin t = (TreeBin)f;
TreeNode lo = null, loTail = null;
TreeNode hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode p = new TreeNode
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 扩容后树节点个数若<=6,将树转链表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
扩容过程有点复杂,这里主要涉及到多线程并发扩容,ForwardingNode的作用就是支持扩容操作,将已处理的节点和空节点置为ForwardingNode,并发处理时多个线程经过ForwardingNode就表示已经遍历了,就往后遍历,下图是多线程合作扩容的过程:

介绍完扩容过程,我们再次回到put流程,在第四步中是向链表或者红黑树里加节点,到第五步,会调用treeifyBin()方法进行链表转红黑树的过程。

private final void treeifyBin(Node[] tab, int index) {
Node b; int n, sc;
if (tab != null) {
//如果整个table的数量小于64,就扩容至原来的一倍,不转红黑树了
//因为这个阈值扩容可以减少hash冲突,不必要去转红黑树
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n <= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode hd = null, tl = null;
for (Node e = b; e != null; e = e.next) {
//封装成TreeNode
TreeNode p =
new TreeNode(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
//通过TreeBin对象对TreeNode转换成红黑树
setTabAt(tab, index, new TreeBin(hd));
}
}
}
}
}
到第六步表示已经数据加入成功了,现在调用addCount()方法计算ConcurrentHashMap的size,在原来的基础上加一,现在来看看addCount()方法。

private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//更新baseCount,table的数量,counterCells表示元素个数的变化
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
//如果多个线程都在执行,则CAS失败,执行fullAddCount,全部加入count
if (as == null || (m = as.length – 1) = 0) {
Node[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) > RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
//当前线程发起库哦哦让操作,nextTable=null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs < 0 &&
(e = tabAt(tab, (n – 1) & h)) != null) {//读取首节点的Node元素
if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//hash值为负值表示正在扩容,这个时候查的是ForwardingNode的find方法来定位到nextTable来
//查找,查找到就返回
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode,那就往下遍历
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ConcurrentHashMap的get操作的流程很简单,也很清晰,可以分为三个步骤来描述

计算hash值,定位到该table索引位置,如果是首节点符合就返回
如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回
以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null
size操作
最后我们来看下例子中最后获取size的方式int size = map.size();,现在让我们看下size()方法

public int size() {
long n = sumCount();
return ((n (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a; //变化的数量
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
在JDK1.8版本中,对于size的计算,在扩容和addCount()方法就已经有处理了,JDK1.7是在调用size()方法才去计算,其实在并发集合中去计算size是没有多大的意义的,因为size是实时在变的,只能计算某一刻的大小,但是某一刻太快了,人的感知是一个时间段,所以并不是很精确。

总结与思考
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言,ConcurrentHashMap只是增加了同步的操作来控制并发,从JDK1.7版本的ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言,总结如下思考:

JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点)
JDK1.8版本的数据结构变得更加简单,使得操作也更加清晰流畅,因为已经使用synchronized来进行同步,所以不需要分段锁的概念,也就不需要Segment这种数据结构了,由于粒度的降低,实现的复杂度也增加了
JDK1.8使用红黑树来优化链表,基于长度很长的链表的遍历是一个很漫长的过程,而红黑树的遍历效率是很快的,代替一定阈值的链表,这样形成一个最佳拍档
JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock,我觉得有以下几点:
因为粒度降低了,在相对而言的低粒度加锁方式,synchronized并不比ReentrantLock差,在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界,更加的灵活,而在低粒度中,Condition的优势就没有了
JVM的开发团队从来都没有放弃synchronized,而且基于JVM的synchronized优化空间更大,使用内嵌的关键字比使用API更加自然
在大量的数据操作下,对于JVM的内存压力,基于API的ReentrantLock会开销更多的内存,虽然不是瓶颈,但是也是一个选择依据
参考
http://blog.csdn.net/u010412719/article/details/52145145
http://www.jianshu.com/p/e694f1e868ec
https://my.oschina.net/liuxiaomian/blog/880088
https://bentang.me/tech/2016/12/01/jdk8-concurrenthashmap-1/
http://cmsblogs.com/?p=2283

Java8系列之重新认识HashMap

简介

Java为数据结构中的映射定义了一个接口java.util.Map,此接口主要有四个常用的实现类,分别是HashMap、Hashtable、LinkedHashMap和TreeMap,类继承关系如下图所示:

java.util.map类图

下面针对各个实现类的特点做一些说明:

(1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

(2) Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

通过上面的比较,我们知道了HashMap是Java的Map家族中一个普通成员,鉴于它可以满足大多数场景的使用条件,所以是使用频度最高的一个。下文我们主要结合源码,从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

内部实现

搞清楚HashMap,首先需要知道HashMap是什么,即它的存储结构-字段;其次弄明白它能干什么,即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。

存储结构-字段

从结构实现来讲,HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,如下如所示。

hashMap内存结构图

这里需要讲明白两个问题:数据底层具体存储的是什么?这样的存储方式有什么优点呢?

(1) 从源码可知,HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组。我们来看Node[JDK1.8]是何物。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node
        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。

(2) HashMap就是使用哈希表来存储的。哈希表为解决冲突,可以采用开放地址法和链地址法等来解决问题,Java中HashMap采用了链地址法。链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。例如程序执行下面代码:

1
map.put("美团","小美");

系统将调用”美团”这个key的hashCode()方法得到其hashCode 值(该方法适用于每个Java对象),然后再通过Hash算法的后两步运算(高位运算和取模运算,下文有介绍)来定位该键值对的存储位置,有时两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。

如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。

在理解Hash和扩容流程之前,我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知,构造函数就是对下面几个字段进行初始化,源码如下:

1
2
3
4
int threshold;             // 所能容纳的key-value对极限
final float loadFactor;    // 负载因子
int modCount; 
int size;

首先,Node[] table的初始化长度length(默认值是16),Load factor为负载因子(默认值是0.75),threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。

结合负载因子的定义公式可知,threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目,超过这个数目就重新resize(扩容),扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

size这个字段其实很好理解,就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数,具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159,Hashtable初始化桶大小为11,就是桶大小设计为素数的应用(Hashtable扩容后不能保证还是素数)。HashMap采用这种非常规设计,主要是为了在取模和扩容时做优化,同时为了减少冲突,HashMap定位哈希桶索引位置时,也加入了高位参与运算的过程。

这里存在一个问题,即使负载因子和Hash算法设计的再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。于是,在JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树。而当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。本文不再对红黑树展开讨论,想了解更多红黑树数据结构的工作原理可以参考http://blog.csdn.net/v_july_v/article/details/6105630

功能实现-方法

HashMap的内部功能实现很多,本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入展开讲解。

1. 确定哈希桶数组索引位置

不管增加、删除、查找键值对,定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,不用遍历链表,大大优化了查询的效率。HashMap定位数组索引位置,直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):

1
2
3
4
5
6
7
8
9
10
11
方法一:
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二:
static int indexFor(int h, int length) {  //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

这里的Hash算法本质上就是三步:取key的hashCode值、高位运算、取模运算

对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,模运算的消耗还是比较大的,在HashMap中是这样做的:调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙,它通过h & (table.length -1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

下面举例说明下,n为table的长度。

hashMap哈希算法例图

2. 分析HashMap的put方法

HashMap的put方法执行过程可以通过下图来理解,自己有兴趣可以去对比源码更清楚地研究学习。

hashMap put方法执行流程图

①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

JDK1.8HashMap的put方法源码如下:

1     public V put(K key, V value) {
 2     // 对key的hashCode()做hash
 3     return putVal(hash(key), key, value, false, true);
 4 }
 5
 6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 7                boolean evict) {
 8     Node<K,V>[] tab; Node<K,V> p; int n, i;
 9     // 步骤①:tab为空则创建
10     if ((tab = table) == null || (n = tab.length) == 0)
11         n = (tab = resize()).length;
12     // 步骤②:计算index,并对null做处理
13     if ((p = tab[i = (n - 1) & hash]) == null)
14         tab[i] = newNode(hash, key, value, null);
15     else {
16         Node<K,V> e; K k;
17         // 步骤③:节点key存在,直接覆盖value
18         if (p.hash == hash &&
19             ((k = p.key) == key || (key != null && key.equals(k))))
20             e = p;
21         // 步骤④:判断该链为红黑树
22         else if (p instanceof TreeNode)
23             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
24         // 步骤⑤:该链为链表
25         else {
26             for (int binCount = 0; ; ++binCount) {
27                 if ((e = p.next) == null) {
28                     p.next = newNode(hash, key,value,null);
                        //链表长度大于8转换为红黑树进行处理
29                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
30                         treeifyBin(tab, hash);
31                     break;
32                 }
                    // key已经存在直接覆盖value
33                 if (e.hash == hash &&
34                     ((k = e.key) == key || (key != null && key.equals(k))))                                            break;
36                 p = e;
37             }
38         }
39
40         if (e != null) { // existing mapping for key
41             V oldValue = e.value;
42             if (!onlyIfAbsent || oldValue == null)
43                 e.value = value;
44             afterNodeAccess(e);
45             return oldValue;
46         }
47     }
48     ++modCount;
49     // 步骤⑥:超过最大容量 就扩容
50     if (++size > threshold)
51         resize();
52     afterNodeInsertion(evict);
53     return null;
54 }

3. 扩容机制

扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。

我们分析下resize的源码,鉴于JDK1.8融入了红黑树,较复杂,为了便于理解我们仍然使用JDK1.7的代码,好理解一些,本质上区别不大,具体区别后文再说。

1 void resize(int newCapacity) {   //传入新的容量
 2     Entry[] oldTable = table;    //引用扩容前的Entry数组
 3     int oldCapacity = oldTable.length;        
 4     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
 5         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
 6         return;
 7     }
 8
 9     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
10     transfer(newTable);                         //!!将数据转移到新的Entry数组里
11     table = newTable;                           //HashMap的table属性引用新的Entry数组
12     threshold = (int)(newCapacity * loadFactor);//修改阈值
13 }

这里就是使用一个容量更大的数组来代替已有的容量小的数组,transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

1 void transfer(Entry[] newTable) {
 2     Entry[] src = table;                   //src引用了旧的Entry数组
 3     int newCapacity = newTable.length;
 4     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
 5         Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
 6         if (e != null) {
 7             src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
 8             do {
 9                 Entry<K,V> next = e.next;
10                 int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
11                 e.next = newTable[i]; //标记[1]
12                 newTable[i] = e;      //将元素放在数组上
13                 e = next;             //访问下一个Entry链上的元素
14             } while (e != null);
15         }
16     }
17 }

newTable[i]的引用赋给了e.next,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话),这一点和Jdk1.8有区别,下文详解。在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。

下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。其中的哈希桶数组table的size=2, 所以key = 3、7、5,put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1,即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4,然后所有的Node重新rehash的过程。

jdk1.7扩容例图

下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

hashMap 1.8 哈希算法例图1

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

hashMap 1.8 哈希算法例图2

因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:

jdk1.8 hashMap扩容例图

这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码,写的很赞,如下:

1 final Node<K,V>[] resize() {
 2     Node<K,V>[] oldTab = table;
 3     int oldCap = (oldTab == null) ? 0 : oldTab.length;
 4     int oldThr = threshold;
 5     int newCap, newThr = 0;
 6     if (oldCap > 0) {
 7         // 超过最大值就不再扩充了,就只好随你碰撞去吧
 8         if (oldCap >= MAXIMUM_CAPACITY) {
 9             threshold = Integer.MAX_VALUE;
10             return oldTab;
11         }
12         // 没超过最大值,就扩充为原来的2倍
13         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
14                  oldCap >= DEFAULT_INITIAL_CAPACITY)
15             newThr = oldThr << 1; // double threshold
16     }
17     else if (oldThr > 0) // initial capacity was placed in threshold
18         newCap = oldThr;
19     else {               // zero initial threshold signifies using defaults
20         newCap = DEFAULT_INITIAL_CAPACITY;
21         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
22     }
23     // 计算新的resize上限
24     if (newThr == 0) {
25
26         float ft = (float)newCap * loadFactor;
27         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
28                   (int)ft : Integer.MAX_VALUE);
29     }
30     threshold = newThr;
31     @SuppressWarnings({"rawtypes""unchecked"})
32         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
33     table = newTab;
34     if (oldTab != null) {
35         // 把每个bucket都移动到新的buckets中
36         for (int j = 0; j < oldCap; ++j) {
37             Node<K,V> e;
38             if ((e = oldTab[j]) != null) {
39                 oldTab[j] = null;
40                 if (e.next == null)
41                     newTab[e.hash & (newCap - 1)] = e;
42                 else if (e instanceof TreeNode)
43                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
44                 else { // 链表优化重hash的代码块
45                     Node<K,V> loHead = null, loTail = null;
46                     Node<K,V> hiHead = null, hiTail = null;
47                     Node<K,V> next;
48                     do {
49                         next = e.next;
50                         // 原索引
51                         if ((e.hash & oldCap) == 0) {
52                             if (loTail == null)
53                                 loHead = e;
54                             else
55                                 loTail.next = e;
56                             loTail = e;
57                         }
58                         // 原索引+oldCap
59                         else {
60                             if (hiTail == null)
61                                 hiHead = e;
62                             else
63                                 hiTail.next = e;
64                             hiTail = e;
65                         }
66                     } while ((e = next) != null);
67                     // 原索引放到bucket里
68                     if (loTail != null) {
69                         loTail.next = null;
70                         newTab[j] = loHead;
71                     }
72                     // 原索引+oldCap放到bucket里
73                     if (hiTail != null) {
74                         hiTail.next = null;
75                         newTab[j + oldCap] = hiHead;
76                     }
77                 }
78             }
79         }
80     }
81     return newTab;
82 }

线程安全性

在多线程使用场景中,应该尽量避免使用线程不安全的HashMap,而使用线程安全的ConcurrentHashMap。那么为什么说HashMap是线程不安全的,下面举例子说明在并发的多线程使用场景中使用HashMap可能造成死循环。代码例子如下(便于理解,仍然使用JDK1.7的环境):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class HashMapInfiniteLoop { 
    private static HashMap<Integer,String> map = new HashMap<Integer,String>(20.75f); 
    public static void main(String[] args) { 
        map.put(5"C"); 
        new Thread("Thread1") { 
            public void run() { 
                map.put(7, "B"); 
                System.out.println(map); 
            }; 
        }.start(); 
        new Thread("Thread2") { 
            public void run() { 
                map.put(3, "A); 
                System.out.println(map); 
            }; 
        }.start();       
    
}

其中,map初始化为一个长度为2的数组,loadFactor=0.75,threshold=2*0.75=1,也就是说当put第二个key的时候,map就需要进行resize。

通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行;然后放开线程2的的断点,让线程2进行resize。结果如下图。

jdk1.7 hashMap死循环例图1

注意,Thread1的 e 指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。

线程一被调度回来执行,先是执行 newTalbe[i] = e, 然后是e = next,导致了e指向了key(7),而下一次循环的next = e.next导致了next指向了key(3)。

jdk1.7 hashMap死循环例图2

jdk1.7 hashMap死循环例图3

e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意:此时的key(7).next 已经指向了key(3), 环形链表就这样出现了。

jdk1.7 hashMap死循环例图4

于是,当我们用线程一调用map.get(11)时,悲剧就出现了——Infinite Loop。

JDK1.8与JDK1.7的性能对比

HashMap中,如果key经过hash算法得出的数组索引位置全部不相同,即Hash算法非常好,那样的话,getKey方法的时间复杂度就是O(1),如果Hash算法技术的结果碰撞非常多,假如Hash算极其差,所有的Hash算法结果得出的索引位置一样,那样所有的键值对都集中到一个桶中,或者在一个链表中,或者在一个红黑树中,时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化,总体性能优于JDK1.7,下面我们从两个方面用例子证明这一点。

Hash较均匀的情况

为了便于测试,我们先写一个类Key,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Key implements Comparable<Key> {
    private final int value;
    Key(int value) {
        this.value = value;
    }
    @Override
    public int compareTo(Key o) {
        return Integer.compare(this.value, o.value);
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Key key = (Key) o;
        return value == key.value;
    }
    @Override
    public int hashCode() {
        return value;
    }
}

这个类复写了equals方法,并且提供了相当好的hashCode函数,任何一个值的hashCode都不会相同,因为直接使用value当做hashcode。为了避免频繁的GC,我将不变的Key实例缓存了起来,而不是一遍一遍的创建它们。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Keys {
    public static final int MAX_KEY = 10_000_000;
    private static final Key[] KEYS_CACHE = new Key[MAX_KEY];
    static {
        for (int i = 0; i < MAX_KEY; ++i) {
            KEYS_CACHE[i] = new Key(i);
        }
    }
    public static Key of(int value) {
        return KEYS_CACHE[value];
    }
}

现在开始我们的试验,测试需要做的仅仅是,创建不同size的HashMap(1、10、100、……10000000),屏蔽了扩容的情况,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void test(int mapSize) {
       HashMap<Key, Integer> map = new HashMap<Key,Integer>(mapSize);
       for (int i = 0; i < mapSize; ++i) {
           map.put(Keys.of(i), i);
       }
       long beginTime = System.nanoTime(); //获取纳秒
       for (int i = 0; i < mapSize; i++) {
           map.get(Keys.of(i));
       }
       long endTime = System.nanoTime();
       System.out.println(endTime - beginTime);
   }
   public static void main(String[] args) {
       for(int i=10;i<= 1000 0000;i*= 10){
           test(i);
       }
   }

在测试中会查找不同的值,然后度量花费的时间,为了计算getKey的平均时间,我们遍历所有的get方法,计算总的时间,除以key的数量,计算一个平均值,主要用来比较,绝对值可能会受很多环境因素的影响。结果如下:

性能比较表1.png

通过观测测试结果可知,JDK1.8的性能要高于JDK1.7 15%以上,在某些size的区域上,甚至高于100%。由于Hash算法较均匀,JDK1.8引入的红黑树效果不明显,下面我们看看Hash不均匀的的情况。

Hash极不均匀的情况

假设我们又一个非常差的Key,它们所有的实例都返回相同的hashCode值。这是使用HashMap最坏的情况。代码修改如下:

1
2
3
4
5
6
7
8
9
class Key implements Comparable<Key> {
    //...
    @Override
    public int hashCode() {
        return 1;
    }
}

仍然执行main方法,得出的结果如下表所示:

性能比较表2.png

从表中结果中可知,随着size的变大,JDK1.7的花费时间是增长的趋势,而JDK1.8是明显的降低趋势,并且呈现对数增长稳定。当一个链表太长的时候,HashMap会动态的将它替换成一个红黑树,这话的话会将时间复杂度从O(n)降为O(logn)。hash算法均匀和不均匀所花费的时间明显也不相同,这两种情况的相对比较,可以说明一个好的hash算法的重要性。

测试环境:处理器为2.2 GHz Intel Core i7,内存为16 GB 1600 MHz DDR3,SSD硬盘,使用默认的JVM参数,运行在64位的OS X 10.10.1上。

小结

(1) 扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容。

(2) 负载因子是可以修改的,也可以大于1,但是建议不要轻易修改,除非情况非常特殊。

(3) HashMap是线程不安全的,不要在并发的环境中同时操作HashMap,建议使用ConcurrentHashMap。

(4) JDK1.8引入红黑树大程度优化了HashMap的性能。

(5) 还没升级JDK1.8的,现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。

参考

  1. JDK1.7&JDK1.8 源码。
  2. CSDN博客频道,HashMap多线程死循环问题,2014。
  3. 红黑联盟,Java类集框架之HashMap(JDK1.8)源码剖析,2015。
  4. CSDN博客频道, 教你初步了解红黑树,2010。
  5. Java Code Geeks,HashMap performance improvements in Java 8,2014。
  6. Importnew,危险!在HashMap中将可变对象用作Key,2014。
  7. CSDN博客频道,为什么一般hashtable的桶数会取一个素数,2013。

HashMap的工作原理

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深。这题经常出现在高级或中高级面试中。投资银行更喜欢问这个问题,甚至会要求你实现HashMap来考察你的编程能力。ConcurrentHashMap和其它同步集合的引入让这道题变得更加复杂。让我们开始探索的旅程吧!

先来些简单的问题

“你用过HashMap吗?” “什么是HashMap?你为什么用到它?”

几乎每个人都会回答“是的”,然后回答HashMap的一些特性,譬如HashMap可以接受null键值和值,而Hashtable则不能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对等等。这显示出你已经用过HashMap,而且对它相当的熟悉。但是面试官来个急转直下,从此刻开始问出一些刁钻的问题,关于HashMap的更多基础的细节。面试官可能会问出下面的问题:

“你知道HashMap的工作原理吗?” “你知道HashMap的get()方法的工作原理吗?”

你也许会回答“我没有详查标准的Java API,你可以看看Java源代码或者Open JDK。”“我可以用Google找到答案。”

但一些面试者可能可以给出答案,“HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。”这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点,或者错误的认为仅仅只在bucket中存储值的话,你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确,也显示出面试者确实知道hashing以及HashMap的工作原理。但是这仅仅是故事的开始,当面试官加入一些Java程序员每天要碰到的实际场景的时候,错误的答案频现。下个问题可能是关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法:

“当两个对象的hashcode相同会发生什么?” 从这里开始,真正的困惑开始了,一些面试者会回答因为hashcode相同,所以两个对象是相等的,HashMap将会抛出异常,或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法,并告诉他们两个对象就算hashcode相同,但是它们可能并不相等。一些面试者可能就此放弃,而另外一些还能继续挺进,他们回答“因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理,虽然有很多种处理碰撞的方法,这种方法是最简单的,也正是HashMap的处理方法。但故事还没有完结,面试官会继续问:

“如果两个键的hashcode相同,你如何获取值对象?” 面试者会回答:当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket,他给出答案:将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较,你是如何确定确定找到值对象的?除非面试者直到HashMap在链表中存储的是键值对,否则他们不可能回答出这一题。

其中一些记得这个重要知识点的面试者会说,找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。完美的答案!

许多情况下,面试者会在这个环节中出错,因为他们混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现,而equals()方法仅仅在获取值对象的时候才出现。一些优秀的开发者会指出使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。

如果你认为到这里已经完结了,那么听到下面这个问题的时候,你会大吃一惊。“如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?”除非你真正知道HashMap的工作原理,否则你将回答不出这道题。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

如果你能够回答这道问题,下面的问题来了:“你了解重新调整HashMap大小存在什么问题吗?”你可能回答不上来,这时面试官会提醒你当多线程的情况下,可能产生条件竞争(race condition)。

当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。这个时候,你可以质问面试官,为什么这么奇怪,要在多线程的环境下使用HashMap呢?:)

热心的读者贡献了更多的关于HashMap的问题:

  1. 为什么String, Interger这样的wrapper类适合作为键? String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。
  2. 我们可以使用自定义的对象作为键吗? 这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。
  3. 我们可以使用CocurrentHashMap来代替Hashtable吗?这是另外一个很热门的面试题,因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。看看这篇博客查看Hashtable和ConcurrentHashMap的区别。

我个人很喜欢这个问题,因为这个问题的深度和广度,也不直接的涉及到不同的概念。让我们再来看看这些问题设计哪些知识点:

  • hashing的概念
  • HashMap中解决碰撞的方法
  • equals()和hashCode()的应用,以及它们在HashMap中的重要性
  • 不可变对象的好处
  • HashMap多线程的条件竞争
  • 重新调整HashMap的大小

总结

HashMap的工作原理

HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

当两个不同的键对象的hashcode相同时会发生什么? 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。

因为HashMap的好处非常多,我曾经在电子商务的应用中使用HashMap作为缓存。因为金融领域非常多的运用Java,也出于性能的考虑,我们会经常用到HashMap和ConcurrentHashMap。你可以查看更多的关于HashMap的文章:

原文链接: Javarevisited 翻译: ImportNew.com 唐小娟
译文链接: http://www.importnew.com/7099.html

高性能场景下,HashMap的优化使用建议

1. HashMap 在JDK 7 与 JDK8 下的差别

顺便理一下HashMap.get(Object key)的几个关键步骤,作为后面讨论的基础。

1.1 获取key的HashCode并二次加工

因为对原Key的hashCode质量没信心,怕会存在大量冲突,HashMap进行了二次加工。

JDK7的做法:

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

JDK8 因为对自己改造过的哈希大量冲突时的红黑树有信心,所以简单一些,只是把高16位异或下来。

return h ^ (h >>> 16);

所以即使Key比较均匀无哈希冲突,JDK8也比JDK7略快的原因大概于此。

顺便科普一下,Integer的HashCode就是自己,Long要把高32位异或下来变成int, String则是循环累计结果*31+下一个字符,不过因为String是不可变对象,所以生成完一次就会自己cache起来。

1.2 落桶

index = hash & (array.length-1);

桶数组大小是2的指数的好处,通过一次&就够了,而不是代价稍大的取模。

1.3 最后选择Entry

判断Entry是否符合,都是首先哈希值要相等,但因为哈希值不是唯一的,所以还要对比key是否相等,最好是同一个对象,能用==对比,否则要走equals()。 比如String,如果不是同一个对象,equals()起来要一个个字符做比较也是挺累的。

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;

更累的是存在哈希冲突的情况,比如两个哈希值取模后落在同一个桶上,或者两条不同的key有相同的哈希值。
JDK7的做法是建一条链表,后插入的元素在上面,一个个地执行上面的判断。
而JDK8则在链表长度达到8,而且桶数量达到64时,建一棵红黑树,解决严重冲突时的性能问题。

2. 很多人忽视的加载因子Load Factor

加载因子存在的原因,还是因为减缓哈希冲突,如果初始桶为16,等到满16个元素才扩容,某些桶里可能就有不止一个元素了。所以加载因子默认为0.75,也就是说大小为16的HashMap,到了第13个元素,就会扩容成32。

2.1 考虑加载因子地设定初始大小

相比扩容时只是System.arraycopy()的ArrayList,HashMap扩容的代价其实蛮大的,首先,要生成一个新的桶数组,然后要把所有元素都重新Hash落桶一次,几乎等于重新执行了一次所有元素的put。

所以如果你心目中有明确的Map 大小,设定时一定要考虑加载因子的存在。

Map map = new HashMap(srcMap.size())这样的写法肯定是不对的,有25%的可能会遇上扩容。

Thrift里的做法比较粗暴, Map map = new HashMap( 2* srcMap.size()), 直接两倍又有点浪费空间。

Guava的做法则是加上如下计算

(int) ((float) expectedSize / 0.75F + 1.0F);

2.2 减小加载因子

在构造函数里,设定加载因子是0.5甚至0.25。
如果你的Map是一个长期存在而不是每次动态生成的,而里面的key又是没法预估的,那可以适当加大初始大小,同时减少加载因子,降低冲突的机率。毕竟如果是长期存在的map,浪费点数组大小不算啥,降低冲突概率,减少比较的次数更重要。

3. Key的设计

对于String型的Key,如果无法保证无冲突而且能用==来对比,那就尽量搞短点,否则一个个字符的equals还是花时间的。

甚至,对于已知的预定义Key,可以自己试着放一下,看冲不冲突。比如,像”a1”,”a2”,”a3” 这种,hashCode是个小数字递增,绝对是不冲突的:)

4. EnumMap

对于上面的问题,有些同学可能会很冲动的想,这么麻烦,我还是换回用数组,然后用常量来定义一些下标算了。其实不用自己来,EnumMap就是可读性与性能俱佳的实现。

EnumMap的原理是,在构造函数里要传入枚举类,那它就构建一个与枚举的所有值等大的数组,按Enum. ordinal()下标来访问数组,不就是你刚才想做的事情么?

美中不足的是,因为要实现Map接口,而 V get(Object key)中key是Object而不是泛型K,所以安全起见,EnumMap每次访问都要先对Key进行类型判断。在JMC里录得不低的采样命中频率。
所以也可以自己再port一个类出来,不实现Map接口,或者自己增加fastGet(),fastPut()的函数。

5. IntObjectHashMap

Netty以及其他FastUtils之类的原始类型map,都支持key是int或 long。但两者的区别并不仅仅在于int 换 Integer的那点空间,而是整个存储结构和Hash冲突的解决方法都不一样。

HashMap的结构是 Node[] table; Node 下面有Hash,Key,Value,Next四个属性。
而IntObjectHashMap的结构是int[] keys 和 Object[] values.

在插入时,同样把int先取模落桶,如果遇到冲突,则不采样HashMap的链地址法,而是用开放地址法(线性探测法)index+1找下一个空桶,最后在keys[index],values[index]中分别记录。在查找时也是先落桶,然后在key[index++]中逐个比较key。

所以,对比整个数据结构,省的不止是int vs Integer,还有每个Node的内容。
而性能嘛,IntObjectHashMap还是稳赢一点的,随便测了几种场景,耗时至少都有24ms vs 28ms的样子,好的时候甚至快1/3。

优化建议

  1. 考虑加载因子地设定初始大小
  2. 减小加载因子
  3. String类型的key,不能用==判断或者可能有哈希冲突时,尽量减少长度
  4. 使用定制版的EnumMap
  5. 使用IntObjectHashMap

(转)Redis和Memcached的区别

Redis的作者Salvatore Sanfilippo曾经对这两种基于内存的数据存储系统进行过比较:

  1. Redis支持服务器端的数据操作:Redis相比Memcached来说,拥有更多的数据结构和并支持更丰富的数据操作,通常在Memcached里,你需要将数据拿到客户端来进行类似的修改再set回去。这大大增加了网络IO的次数和数据体积。在Redis中,这些复杂的操作通常和一般的GET/SET一样高效。所以,如果需要缓存能够支持更复杂的结构和操作,那么Redis会是不错的选择。
  2. 内存使用效率对比:使用简单的key-value存储的话,Memcached的内存利用率更高,而如果Redis采用hash结构来做key-value存储,由于其组合式的压缩,其内存利用率会高于Memcached。
  3. 性能对比:由于Redis只使用单核,而Memcached可以使用多核,所以平均每一个核上Redis在存储小数据时比Memcached性能更高。而在100k以上的数据中,Memcached性能要高于Redis,虽然Redis最近也在存储大数据的性能上进行优化,但是比起Memcached,还是稍有逊色。

具体为什么会出现上面的结论,以下为收集到的资料:

1、数据类型支持不同

与Memcached仅支持简单的key-value结构的数据记录不同,Redis支持的数据类型要丰富得多。最为常用的数据类型主要由五种:String、Hash、List、Set和Sorted Set。Redis内部使用一个redisObject对象来表示所有的key和value。redisObject最主要的信息如图所示:

redisObject

type代表一个value对象具体是何种数据类型,encoding是不同数据类型在redis内部的存储方式,比如:type=string代表value存储的是一个普通字符串,那么对应的encoding可以是raw或者是int,如果是int则代表实际redis内部是按数值型类存储和表示这个字符串的,当然前提是这个字符串本身可以用数值表示,比如:”123″ “456”这样的字符串。只有打开了Redis的虚拟内存功能,vm字段字段才会真正的分配内存,该功能默认是关闭状态的。

1)String

  • 常用命令:set/get/decr/incr/mget等;
  • 应用场景:String是最常用的一种数据类型,普通的key/value存储都可以归为此类;
  • 实现方式:String在redis内部存储默认就是一个字符串,被redisObject所引用,当遇到incr、decr等操作时会转成数值型进行计算,此时redisObject的encoding字段为int。

2)Hash

  • 常用命令:hget/hset/hgetall等
  • 应用场景:我们要存储一个用户信息对象数据,其中包括用户ID、用户姓名、年龄和生日,通过用户ID我们希望获取该用户的姓名或者年龄或者生日;
  • 实现方式:Redis的Hash实际是内部存储的Value为一个HashMap,并提供了直接存取这个Map成员的接口。如图所示,Key是用户ID, value是一个Map。这个Map的key是成员的属性名,value是属性值。这样对数据的修改和存取都可以直接通过其内部Map的Key(Redis里称内部Map的key为field), 也就是通过 key(用户ID) + field(属性标签) 就可以操作对应属性数据。当前HashMap的实现有两种方式:当HashMap的成员比较少时Redis为了节省内存会采用类似一维数组的方式来紧凑存储,而不会采用真正的HashMap结构,这时对应的value的redisObject的encoding为zipmap,当成员数量增大时会自动转成真正的HashMap,此时encoding为ht。
  • hash
3)List
  • 常用命令:lpush/rpush/lpop/rpop/lrange等;
  • 应用场景:Redis list的应用场景非常多,也是Redis最重要的数据结构之一,比如twitter的关注列表,粉丝列表等都可以用Redis的list结构来实现;
  • 实现方式:Redis list的实现为一个双向链表,即可以支持反向查找和遍历,更方便操作,不过带来了部分额外的内存开销,Redis内部的很多实现,包括发送缓冲队列等也都是用的这个数据结构。
4)Set
  • 常用命令:sadd/spop/smembers/sunion等;
  • 应用场景:Redis set对外提供的功能与list类似是一个列表的功能,特殊之处在于set是可以自动排重的,当你需要存储一个列表数据,又不希望出现重复数据时,set是一个很好的选择,并且set提供了判断某个成员是否在一个set集合内的重要接口,这个也是list所不能提供的;
  • 实现方式:set 的内部实现是一个 value永远为null的HashMap,实际就是通过计算hash的方式来快速排重的,这也是set能提供判断一个成员是否在集合内的原因。

5)Sorted Set

  • 常用命令:zadd/zrange/zrem/zcard等;
  • 应用场景:Redis sorted set的使用场景与set类似,区别是set不是自动有序的,而sorted set可以通过用户额外提供一个优先级(score)的参数来为成员排序,并且是插入有序的,即自动排序。当你需要一个有序的并且不重复的集合列表,那么可以选择sorted set数据结构,比如twitter 的public timeline可以以发表时间作为score来存储,这样获取时就是自动按时间排好序的。
  • 实现方式:Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序,HashMap里放的是成员到score的映射,而跳跃表里存放的是所有的成员,排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率,并且在实现上比较简单。

2、内存管理机制不同

在Redis中,并不是所有的数据都一直存储在内存中的。这是和Memcached相比一个最大的区别。当物理内存用完时,Redis可以将一些很久没用到的value交换到磁盘。Redis只会缓存所有的key的信息,如果Redis发现内存的使用量超过了某一个阀值,将触发swap的操作,Redis根据“swappability = age*log(size_in_memory)”计算出哪些key对应的value需要swap到磁盘。然后再将这些key对应的value持久化到磁盘中,同时在内存中清除。这种特性使得Redis可以保持超过其机器本身内存大小的数据。当然,机器本身的内存必须要能够保持所有的key,毕竟这些数据是不会进行swap操作的。同时由于Redis将内存中的数据swap到磁盘中的时候,提供服务的主线程和进行swap操作的子线程会共享这部分内存,所以如果更新需要swap的数据,Redis将阻塞这个操作,直到子线程完成swap操作后才可以进行修改。当从Redis中读取数据的时候,如果读取的key对应的value不在内存中,那么Redis就需要从swap文件中加载相应数据,然后再返回给请求方。 这里就存在一个I/O线程池的问题。在默认的情况下,Redis会出现阻塞,即完成所有的swap文件加载后才会相应。这种策略在客户端的数量较小,进行批量操作的时候比较合适。但是如果将Redis应用在一个大型的网站应用程序中,这显然是无法满足大并发的情况的。所以Redis运行我们设置I/O线程池的大小,对需要从swap文件中加载相应数据的读取请求进行并发操作,减少阻塞的时间。

对于像Redis和Memcached这种基于内存的数据库系统来说,内存管理的效率高低是影响系统性能的关键因素。传统C语言中的malloc/free函数是最常用的分配和释放内存的方法,但是这种方法存在着很大的缺陷:首先,对于开发人员来说不匹配的malloc和free容易造成内存泄露;其次频繁调用会造成大量内存碎片无法回收重新利用,降低内存利用率;最后作为系统调用,其系统开销远远大于一般函数调用。所以,为了提高内存的管理效率,高效的内存管理方案都不会直接使用malloc/free调用。Redis和Memcached均使用了自身设计的内存管理机制,但是实现方法存在很大的差异,下面将会对两者的内存管理机制分别进行介绍。

Memcached默认使用Slab Allocation机制管理内存,其主要思想是按照预先规定的大小,将分配的内存分割成特定长度的块以存储相应长度的key-value数据记录,以完全解决内存碎片问题。Slab Allocation机制只为存储外部数据而设计,也就是说所有的key-value数据都存储在Slab Allocation系统里,而Memcached的其它内存请求则通过普通的malloc/free来申请,因为这些请求的数量和频率决定了它们不会对整个系统的性能造成影响Slab Allocation的原理相当简单。 如图所示,它首先从操作系统申请一大块内存,并将其分割成各种尺寸的块Chunk,并把尺寸相同的块分成组Slab Class。其中,Chunk就是用来存储key-value数据的最小单位。每个Slab Class的大小,可以在Memcached启动的时候通过制定Growth Factor来控制。假定图中Growth Factor的取值为1.25,如果第一组Chunk的大小为88个字节,第二组Chunk的大小就为112个字节,依此类推。

Slab-Allocation

当Memcached接收到客户端发送过来的数据时首先会根据收到数据的大小选择一个最合适的Slab Class,然后通过查询Memcached保存着的该Slab Class内空闲Chunk的列表就可以找到一个可用于存储数据的Chunk。当一条数据库过期或者丢弃时,该记录所占用的Chunk就可以回收,重新添加到空闲列表中。从以上过程我们可以看出Memcached的内存管理制效率高,而且不会造成内存碎片,但是它最大的缺点就是会导致空间浪费。因为每个Chunk都分配了特定长度的内存空间,所以变长数据无法充分利用这些空间。如图 所示,将100个字节的数据缓存到128个字节的Chunk中,剩余的28个字节就浪费掉了。

Chunk

Redis的内存管理主要通过源码中zmalloc.h和zmalloc.c两个文件来实现的。Redis为了方便内存的管理,在分配一块内存之后,会将这块内存的大小存入内存块的头部。如图所示,real_ptr是redis调用malloc后返回的指针。redis将内存块的大小size存入头部,size所占据的内存大小是已知的,为size_t类型的长度,然后返回ret_ptr。当需要释放内存的时候,ret_ptr被传给内存管理程序。通过ret_ptr,程序可以很容易的算出real_ptr的值,然后将real_ptr传给free释放内存。

zmalloc

Redis通过定义一个数组来记录所有的内存分配情况,这个数组的长度为ZMALLOC_MAX_ALLOC_STAT。数组的每一个元素代表当前程序所分配的内存块的个数,且内存块的大小为该元素的下标。在源码中,这个数组为zmalloc_allocations。zmalloc_allocations[16]代表已经分配的长度为16bytes的内存块的个数。zmalloc.c中有一个静态变量used_memory用来记录当前分配的内存总大小。所以,总的来看,Redis采用的是包装的mallc/free,相较于Memcached的内存管理方法来说,要简单很多。

3、数据持久化支持

Redis虽然是基于内存的存储系统,但是它本身是支持内存数据的持久化的,而且提供两种主要的持久化策略:RDB快照和AOF日志。而memcached是不支持数据持久化操作的。

1)RDB快照

Redis支持将当前数据的快照存成一个数据文件的持久化机制,即RDB快照。但是一个持续写入的数据库如何生成快照呢?Redis借助了fork命令的copy on write机制。在生成快照时,将当前进程fork出一个子进程,然后在子进程中循环所有的数据,将数据写成为RDB文件。我们可以通过Redis的save指令来配置RDB快照生成的时机,比如配置10分钟就生成快照,也可以配置有1000次写入就生成快照,也可以多个规则一起实施。这些规则的定义就在Redis的配置文件中,你也可以通过Redis的CONFIG SET命令在Redis运行时设置规则,不需要重启Redis。

Redis的RDB文件不会坏掉,因为其写操作是在一个新进程中进行的,当生成一个新的RDB文件时,Redis生成的子进程会先将数据写到一个临时文件中,然后通过原子性rename系统调用将临时文件重命名为RDB文件,这样在任何时候出现故障,Redis的RDB文件都总是可用的。同时,Redis的RDB文件也是Redis主从同步内部实现中的一环。RDB有他的不足,就是一旦数据库出现问题,那么我们的RDB文件中保存的数据并不是全新的,从上次RDB文件生成到Redis停机这段时间的数据全部丢掉了。在某些业务下,这是可以忍受的。

2)AOF日志

AOF日志的全称是append only file,它是一个追加写入的日志文件。与一般数据库的binlog不同的是,AOF文件是可识别的纯文本,它的内容就是一个个的Redis标准命令。只有那些会导致数据发生修改的命令才会追加到AOF文件。每一条修改数据的命令都生成一条日志,AOF文件会越来越大,所以Redis又提供了一个功能,叫做AOF rewrite。其功能就是重新生成一份AOF文件,新的AOF文件中一条记录的操作只会有一次,而不像一份老文件那样,可能记录了对同一个值的多次操作。其生成过程和RDB类似,也是fork一个进程,直接遍历数据,写入新的AOF临时文件。在写入新文件的过程中,所有的写操作日志还是会写到原来老的AOF文件中,同时还会记录在内存缓冲区中。当重完操作完成后,会将所有缓冲区中的日志一次性写入到临时文件中。然后调用原子性的rename命令用新的AOF文件取代老的AOF文件。

AOF是一个写文件操作,其目的是将操作日志写到磁盘上,所以它也同样会遇到我们上面说的写操作的流程。在Redis中对AOF调用write写入后,通过appendfsync选项来控制调用fsync将其写到磁盘上的时间,下面appendfsync的三个设置项,安全强度逐渐变强。

  • appendfsync no 当设置appendfsync为no的时候,Redis不会主动调用fsync去将AOF日志内容同步到磁盘,所以这一切就完全依赖于操作系统的调试了。对大多数Linux操作系统,是每30秒进行一次fsync,将缓冲区中的数据写到磁盘上。
  • appendfsync everysec 当设置appendfsync为everysec的时候,Redis会默认每隔一秒进行一次fsync调用,将缓冲区中的数据写到磁盘。但是当这一次的fsync调用时长超过1秒时。Redis会采取延迟fsync的策略,再等一秒钟。也就是在两秒后再进行fsync,这一次的fsync就不管会执行多长时间都会进行。这时候由于在fsync时文件描述符会被阻塞,所以当前的写操作就会阻塞。所以结论就是,在绝大多数情况下,Redis会每隔一秒进行一次fsync。在最坏的情况下,两秒钟会进行一次fsync操作。这一操作在大多数数据库系统中被称为group commit,就是组合多次写操作的数据,一次性将日志写到磁盘。
  • appednfsync always 当设置appendfsync为always时,每一次写操作都会调用一次fsync,这时数据是最安全的,当然,由于每次都会执行fsync,所以其性能也会受到影响。

对于一般性的业务需求,建议使用RDB的方式进行持久化,原因是RDB的开销并相比AOF日志要低很多,对于那些无法忍数据丢失的应用,建议使用AOF日志。

4、集群管理的不同

Memcached是全内存的数据缓冲系统,Redis虽然支持数据的持久化,但是全内存毕竟才是其高性能的本质。作为基于内存的存储系统来说,机器物理内存的大小就是系统能够容纳的最大数据量。如果需要处理的数据量超过了单台机器的物理内存大小,就需要构建分布式集群来扩展存储能力。

Memcached本身并不支持分布式,因此只能在客户端通过像一致性哈希这样的分布式算法来实现Memcached的分布式存储。下图给出了Memcached的分布式存储实现架构。当客户端向Memcached集群发送数据之前,首先会通过内置的分布式算法计算出该条数据的目标节点,然后数据会直接发送到该节点上存储。但客户端查询数据时,同样要计算出查询数据所在的节点,然后直接向该节点发送查询请求以获取数据。

Memcached-node

 

相较于Memcached只能采用客户端实现分布式存储,Redis更偏向于在服务器端构建分布式存储。最新版本的Redis已经支持了分布式存储功能。Redis Cluster是一个实现了分布式且允许单点故障的Redis高级版本,它没有中心节点,具有线性可伸缩的功能。下图给出Redis Cluster的分布式存储架构,其中节点与节点之间通过二进制协议进行通信,节点与客户端之间通过ascii协议进行通信。在数据的放置策略上,Redis Cluster将整个key的数值域分成4096个哈希槽,每个节点上可以存储一个或多个哈希槽,也就是说当前Redis Cluster支持的最大节点数就是4096。Redis Cluster使用的分布式算法也很简单:crc16( key ) % HASH_SLOTS_NUMBER。

Redis-Cluster

 

为了保证单点故障下的数据可用性,Redis Cluster引入了Master节点和Slave节点。在Redis Cluster中,每个Master节点都会有对应的两个用于冗余的Slave节点。这样在整个集群中,任意两个节点的宕机都不会导致数据的不可用。当Master节点退出后,集群会自动选择一个Slave节点成为新的Master节点。

Redis-Cluster-2

参考资料:

码字很辛苦,转载请注明来自标点符《Redis和Memcached的区别》

Java HashSet工作原理及实现

来源:Yikun

网址:http://yikun.github.io/2015/04/08/

1. 概述

This class implements the Set interface, backed by a hash table (actually a HashMapinstance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

HashSet是基于HashMap来实现的,操作很简单,更像是对HashMap做了一次“封装”,而且只使用了HashMap的key来实现各种特性,我们先来感性的认识一下这个结构:

HashSet<String> set = new HashSet<String>();

set.add(“语文”);

set.add(“数学”);

set.add(“英语”);

set.add(“历史”);

set.add(“政治”);

set.add(“地理”);

set.add(“生物”);

set.add(“化学”);

其大致的结构是这样的:

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map

private static final Object PRESENT = new Object();

map是整个HashSet的核心,而PRESENT则是用来造一个假的value来用的。

2. 基本操作

public boolean add(E e) {

return map.put(e, PRESENT)==null;

}

 

public boolean remove(Object o) {

return map.remove(o)==PRESENT;

}

 

public boolean contains(Object o) {

return map.containsKey(o);

}

 

public int size() {

return map.size();

}

基本操作也非常简单,就是调用HashMap的相关方法,其中value就是之前那个dummy的Object。所以,只要了解#7 HashMap的实现就可以了。

参考资料

HashSet(Java Platform 8)

Java ArrayList工作原理及实现

来源:Yikun

链接:http://yikun.github.io/2015/04/04/Java-ArrayList%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

1. 概述

关于Java集合的小抄中是这样描述的:

以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组,因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。

按数组下标访问元素—get(i)/set(i,e) 的性能很高,这是数组的基本优势。

直接在数组末尾加入元素—add(e)的性能也高,但如果按下标插入、删除元素—add(i,e), remove(i), remove(e),则要用System.arraycopy()来移动部分受影响的元素,性能就变差了,这是基本劣势。

然后再来学习一下官方文档:

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

ArrayList是一个相对来说比较简单的数据结构,最重要的一点就是它的自动扩容,可以认为就是我们常说的“动态数组”。

来看一段简单的代码:

ArrayList<String> list = new ArrayList<String>();

list.add(“语文: 99”);

list.add(“数学: 98”);

list.add(“英语: 100”);

list.remove(0);

在执行这四条语句时,是这么变化的:

其中,add操作可以理解为直接将数组的内容置位,remove操作可以理解为删除index为0的节点,并将后面元素移到0处。

2. add函数

当我们在ArrayList中增加元素的时候,会使用add函数。他会将元素放到末尾。具体实现如下:

public boolean add(E e) {

ensureCapacityInternal(size + 1);  // Increments modCount!!

elementData[size++] = e;

return true;

}

我们可以看到他的实现其实最核心的内容就是ensureCapacityInternal。这个函数其实就是自动扩容机制的核心。我们依次来看一下他的具体实现

private void ensureCapacityInternal(int minCapacity) {

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

}

 

ensureExplicitCapacity(minCapacity);

}

 

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

 

// overflow-conscious code

if (minCapacity – elementData.length > 0)

grow(minCapacity);

}

 

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

// 扩展为原来的1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1);

// 如果扩为1.5倍还不满足需求,直接扩为需求值

if (newCapacity – minCapacity < 0)

newCapacity = minCapacity;

if (newCapacity – MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity);

}

也就是说,当增加数据的时候,如果ArrayList的大小已经不满足需求时,那么就将数组变为原长度的1.5倍,之后的操作就是把老的数组拷到新的数组里面。例如,默认的数组大小是10,也就是说当我们add10个元素之后,再进行一次add时,就会发生自动扩容,数组长度由10变为了15具体情况如下所示:

3 set和get函数

Array的put和get函数就比较简单了,先做index检查,然后执行赋值或访问操作:

public E set(int index, E element) {

rangeCheck(index);

 

E oldValue = elementData(index);

elementData[index] = element;

return oldValue;

}

 

public E get(int index) {

rangeCheck(index);

 

return elementData(index);

}

4 remove函数

public E remove(int index) {

rangeCheck(index);

 

modCount++;

E oldValue = elementData(index);

 

int numMoved = size – index – 1;

if (numMoved > 0)

// 把后面的往前移

System.arraycopy(elementData, index+1, elementData, index,

numMoved);

// 把最后的置null

elementData[–size] = null; // clear to let GC do its work

 

return oldValue;

}

注释很清楚:

Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

参考资料

Class ArrayList

ArrayList其实就那么一回事儿之源码浅析

关于ArrayList

ConcurrentHashMap原理分析

一.Java并发基础

当一个对象或变量可以被多个线程共享的时候,就有可能使得程序的逻辑出现问题。 在一个对象中有一个变量i=0,有两个线程A,B都想对i加1,这个时候便有问题显现出来,关键就是对i加1的这个过程不是原子操作。要想对i进行递增,第一步就是获取i的值,当A获取i的值为0,在A将新的值写入A之前,B也获取了A的值0,然后A写入,i变成1,然后B也写入i,i这个时候依然是1. 当然java的内存模型没有上面这么简单,在Java Memory Model中,Memory分为两类,main memory和working memory,main memory为所有线程共享,working memory中存放的是线程所需要的变量的拷贝(线程要对main memory中的内容进行操作的话,首先需要拷贝到自己的working memory,一般为了速度,working memory一般是在cpu的cache中的)。volatile的变量在被操作的时候不会产生working memory的拷贝,而是直接操作main memory,当然volatile虽然解决了变量的可见性问题,但没有解决变量操作的原子性的问题,这个还需要synchronized或者CAS相关操作配合进行。

多线程中几个重要的概念:

可见性

也就说假设一个对象中有一个变量i,那么i是保存在main memory中的,当某一个线程要操作i的时候,首先需要从main memory中将i 加载到这个线程的working memory中,这个时候working memory中就有了一个i的拷贝,这个时候此线程对i的修改都在其working memory中,直到其将i从working memory写回到main memory中,新的i的值才能被其他线程所读取。从某个意义上说,可见性保证了各个线程的working memory的数据的一致性。 可见性遵循下面一些规则:

  • 当一个线程运行结束的时候,所有写的变量都会被flush回main memory中。
  • 当一个线程第一次读取某个变量的时候,会从main memory中读取最新的。
  • volatile的变量会被立刻写到main memory中的,在jsr133中,对volatile的语义进行增强,后面会提到
  • 当一个线程释放锁后,所有的变量的变化都会flush到main memory中,然后一个使用了这个相同的同步锁的进程,将会重新加载所有的使用到的变量,这样就保证了可见性。

原子性

还拿上面的例子来说,原子性就是当某一个线程修改i的值的时候,从取出i到将新的i的值写给i之间不能有其他线程对i进行任何操作。也就是说保证某个线程对i的操作是原子性的,这样就可以避免数据脏读。 通过锁机制或者CAS(Compare And Set 需要硬件CPU的支持)操作可以保证操作的原子性。

有序性

假设在main memory中存在两个变量i和j,初始值都为0,在某个线程A的代码中依次对i和j进行自增操作(i,j的操作不相互依赖)

i++;

j++;

由于,所以i,j修改操作的顺序可能会被重新排序。那么修改后的ij写到main memory中的时候,顺序可能就不是按照i,j的顺序了,这就是所谓的reordering,在单线程的情况下,当线程A运行结束的后i,j的值都加1了,在线程自己看来就好像是线程按照代码的顺序进行了运行(这些操作都是基于as-if-serial语义的),即使在实际运行过程中,i,j的自增可能被重新排序了,当然计算机也不能帮你乱排序,存在上下逻辑关联的运行顺序肯定还是不会变的。但是在多线程环境下,问题就不一样了,比如另一个线程B的代码如下

if(j==1) {

System.out.println(i);

}

按照我们的思维方式,当j为1的时候那么i肯定也是1,因为代码中i在j之前就自增了,但实际的情况有可能当j为1的时候i还是为0。这就是reordering产生的不好的后果,所以我们在某些时候为了避免这样的问题需要一些必要的策略,以保证多个线程一起工作的时候也存在一定的次序。JMM提供了happens-before 的排序策略。这样我们可以得到多线程环境下的as-if-serial语义。 这里不对happens-before进行详细解释了,详细的请看这里http://www.ibm.com/developerworks/cn/java/j-jtp03304/,这里主要讲一下volatile在新的java内存模型下的变化,在jsr133之前,下面的代码可能会出现问题

Map configOptions;

char[] configText;

volatile boolean initialized = false;

// In Thread A

configOptions = new HashMap();

configText = readConfigFile(fileName);

processConfigOptions(configText, configOptions);

initialized = true;

// In Thread B

while (!initialized)

sleep();

// use configOptions

jsr133之前,虽然对 volatile 变量的读和写不能与对其他 volatile 变量的读和写一起重新排序,但是它们仍然可以与对 nonvolatile 变量的读写一起重新排序,所以上面的Thread A的操作,就可能initialized变成true的时候,而configOptions还没有被初始化,所以initialized先于configOptions被线程B看到,就产生问题了。

JSR 133 Expert Group 决定让 volatile 读写不能与其他内存操作一起重新排序,新的内存模型下,如果当线程 A 写入 volatile 变量 V 而线程 B 读取 V 时,那么在写入 V 时,A 可见的所有变量值现在都可以保证对 B 是可见的。

结果就是作用更大的 volatile 语义,代价是访问 volatile 字段时会对性能产生更大的影响。这一点在ConcurrentHashMap中的统计某个segment元素个数的count变量中使用到了。

二.线程安全的HashMap

什么时候我们需要使用线程安全的hashmap呢,比如一个hashmap在运行的时候只有读操作,那么很明显不会有问题,但是当涉及到同时有改变也有读的时候,就要考虑线程安全问题了,在不考虑性能问题的时候,我们的解决方案有Hashtable或者Collections.synchronizedMap(hashMap),这两种方式基本都是对整个hash表结构做锁定操作的,这样在锁表的期间,别的线程就需要等待了,无疑性能不高。

三.ConcurrentHashMap实现原理

数据结构 ConcurrentHashMap的目标是实现支持高并发、高吞吐量的线程安全的HashMap。当然不能直接对整个hashtable加锁,所以在ConcurrentHashMap中,数据的组织结构和HashMap有所区别。

一个ConcurrentHashMap由多个segment组成,每一个segment都包含了一个HashEntry数组的hashtable, 每一个segment包含了对自己的hashtable的操作,比如get,put,replace等操作,这些操作发生的时候,对自己的hashtable进行锁定。由于每一个segment写操作只锁定自己的hashtable,所以可能存在多个线程同时写的情况,性能无疑好于只有一个hashtable锁定的情况。

源码分析 在ConcurrentHashMap的remove,put操作还是比较简单的,都是将remove或者put操作交给key所对应的segment去做的,所以当几个操作不在同一个segment的时候就可以并发的进行。

public V remove(Object key) {

int hash = hash(key.hashCode());

return segmentFor(hash).remove(key, hash, null);

}

而segment中的remove操作除了加锁之外和HashMap中的remove操作基本无异。

/**

* Remove; match on key only if value null, else match both.

*/

V remove(Object key, int hash, Object value) {

lock();

try {

int c = count – 1;

HashEntry<K,V>[] tab = table;

int index = hash & (tab.length – 1);

HashEntry<K,V> first = tab[index];

HashEntry<K,V> e = first;

while (e != null && (e.hash != hash || !key.equals(e.key)))

e = e.next;

V oldValue = null;

if (e != null) {

V v = e.value;

if (value == null || value.equals(v)) {

oldValue = v;

// All entries following removed node can stay

// in list, but all preceding ones need to be

// cloned.

++modCount;

HashEntry<K,V> newFirst = e.next;

for (HashEntry<K,V> p = first; p != e; p = p.next)

newFirst = new HashEntry<K,V>(p.key, p.hash,

newFirst, p.value);

tab[index] = newFirst;

count = c; // write-volatile

}

}

return oldValue;

} finally {

unlock();

}

}

上面的代码中关于volatile类型的变量count值得一提,这里充分利用了Java 5中对volatile语义的增强,count = c的操作必须在modCount,table等操作的后面,这样才能保证这些变量操作的可见性。 Segment类继承于ReentrantLock,主要是为了使用ReentrantLock的锁,ReentrantLock的实现比 synchronized在多个线程争用下的总体开销小。 put操作和remove操作类似。

接下来我们来看下get操作。

public V get(Object key) {

int hash = hash(key.hashCode());

return segmentFor(hash).get(key, hash);

}

也是使用了对应的segment的get

V get(Object key, int hash) {

if (count != 0) { // read-volatile

HashEntry<K,V> e = getFirst(hash);

while (e != null) {

if (e.hash == hash && key.equals(e.key)) {

V v = e.value;

if (v != null)

return v;

return readValueUnderLock(e); // recheck

}

e = e.next;

}

}

return null;

}

上面的代码中,一开始就对volatile变量count进行了读取比较,这个还是java5对volatile语义增强的作用,这样就可以获取变量的可见性。所以count != 0之后,我们可以认为对应的hashtable是最新的,当然由于读取的时候没有加锁,在get的过程中,可能会有更新。当发现根据key去找元素的时候,但发现找得的key对应的value为null,这个时候可能会有其他线程正在对这个元素进行写操作,所以需要在使用锁的情况下在读取一下value,以确保最终的值。

其他相关涉及读取的操作也都类似。

出处:geeklu

链接:http://geeklu.com/2010/07/concurrenthashmap/

Java HashMap工作原理

原文:coding-geeks

译文:ImportNew – Wing

链接:http://www.importnew.com/16599.html

大部分Java开发者都在使用Map,特别是HashMap。HashMap是一种简单但强大的方式去存储和获取数据。但有多少开发者知道HashMap内部如何工作呢?几天前,我阅读了java.util.HashMap的大量源代码(包括Java 7 和Java 8),来深入理解这个基础的数据结构。在这篇文章中,我会解释java.util.HashMap的实现,描述Java 8实现中添加的新特性,并讨论性能、内存以及使用HashMap时的一些已知问题。

内部存储

Java HashMap类实现了Map<K, V>接口。这个接口中的主要方法包括:

  • V put(K key, V value)
  • V get(Object key)
  • V remove(Object key)
  • Boolean containsKey(Object key)

HashMap使用了一个内部类Entry<K, V>来存储数据。这个内部类是一个简单的键值对,并带有额外两个数据:

  • 一个指向其他入口(译者注:引用对象)的引用,这样HashMap可以存储类似链接列表这样的对象。
  • 一个用来代表键的哈希值,存储这个值可以避免HashMap在每次需要时都重新生成键所对应的哈希值。

下面是Entry<K, V>在Java 7下的一部分代码:

static class Entry<K,V> implements Map.Entry<K,V> {

final K key;

V value;

Entry<K,V> next;

int hash;

}

HashMap将数据存储到多个单向Entry链表中(有时也被称为桶bucket或者容器orbins)。所有的列表都被注册到一个Entry数组中(Entry<K, V>[]数组),这个内部数组的默认长度是16。

下面这幅图描述了一个HashMap实例的内部存储,它包含一个nullable对象组成的数组。每个对象都连接到另外一个对象,这样就构成了一个链表。

所有具有相同哈希值的键都会被放到同一个链表(桶)中。具有不同哈希值的键最终可能会在相同的桶中。

当用户调用 put(K key, V value) 或者 get(Object key) 时,程序会计算对象应该在的桶的索引。然后,程序会迭代遍历对应的列表,来寻找具有相同键的Entry对象(使用键的equals()方法)。

对于调用get()的情况,程序会返回值所对应的Entry对象(如果Entry对象存在)。

对于调用put(K key, V value)的情况,如果Entry对象已经存在,那么程序会将值替换为新值,否则,程序会在单向链表的表头创建一个新的Entry(从参数中的键和值)。

桶(链表)的索引,是通过map的3个步骤生成的:

  • 首先获取键的散列码。
  • 程序重复散列码,来阻止针对键的糟糕的哈希函数,因为这有可能会将所有的数据都放到内部数组的相同的索引(桶)上。
  • 程序拿到重复后的散列码,并对其使用数组长度(最小是1)的位掩码(bit-mask)。这个操作可以保证索引不会大于数组的大小。你可以将其看做是一个经过计算的优化取模函数。

下面是生成索引的源代码:

// the “rehash” function in JAVA 7 that takes the hashcode of the key

static int hash(int h) {

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

// the “rehash” function in JAVA 8 that directly takes the key

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

// the function that returns the index from the rehashed hash

static int indexFor(int h, int length) {

return h & (length-1);

}

为了更有效地工作,内部数组的大小必须是2的幂值。让我们看一下为什么:

假设数组的长度是17,那么掩码的值就是16(数组长度-1)。16的二进制表示是0…010000,这样对于任何值H来说,“H & 16”的结果就是16或者0。这意味着长度为17的数组只能应用到两个桶上:一个是0,另外一个是16,这样不是很有效率。但是如果你将数组的长度设置为2的幂值,例如16,那么按位索引的工作变成“H & 15”。15的二进制表示是0…001111,索引公式输出的值可以从0到15,这样长度为16的数组就可以被充分使用了。例如:

  • 如果H = 952,它的二进制表示是0..01110111000,对应的索引是0…01000 = 8
  • 如果H = 1576,它的二进制表示是0..011000101000,对应的索引是0…01000 = 8
  • 如果H = 12356146,它的二进制表示是0..0101111001000101000110010,对应的索引是0…00010 = 2
  • 如果H = 59843,它的二进制表示是0..01110100111000011,它对应的索引是0…00011 = 3

这种机制对于开发者来说是透明的:如果他选择一个长度为37的HashMap,Map会自动选择下一个大于37的2的幂值(64)作为内部数组的长度。

自动调整大小

在获取索引后,get()、put()或者remove()方法会访问对应的链表,来查看针对指定键的Entry对象是否已经存在。在不做修改的情况下,这个机制可能会导致性能问题,因为这个方法需要迭代整个列表来查看Entry对象是否存在。假设内部数组的长度采用默认值16,而你需要存储2,000,000条记录。在最好的情况下,每个链表会有125,000个Entry对象(2,000,000/16)。get()、remove()和put()方法在每一次执行时,都需要进行125,000次迭代。为了避免这种情况,HashMap可以增加内部数组的长度,从而保证链表中只保留很少的Entry对象。

当你创建一个HashMap时,你可以通过以下构造函数指定一个初始长度,以及一个loadFactor:

</pre>

public HashMap(int initialCapacity, float loadFactor)

<pre>

如果你不指定参数,那么默认的initialCapacity的值是16, loadFactor的默认值是0.75。initialCapacity代表内部数组的链表的长度。

当你每次使用put(…)方法向Map中添加一个新的键值对时,该方法会检查是否需要增加内部数组的长度。为了实现这一点,Map存储了2个数据:

  • Map的大小:它代表HashMap中记录的条数。我们在向HashMap中插入或者删除值时更新它。
  • 阀值:它等于内部数组的长度*loadFactor,在每次调整内部数组的长度时,该阀值也会同时更新。

在添加新的Entry对象之前,put(…)方法会检查当前Map的大小是否大于阀值。如果大于阀值,它会创建一个新的数组,数组长度是当前内部数组的两倍。因为新数组的大小已经发生改变,所以索引函数(就是返回“键的哈希值 & (数组长度-1)”的位运算结果)也随之改变。调整数组的大小会创建两个新的桶(链表),并且将所有现存Entry对象重新分配到桶上。调整数组大小的目标在于降低链表的大小,从而降低put()、remove()和get()方法的执行时间。对于具有相同哈希值的键所对应的所有Entry对象来说,它们会在调整大小后分配到相同的桶中。但是,如果两个Entry对象的键的哈希值不一样,但它们之前在同一个桶上,那么在调整以后,并不能保证它们依然在同一个桶上。

这幅图片描述了调整前和调整后的内部数组的情况。在调整数组长度之前,为了得到Entry对象E,Map需要迭代遍历一个包含5个元素的链表。在调整数组长度之后,同样的get()方法则只需要遍历一个包含2个元素的链表,这样get()方法在调整数组长度后的运行速度提高了2倍。

线程安全

如果你已经非常熟悉HashMap,那么你肯定知道它不是线程安全的,但是为什么呢?例如假设你有一个Writer线程,它只会向Map中插入已经存在的数据,一个Reader线程,它会从Map中读取数据,那么它为什么不工作呢?

因为在自动调整大小的机制下,如果线程试着去添加或者获取一个对象,Map可能会使用旧的索引值,这样就不会找到Entry对象所在的新桶。

在最糟糕的情况下,当2个线程同时插入数据,而2次put()调用会同时出发数组自动调整大小。既然两个线程在同时修改链表,那么Map有可能在一个链表的内部循环中退出。如果你试着去获取一个带有内部循环的列表中的数据,那么get()方法永远不会结束。

HashTable提供了一个线程安全的实现,可以阻止上述情况发生。但是,既然所有的同步的CRUD操作都非常慢。例如,如果线程1调用get(key1),然后线程2调用get(key2),线程2调用get(key3),那么在指定时间,只能有1个线程可以得到它的值,但是3个线程都可以同时访问这些数据。

从Java 5开始,我们就拥有一个更好的、保证线程安全的HashMap实现:ConcurrentHashMap。对于ConcurrentMap来说,只有桶是同步的,这样如果多个线程不使用同一个桶或者调整内部数组的大小,它们可以同时调用get()、remove()或者put()方法。在一个多线程应用程序中,这种方式是更好的选择。

键的不变性

为什么将字符串和整数作为HashMap的键是一种很好的实现?主要是因为它们是不可变的!如果你选择自己创建一个类作为键,但不能保证这个类是不可变的,那么你可能会在HashMap内部丢失数据。

我们来看下面的用例:

  • 你有一个键,它的内部值是“1”。
  • 你向HashMap中插入一个对象,它的键就是“1”。
  • HashMap从键(即“1”)的散列码中生成哈希值。
  • Map在新创建的记录中存储这个哈希值。
  • 你改动键的内部值,将其变为“2”。
  • 键的哈希值发生了改变,但是HashMap并不知道这一点(因为存储的是旧的哈希值)。
  • 你试着通过修改后的键获取相应的对象。
  • Map会计算新的键(即“2”)的哈希值,从而找到Entry对象所在的链表(桶)。
  • 情况1: 既然你已经修改了键,Map会试着在错误的桶中寻找Entry对象,没有找到。
  • 情况2: 你很幸运,修改后的键生成的桶和旧键生成的桶是同一个。Map这时会在链表中进行遍历,已找到具有相同键的Entry对象。但是为了寻找键,Map首先会通过调用equals()方法来比较键的哈希值。因为修改后的键会生成不同的哈希值(旧的哈希值被存储在记录中),那么Map没有办法在链表中找到对应的Entry对象。

下面是一个Java示例,我们向Map中插入两个键值对,然后我修改第一个键,并试着去获取这两个对象。你会发现从Map中返回的只有第二个对象,第一个对象已经“丢失”在HashMap中:

public class MutableKeyTest {

public static void main(String[] args) {

class MyKey {

Integer i;

public void setI(Integer i) {

this.i = i;

}

public MyKey(Integer i) {

this.i = i;

}

@Override

public int hashCode() {

return i;

}

@Override

public boolean equals(Object obj) {

if (obj instanceof MyKey) {

return i.equals(((MyKey) obj).i);

} else

return false;

}

}

Map<MyKey, String> myMap = new HashMap<>();

MyKey key1 = new MyKey(1);

MyKey key2 = new MyKey(2);

myMap.put(key1, “test ” + 1);

myMap.put(key2, “test ” + 2);

// modifying key1

key1.setI(3);

String test1 = myMap.get(key1);

String test2 = myMap.get(key2);

System.out.println(“test1= ” + test1 + ” test2=” + test2);

}

}

上述代码的输出是“test1=null test2=test 2”。如我们期望的那样,Map没有能力获取经过修改的键 1所对应的字符串1。

Java 8 中的改进

在Java 8中,HashMap中的内部实现进行了很多修改。的确如此,Java 7使用了1000行代码来实现,而Java 8中使用了2000行代码。我在前面描述的大部分内容在Java 8中依然是对的,除了使用链表来保存Entry对象。在Java 8中,我们仍然使用数组,但它会被保存在Node中,Node中包含了和之前Entry对象一样的信息,并且也会使用链表:

下面是在Java 8中Node实现的一部分代码:

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

那么和Java 7相比,到底有什么大的区别呢?好吧,Node可以被扩展成TreeNode。TreeNode是一个红黑树的数据结构,它可以存储更多的信息,这样我们可以在O(log(n))的复杂度下添加、删除或者获取一个元素。下面的示例描述了TreeNode保存的所有信息:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

final int hash; // inherited from Node<K,V>

final K key; // inherited from Node<K,V>

V value; // inherited from Node<K,V>

Node<K,V> next; // inherited from Node<K,V>

Entry<K,V> before, after;// inherited from LinkedHashMap.Entry<K,V>

TreeNode<K,V> parent;

TreeNode<K,V> left;

TreeNode<K,V> right;

TreeNode<K,V> prev;

boolean red;

红黑树是自平衡的二叉搜索树。它的内部机制可以保证它的长度总是log(n),不管我们是添加还是删除节点。使用这种类型的树,最主要的好处是针对内部表中许多数据都具有相同索引(桶)的情况,这时对树进行搜索的复杂度是O(log(n)),而对于链表来说,执行相同的操作,复杂度是O(n)。

如你所见,我们在树中确实存储了比链表更多的数据。根据继承原则,内部表中可以包含Node(链表)或者TreeNode(红黑树)。Oracle决定根据下面的规则来使用这两种数据结构:

– 对于内部表中的指定索引(桶),如果node的数目多于8个,那么链表就会被转换成红黑树。

– 对于内部表中的指定索引(桶),如果node的数目小于6个,那么红黑树就会被转换成链表。

这张图片描述了在Java 8 HashMap中的内部数组,它既包含树(桶0),也包含链表(桶1,2和3)。桶0是一个树结构是因为它包含的节点大于8个。

内存开销

JAVA 7

使用HashMap会消耗一些内存。在Java 7中,HashMap将键值对封装成Entry对象,一个Entry对象包含以下信息:

  • 指向下一个记录的引用
  • 一个预先计算的哈希值(整数)
  • 一个指向键的引用
  • 一个指向值的引用

此外,Java 7中的HashMap使用了Entry对象的内部数组。假设一个Java 7 HashMap包含N个元素,它的内部数组的容量是CAPACITY,那么额外的内存消耗大约是:

sizeOf(integer)* N + sizeOf(reference)* (3*N+C)

其中:

  • 整数的大小是4个字节
  • 引用的大小依赖于JVM、操作系统以及处理器,但通常都是4个字节。

这就意味着内存总开销通常是16 * N + 4 * CAPACITY字节。

注意:在Map自动调整大小后,CAPACITY的值是下一个大于N的最小的2的幂值。

注意:从Java 7开始,HashMap采用了延迟加载的机制。这意味着即使你为HashMap指定了大小,在我们第一次使用put()方法之前,记录使用的内部数组(耗费4*CAPACITY字节)也不会在内存中分配空间。

JAVA 8

在Java 8实现中,计算内存使用情况变得复杂一些,因为Node可能会和Entry存储相同的数据,或者在此基础上再增加6个引用和一个Boolean属性(指定是否是TreeNode)。

如果所有的节点都只是Node,那么Java 8 HashMap消耗的内存和Java 7 HashMap消耗的内存是一样的。

如果所有的节点都是TreeNode,那么Java 8 HashMap消耗的内存就变成:

N * sizeOf(integer) + N * sizeOf(boolean) + sizeOf(reference)* (9*N+CAPACITY )

在大部分标准JVM中,上述公式的结果是44 * N + 4 * CAPACITY 字节。

性能问题

非对称HashMap vs 均衡HashMap

在最好的情况下,get()和put()方法都只有O(1)的复杂度。但是,如果你不去关心键的哈希函数,那么你的put()和get()方法可能会执行非常慢。put()和get()方法的高效执行,取决于数据被分配到内部数组(桶)的不同的索引上。如果键的哈希函数设计不合理,你会得到一个非对称的分区(不管内部数据的是多大)。所有的put()和get()方法会使用最大的链表,这样就会执行很慢,因为它需要迭代链表中的全部记录。在最坏的情况下(如果大部分数据都在同一个桶上),那么你的时间复杂度就会变为O(n)。

下面是一个可视化的示例。第一张图描述了一个非对称HashMap,第二张图描述了一个均衡HashMap。

在这个非对称HashMap中,在桶0上运行get()和put()方法会很花费时间。获取记录K需要花费6次迭代。

在这个均衡HashMap中,获取记录K只需要花费3次迭代。这两个HashMap存储了相同数量的数据,并且内部数组的大小一样。唯一的区别是键的哈希函数,这个函数用来将记录分布到不同的桶上。

下面是一个使用Java编写的极端示例,在这个示例中,我使用哈希函数将所有的数据放到相同的链表(桶),然后我添加了2,000,000条数据。

public class Test {

public static void main(String[] args) {

class MyKey {

Integer i;

public MyKey(Integer i){

this.i =i;

}

@Override

public int hashCode() {

return 1;

}

@Override

public boolean equals(Object obj) {

}

}

Date begin = new Date();

Map <MyKey,String> myMap= new HashMap<>(2_500_000,1);

for (int i=0;i<2_000_000;i++){

myMap.put( new MyKey(i), “test “+i);

}

Date end = new Date();

System.out.println(“Duration (ms) “+ (end.getTime()-begin.getTime()));

}

}

我的机器配置是core i5-2500k @ 3.6G,在java 8u40下需要花费超过45分钟的时间来运行(我在45分钟后停止了进程)。如果我运行同样的代码, 但是我使用如下的hash函数:

@Override

public int hashCode() {

int key = 2097152-1;

return key+2097152*i;

}

运行它需要花费46秒,和之前比,这种方式好很多了!新的hash函数比旧的hash函数在处理哈希分区时更合理,因此调用put()方法会更快一些。如果你现在运行相同的代码,但是使用下面的hash函数,它提供了更好的哈希分区:

@Override

public int hashCode() {

return i;

}

现在只需要花费2秒!

我希望你能够意识到哈希函数有多重要。如果在Java 7上面运行同样的测试,第一个和第二个的情况会更糟(因为Java 7中的put()方法复杂度是O(n),而Java 8中的复杂度是O(log(n))。

在使用HashMap时,你需要针对键找到一种哈希函数,可以将键扩散到最可能的桶上。为此,你需要避免哈希冲突。String对象是一个非常好的键,因为它有很好的哈希函数。Integer也很好,因为它的哈希值就是它自身的值。

调整大小的开销

如果你需要存储大量数据,你应该在创建HashMap时指定一个初始的容量,这个容量应该接近你期望的大小。

如果你不这样做,Map会使用默认的大小,即16,factorLoad的值是0.75。前11次调用put()方法会非常快,但是第12次(16*0.75)调用时会创建一个新的长度为32的内部数组(以及对应的链表/树),第13次到第22次调用put()方法会很快,但是第23次(32*0.75)调用时会重新创建(再一次)一个新的内部数组,数组的长度翻倍。然后内部调整大小的操作会在第48次、96次、192次…..调用put()方法时触发。如果数据量不大,重建内部数组的操作会很快,但是数据量很大时,花费的时间可能会从秒级到分钟级。通过初始化时指定Map期望的大小,你可以避免调整大小操作带来的消耗。

但这里也有一个缺点:如果你将数组设置的非常大,例如2^28,但你只是用了数组中的2^26个桶,那么你将会浪费大量的内存(在这个示例中大约是2^30字节)。

结论

对于简单的用例,你没有必要知道HashMap是如何工作的,因为你不会看到O(1)、O(n)以及O(log(n))之间的区别。但是如果能够理解这一经常使用的数据结构背后的机制,总是有好处的。另外,对于Java开发者职位来说,这是一道典型的面试问题。

对于大数据量的情况,了解HashMap如何工作以及理解键的哈希函数的重要性就变得非常重要。

我希望这篇文章可以帮助你对HashMap的实现有一个深入的理解。

HashMap的实现原理

来源:李大辉的博客

链接:http://t.cn/RLtyQVc

点击“阅读全文”可查看本文网页版

HashMap概述

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

HashMap的数据结构

在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。

从上图中可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。

/**

* The table, resized as necessary. Length MUST Always be a power of two.

*/

transient Entry[] table;

static class Entry<K,V> implements Map.Entry<K,V> {

final K key;

V value;

Entry<K,V> next;

final int hash;

……

}

可以看出,Entry就是数组中的元素,每个 Map.Entry 其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表。

HashMap的存取实现

存储

public V put(K key, V value) {

// HashMap允许存放null键和null值。

// 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。

if (key == null)

return putForNullKey(value);

// 根据key的keyCode重新计算hash值。

int hash = hash(key.hashCode());

// 搜索指定hash值在对应table中的索引。

int i = indexFor(hash, table.length);

// 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。

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;

}

}

// 如果i索引处的Entry为null,表明此处还没有Entry。

modCount++;

// 将key、value添加到i索引处。

addEntry(hash, key, value, i);

return null;

}

从上面的源代码中可以看出:当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标), 如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

addEntry(hash, key, value, i)方法根据计算出的hash值,将key-value对放在数组table的i索引处。addEntry 是 HashMap 提供的一个包访问权限的方法,代码如下:

void addEntry(int hash, K key, V value, int bucketIndex) {

// 获取指定 bucketIndex 索引处的 Entry

Entry<K,V> e = table[bucketIndex];

// 将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry

table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

// 如果 Map 中的 key-value 对的数量超过了极限

if (size++ >= threshold)

// 把 table 对象的长度扩充到原来的2倍。

resize(2 * table.length);

}

当系统决定存储HashMap中的key-value对时,完全没有考虑Entry中的value,仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value 随之保存在那里即可。

hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算,防止低位不变,高位变化时,造成的hash冲突。

static int hash(int h) {

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

我们可以看到在HashMap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表,这样就大大优化了查询的效率。

对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在HashMap中是这样做的:调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下:

static int indexFor(int h, int length) {

return h & (length-1);

}

这个方法非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的 n 次方,这是HashMap在速度上的优化。在 HashMap 构造器中有如下代码:

int capacity = 1;

while (capacity < initialCapacity)

capacity <<= 1;

这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方。

当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

这看上去很简单,其实比较有玄机的,我们举个例子来说明:

假设数组长度分别为15和16,优化后的hash码分别为8和9,那么&运算后的结果如下:

h & (table.length-1) hash table.length-1
8 & (15-1): 0100 & 1110 = 0100
9 & (15-1): 0101 & 1110 = 0100
8 & (16-1): 0100 & 1111 = 0100
9 & (16-1): 0101 & 1111 = 0101

从上面的例子中可以看出:当它们和15-1(1110)“与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到数组中的同一个位置上形成链表,那么查询的时候就需要遍历这个链 表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hash值会与15-1(1110)进行“与”,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!而当数组长度为16时,即为2的n次方时,2n-1得到的二进制数的每个位上的值都为1,这使得在低位上&时,得到的和原hash的低位相同,加之hash(int h)方法对key的hashCode的进一步优化,加入了高位计算,就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。

所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

根据上面 put 方法的源代码可以看出,当程序试图将一个key-value对放入HashMap中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

读取

public V get(Object key) {

if (key == null)

return getForNullKey();

int hash = hash(key.hashCode());

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.equals(k)))

return e.value;

}

return null;

}

有了上面存储时的hash算法作为基础,理解起来这段代码就很容易了。从上面的源代码中可以看出:从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

归纳

简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,

也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

HashMap的resize(rehash)

当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。

那么HashMap什么时候进行扩容呢?当HashMap中的元素个数超过数组大小loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过160.75=12的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

HashMap的性能参数

HashMap 包含如下几个构造器:

  1. HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
  2. ashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。
  3. HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。

HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量initialCapacity和负载因子loadFactor。

负载因子loadFactor衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。

HashMap的实现中,通过threshold字段来判断HashMap的最大容量:

threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时, resize后的HashMap容量是容量的两倍:

Fail-Fast机制

我们知道java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域,modCount顾名思义就是修改次数,对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

HashIterator() {

expectedModCount = modCount;

if (size > 0) { // advance to first entry

Entry[] t = table;

while (index < t.length && (next = t[index++]) == null)

;

}

}

在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map:

注意到modCount声明为volatile,保证线程之间修改的可见性。

final Entry<K,V> nextEntry() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

在HashMap的API中指出:

由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险。

注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。

HashMap的两种遍历方式

第一种

Map map = new HashMap();

Iterator iter = map.entrySet().iterator();

while (iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以后一定要使用此种方式!

第二种

Map map = new HashMap();

Iterator iter = map.keySet().iterator();

while (iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以后尽量少使用!