|
锁定老帖子 主题：HashMap深度分析
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-09-07
这一定是对源码的分析总结，非常不错。源码当中有很多细节值得借鉴和学习。
|
| 返回顶楼 | |
|
发表时间：2010-09-08
netingcn 写道 cash-007 写道 resize后
k.hashCode()) 定值 hash(k.hashCode());定值 indexFor(hash, table.length);因为table.length 翻倍了，所以计算出的位置肯定会有变化。但是hash值是不会变的。 比如 扩容前 length×2后 length 4 8 length-1 11(3) 111(7) hashcode 10(2) 10(2) i值 10(2) 110(6) 所以扩容前在table[2]位置，扩容后就在table[6] 扩容前 length×2后 length 4 8 length-1 11(3) 111(7) hashcode 10(2) 010(2) i值 10(2) 010(2) 我写了一个例子，观察了一下，确实i的值没有变化， 另外，我发现jdk6中，resize似乎有优化，比如我插入10000个对象，用new HashMap()和new HashMap(10000),运行的时间基本一致。 还有补充一下，HashMap的容量永远是2的N次方（当然肯定是偶数），这样的作的目的是提高Map的效率，因为当length - 1的二进制总是111...111,这样计算indexFor时得到的结果永远是小于Map的长度的。  我错了。。。。 忘记左补0了
|
| 返回顶楼 | |
|
发表时间：2010-09-10
如果执行new HashMap(9,0.75)；那么HashMap的初始容量是16，而不是9，想想为什么吧。 初始容量应该是18吧
|
| 返回顶楼 | |
|
发表时间：2010-09-10
jiang562 写道 如果执行new HashMap(9,0.75)；那么HashMap的初始容量是16，而不是9，想想为什么吧。 初始容量应该是18吧
你没有仔细看我的帖子，我不想再讲，你可以回头看看，是16还是18，如果你不明白你可以动手验证一下。 |
| 返回顶楼 | |
|
发表时间：2010-09-13
cash-007 写道 netingcn 写道 cash-007 写道 resize后
k.hashCode()) 定值 hash(k.hashCode());定值 indexFor(hash, table.length);因为table.length 翻倍了，所以计算出的位置肯定会有变化。但是hash值是不会变的。 比如 扩容前 length×2后 length 4 8 length-1 11(3) 111(7) hashcode 10(2) 10(2) i值 10(2) 110(6) 所以扩容前在table[2]位置，扩容后就在table[6] 扩容前 length×2后 length 4 8 length-1 11(3) 111(7) hashcode 10(2) 010(2) i值 10(2) 010(2) 我写了一个例子，观察了一下，确实i的值没有变化， 另外，我发现jdk6中，resize似乎有优化，比如我插入10000个对象，用new HashMap()和new HashMap(10000),运行的时间基本一致。 还有补充一下，HashMap的容量永远是2的N次方（当然肯定是偶数），这样的作的目的是提高Map的效率，因为当length - 1的二进制总是111...111,这样计算indexFor时得到的结果永远是小于Map的长度的。 我错了。。。。 忘记左补0了有点不理解。1、既然扩容后i值不变，为什么还要费时重新hash。 2、transfer中e.next = newTable[i];这句是干嘛用的。看下来好像就是这句导致的闭环。 |
| 返回顶楼 | |
|
发表时间：2010-09-14
会引起链表的闭环
链表的闭环 什么意思。 楼主能解释下吗？ |
| 返回顶楼 | |
|
发表时间：2010-09-15
string2020 写道 会引起链表的闭环
链表的闭环 什么意思。 楼主能解释下吗？ 你喜欢我，我不喜欢你，我喜欢ta；ta不喜欢我，ta喜欢你，你不喜欢ta。。。。 一个复杂的闭环关系。。。。 |
| 返回顶楼 | |
|
发表时间：2010-11-28
最后修改：2010-11-28
重复的删了
|
| 返回顶楼 | |
|
发表时间：2010-11-28
jameswxx 写道 netingcn 写道 cash-007 写道 resize后
k.hashCode()) 定值 hash(k.hashCode());定值 indexFor(hash, table.length);因为table.length 翻倍了，所以计算出的位置肯定会有变化。但是hash值是不会变的。 比如 扩容前 length×2后 length 4 8 length-1 11(3) 111(7) hashcode 10(2) 10(2) i值 10(2) 110(6) 所以扩容前在table[2]位置，扩容后就在table[6] 扩容前 length×2后 length 4 8 length-1 11(3) 111(7) hashcode 10(2) 010(2) i值 10(2) 010(2) 我写了一个例子，观察了一下，确实i的值没有变化， 另外，我发现jdk6中，resize似乎有优化，比如我插入10000个对象，用new HashMap()和new HashMap(10000),运行的时间基本一致。 还有补充一下，HashMap的容量永远是2的N次方（当然肯定是偶数），这样的作的目的是提高Map的效率，因为当length - 1的二进制总是111...111,这样计算indexFor时得到的结果永远是小于Map的长度的。 你说对了结果，但是没有说对原因，“HashMap的容量永远是2的N次方（当然肯定是偶数），这样的作的目的是提高Map的效率”，的确如此，“因为当length - 1的二进制总是111...111,这样计算indexFor时得到的结果永远是小于Map的长度的”，你说的这个是错误的，要知道，一个大数字和一个小数字按位与运算，结果永远不可能大于大数字，HashMap里的这种做法是为了使数据能够更均匀的分布到数组里，我在帖子里已经详细讲过了。 有那么复杂嘛 “h & (length-1)” 就是取正数吧 hashMap分配均匀否是那个很tricky的static int hash(int h)决定的 |
| 返回顶楼 | |
|
发表时间：2010-12-03
niumd 写道 finux 写道 jameswxx 写道 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; 为啥默认的最大容量为2**30，而不是2**31-1呢？ 整数的最大范围是：-2的31次方到2的31次方-1，容量不会有负数，估计设计者选择的正负数的和； 人家是低调点，有所保留，呵呵 |
| 返回顶楼 | |
