java.util.HashMap源码要点浅析
1、散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式,链表是单向链表,因此在删除过程中要自己维持prev节点,我想不采用双向链表是从节省空间考虑。一个典型的查找过程:
for (EntryK,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;
}
HashMap采用链表法而不是开放地址法,猜想可能的原因是从实用角度出发,对空间和时间效率做出的折中选择。采用开放地址法,无论是线性探测或者二次探测都可能造成群集现象,而双重散列会要求散列表的装填程度比较低的情况下会有比较好的查找效率,容易造成空间的浪费。
2、什么是负载因子?负载因子a定义为
a=散列表的实际元素数目(n)/ 散列表的容量(m)
负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是 O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。
回到HashMap的实现,HashMap中的loadFactor其实定义的就是该map对象允许的最大的负载因子,如果超过这个系数将重新resize。这个是通过threshold字段来判断,看threshold的计算:
threshold = (int)(capacity * loadFactor);
结合上面的负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。注意到的一点是resize的规模是现有 capacity的两倍:
if (size++ >= threshold)
resize(2 * table.length);
3、可能你也注意到了,java.util.HashMap对key的hash值多做了一步处理,而不是直接使用hashCode:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
这个处理的原因在于HashMap的容量总是采用2的p次幂,而取index(槽位)的方法是
static int indexFor(int h, int length) {
return h & (length-1);
}
这一运算等价于对length取模,也就是
h % 2^p
返回的将是h的p个最低位组成的数字,我们假设hash输入是符合简单一致散列,然而这一假设并不能推论出hash的p个最低位也会符合简单一致散列,也许h的这p个最低位相同的几率很大,那么冲突的几率就非常大了。优秀的散列函数应该需要考虑所有的位。
因此为了防止这些“坏”的散列函数造成效率的降低,HashMap预先对hash值做了处理以考虑到所有的位,根据注释也可以知道。这个处理我看不懂,留待高人解释,也许来自于某本算法书也不一定。
4、我们知道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
final EntryK,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
注意到modCount声明为volatile,保证线程之间修改的可见性。
分享到:
相关推荐
本文通过对数据压缩算法的简要介绍,然后以详细的示例演示了利用java.util.zip包实现数据的压缩与解压,并扩展到在网络传输方面如何应用java.util.zip包现数据压缩与解压
1. java.util.concurrent - Java 并发工具包 2. 阻塞队列 BlockingQueue 3. 数组阻塞队列 ArrayBlockingQueue 4. 延迟队列 DelayQueue 5. 链阻塞队列 LinkedBlockingQueue 6. 具有优先级的阻塞队列 ...
java.util.ConcurrentModificationException 异常问题详解1
java.util包源码,pdf版,方便打印
详细介绍了java.util.logging.Logger的用法和结构,对如果扩展Logger起到抛砖引玉的作用!尊重劳动成果,亲下载了要给个评价!
Tomcat内存溢出的解决方法(java.util.concurrent.ExecutionException:java.lang.OutOfMemoryError),内附解决方案!
Exception in thread “main“ java.util.InputMismatchException
java.util.ConcurrentModificationException 解决方法 ... at java.util.HashMap$HashIterator.nextEntry(HashMap.java:793) at java.util.HashMap$KeyIterator.next(HashMap.java:828) 例如以下程序(转
Java完成zip压缩源码,包括修改后的java.util.zip下的文件(可以解决中文文件名的问题)
java.util.Date与java.sql.Date互转及字符串转换为日期时间格式.docx
java.util.concurrent系列文章(1) java.util.concurrent系列文章(1) java.util.concurrent系列文章(1) java.util.concurrent系列文章(1)
java并发工具包 java.util.concurrent中文版-带书签版
详细介绍java.util.Date和java.sql.Date相互转换的多种方法总结,希望对大家有帮助
这是我在编写struts2中遇到的问题,整理出来,包括截图,希望可以帮到大家
java.util包
世界范围内的时区列表。由 java.util.TimeZone 类导出
使用java.util.timer实现的简单定时任务,在实现简单一次性定时任务时,使用java.util.timer非常的简单易用,适合没有接触过quartz的新手急用。
java.util.pdf
java.util包总结,方便大家学习。请多指教。
java.util.concurrent总体概览图。 收取资源分3分。需要的同学可以下载一下。 java.util.concurrent主要包括5个部分executor,colletions,locks,atomic,tools。 该图详细的列举了并发包下面的结构,包含所有接口和...