|
锁定老帖子 主题：HashMap深度分析
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-07-19
引用 为啥默认的最大容量为2**30，而不是2**31-1呢？ 最大容量%2应该等于0. |
| 返回顶楼 | |
|
发表时间：2011-07-25
分析的很棒..以前我也看过这个源代码..但是没用去细细推敲..collection framework写的很清晰的, joush block大师的杰作...看过大这个框架的大部分代码, 但是, 没有去细细推敲...所以, 现在没什么印象了...看完楼主的分析, 感觉真好..
|
| 返回顶楼 | |
|
发表时间：2011-07-26
最后修改：2011-07-26
uule 写道 zhang34082 写道 在方法中：
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
由于 使用了新的newCapacity,indexFor出来的值 就不会一样，这一句 e.next = newTable[i]; 为什么不写成 e.next = null; 希望牛人回答 --- 呵呵 想明白了  我也有这个疑问。。。什么原因？ 假设数组初始容量为 4 元素A的hash为 1101 ,在 table中的index为 1101 & 11=01 元素B的hash为 1001 ,在 table中的index为 1001 & 11=01 所以他们是挂在同个index下的链表上的 当数组扩容到了8后 元素A的在新 table中的index为 1101 & 111=101 元素B的在新 table中的index为 1001 & 111=001 他们在新table中是不能挂在同个index下的链表上了 假设还有个C的hash与B相同，那么在旧table中他们3是挂在同个list上的 而在新的table上只有B、C是在同个list上了 这就是为什么扩容后需要再hash，因为在新table中分布已经变了 |
| 返回顶楼 | |
|
发表时间：2011-07-26
最后修改：2011-07-26
引用 所以length-1一定是个奇数，假设现在长度为16，减去1后就是15，对应的二进制是：1111。 假设有两个元素，一个哈希值是8，二进制是1000，一个哈希值是9，二进制是1001。和1111与运算后，分别还是1000和1001，它们被分配在了数组的不同位置，这样，哈希的分布非常均匀。 那么，如果数组长度是奇数，减去1后就是偶数了，偶数对应的二进制最低位一定是0了，例如14二进制1110。对上面两个数子分别与运算，得到1000和1000。看到了吗？都是一样的值，哈希值8和9的元素多被存储在数组同一个位置的链表中。在操作的时候，链表中的元素越多，效率越低，因为要不停的对链表循环比较。所以，一定要哈希均匀分布，尽量减少哈希冲突，减少了哈希冲突，就减少了链表循环，就提高了效率。 这么解释有点因果不清了 为什么要这么做其实得从hash的内部存储分析 因为table是个数组，indexFor根据hash计算在table中存储的index值要落在区间 [0,length-1] 内
static int indexFor(int h, int length) {
return h & (length-1);
}
与 length-1 进行 & 的结果就是index（也就是其值刚好落在上述区间内），这才是 【因】。 同时，元素的分布还是应该由hash值决定，indexFor不应该改变hash的分布 （实际上indexFor的操作结果是个均匀分布，这就好比数学里的 n*1=n ）。 为了实现一个存储均匀分布的indexFor函数，所以要求length-1的值是 11111...（二进制位所有位上的值为1）的。 于是才有了要求length为2的次方的 【果】。 PS: HashMap中的那个 hash函数
static int hash(int h) {
return useNewHash ? newHash(h) : oldHash(h);
}
oldHash的具体原理没深入，但我分析这是为了处理： 当Map较小时，存入数据的hash在高位(大数范畴内)分布均匀，而在低位（小数范畴内）分布不均匀的情况。 |
| 返回顶楼 | |
|
发表时间：2011-07-26
h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); 这个hash的算法一直没明白，有大牛能给讲讲为什么要这样吗？ |
| 返回顶楼 | |
|
发表时间：2011-07-27
最后修改：2011-07-27
不错，分享了！
另外，从楼主的观点来看，代码： /**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
length -1 的原因是由于奇偶效应，而楼上却有人说是区间效应。我觉得都有道理，不知道楼主目前的理解是怎样的 |
| 返回顶楼 | |
|
发表时间：2011-07-27
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] 这个例子有点问题吧，2与3和7的i值都是2,怎么会是6呢？ |
| 返回顶楼 | |
|
发表时间：2011-07-30
佩服楼主，分析的这么透彻，并发下有时还是使用HashMap的需要,
楼主可以试试 Collections.synchronizedMap(new HashMap()); 这样获取的是个线程安全的HashMap |
| 返回顶楼 | |
