- 浏览: 497623 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (200)
- java基础 (30)
- ajax (19)
- 乱写 (5)
- groovy (2)
- db (8)
- gwt (0)
- jee (2)
- 我关注的开源 (1)
- RIA AIR (1)
- spring (11)
- lucene (0)
- 工具 (10)
- 百科 (2)
- linux (6)
- android (40)
- 移动开发 (21)
- 代码片断 (15)
- tomcat (1)
- css (1)
- html5 (2)
- jquery (2)
- playframework (3)
- web (2)
- nio (3)
- design (1)
- nosql (3)
- 日志 (12)
- mysql (4)
- 图表 (1)
- python (3)
- ruby (1)
- git (0)
- hibernate (1)
- springboot (1)
- guava (1)
- mybatis (0)
- 工作问题 (3)
- php (1)
最新评论
-
linzm1990:
踩了很多坑啊。。。。
hibernate @Nofound 与@ManyToOne fetch lazy的问题 -
Ccccrrrrrr:
...
转: Spring boot 文件上传 -
rmzdb:
兄弟,你这个东西,在ie内核的浏览器,貌似不识别 文件名
工作问题:http下载文件,中文文件名在firefox下乱码问题 -
107x:
问题解决了,谢谢!
工作问题:http下载文件,中文文件名在firefox下乱码问题 -
klxqljq:
额鹅鹅鹅
android布局实现头尾固定, 中间多余内容可以滚动
转自 http://www.blogjava.net/killme2008/archive/2009/04/15/265721.html
1、散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式,链表是单向链表,因此在删除过程中要自己维持prev节点,我想不采用双向链表是从节省空间考虑。一个典型的查找过程:
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就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。注意到的一点是resize的规模是现有 capacity的两倍:
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(槽位)的方法是
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 Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
注意到modCount声明为volatile,保证线程之间修改的可见性。
发表评论
-
ChartDirectorvk如何测试文本的长度跟宽度
2012-11-30 15:53 1098在使用charDirector画图时, 要确定setPlotA ... -
Java调用外部程序技巧
2012-08-24 13:43 1280http://www.yankay.com/java%E8%B ... -
java中的协变
2012-08-14 09:10 1117协变是指一个类型随着它关联的类型一起变化,有点抽像,java中 ... -
jdbm
2012-07-11 15:20 1304jdbm4也发布部分代码了, ... -
使用java实现grep功能(FileChannel, Pattern, MappedByteBuffer 直接字节缓冲区,其内容是文件的内存映射区域)
2012-02-23 10:42 2925利用正则表达式查找一系列文件,类似于grep功能. 演示了 N ... -
并发--Effective Java的一小段代码
2012-02-20 17:14 1174import java.util.concurrent.T ... -
JAVA使用EPoll来进行NIO处理的方法
2012-02-14 09:20 997JDK 6.0 以及JDK 5.0 update 9 的 ni ... -
java里的枚举
2011-12-30 15:03 1115参考: http://www.ibm.com/develope ... -
项目中用到的一个小工具类(字符过滤器)
2011-10-25 09:08 1025见: http://javatar.iteye.com/blo ... -
下载处理Servlet工具类
2011-10-25 09:06 937转自 http://javatar.iteye.com/blo ... -
局部类访问外部final变量
2011-01-26 12:21 1110在局部类, 我们要更新封闭作用域用的变量, 这一般来说是不容易 ... -
tomcat开启gzip
2011-01-21 13:46 1177在conf/server.xml中找到第一个Connector ... -
maven中国地址
2011-01-06 13:37 3295maven的中国mirror <mirror> ... -
java范型小记
2010-12-18 17:51 01. Collections.<String>em ... -
jsp里的${}和jquery template的${} 怎么样转义
2010-12-16 14:38 4765ttp://www.infoq.com/cn/news/201 ... -
正则表达式
2010-11-30 08:27 1351由于项目中需要用到正则表达式,再一每次使用正则表达式时都要查资 ... -
Java Web 应用程序的字符编码问题
2010-11-30 08:13 1068Java Web 应用程序经常会出现乱码的情况,这里可以通过 ... -
异常的限制
2010-11-30 08:09 1032java 程序声明异常时,父类的某个方法声明了异常的抛出,那 ... -
JVM参数调优(带JMX)
2010-09-09 08:48 1359JAVA_OPTS='-d64-Djava.rmi.serve ... -
java Bridge method
2010-08-06 15:15 2267bridge method may be create ...
相关推荐
本文通过对数据压缩算法的简要介绍,然后以详细的示例演示了利用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。 该图详细的列举了并发包下面的结构,包含所有接口和...