|
锁定老帖子 主题：HashMap深度分析
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-02-18
最后修改：2011-02-18
在方法中：
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; 希望牛人回答 --- 呵呵 想明白了 
|
| 返回顶楼 | |
|
发表时间：2011-02-18
又被翻出来了，不过我还是仔细看了一把
个人感觉下面引用里面提到的死循环不是那么回事吧，就纯粹的resize来讲，e1和本身不会是个闭环... el的next应该是null(就引用里面的例子...) 闭环应该是在多线程同时扩容的时候可能产生,因为扩容的时候会把entry链表反序... Refer:http://pt.alibaba-inc.com/wp/dev_related_969/hashmap-result-in-improper-use-cpu-100-of-the-problem-investigated.html ch_space 写道 死锁是扩容操作与put或get方法并发引起的，看源码： 引用 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;//切换2 e = next; } while (e != null); } } } //get()
for (Entry<K,V> e = table[indexFor(hash, table.length)];//切换1
e != null;
e = e.next)
table初始状态： 
假设执行get的线程1在e = table[indexFor(hash, table.length)]后进行“切换1”，切换到线程2的put方法，而且进行了扩容。此时table和newTable的状态是： 
线程2在newTable[i] = e后进行“切换2”，继续执行线程1的get，在for循环里e.next==e，永远不为空，若 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))不满足，则进入了死循环。 |
| 返回顶楼 | |
|
发表时间：2011-04-10
楼主威武，受教
|
| 返回顶楼 | |
|
发表时间：2011-04-11
HashMap 是个好东西。。常用
|
| 返回顶楼 | |
|
发表时间：2011-07-12
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; 希望牛人回答 --- 呵呵 想明白了 我也有这个疑问。。。什么原因？ |
| 返回顶楼 | |
|
发表时间：2011-07-12
我承认我没看懂 先自己研究一下，再看这里的分析
|
| 返回顶楼 | |
|
发表时间：2011-07-18
最后修改：2011-07-18
static int indexFor(int h, int length) {
return h & (length-1);
}
“h & (length-1)”其实这里是很有讲究的，为什么是和(length-1)进行按位与运算呢？这样做是为了提高HashMap的效率。什么？这样能提高效率？且听我细细道来。 首先我们要确定一下，HashMap的数组长度永远都是偶数，即使你在初始化的时候是这样的new HashMap(15,0.75);因为在构造函数内部，上面也讲过，有这样的一段代码： while (capacity 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;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
jdk哪有这么神秘？真以为每行代码都是高效率的啊？ 这操作只是理所当然的操作，你自己去实现，一样会加这行代码：求余而已~不求余显然会出问题的，即使是奇数，一样要求余的~而且在均匀分布来讲，也是一样的，取决于hash函数而已 hashmap有这么高深吗？不就一个hash函数吗 |
| 返回顶楼 | |
|
发表时间：2011-07-18
最后修改：2011-07-18
zhang34082 写道 static int indexFor(int h, int length) {
return h & (length-1);
}
“h & (length-1)”其实这里是很有讲究的，为什么是和(length-1)进行按位与运算呢？这样做是为了提高HashMap的效率。什么？这样能提高效率？且听我细细道来。 首先我们要确定一下，HashMap的数组长度永远都是偶数，即使你在初始化的时候是这样的new HashMap(15,0.75);因为在构造函数内部，上面也讲过，有这样的一段代码： while (capacity 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;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}jdk哪有这么神秘？真以为每行代码都是高效率的啊？ 这操作只是理所当然的操作，你自己去实现，一样会加这行代码：求余而已~不求余显然会出问题的，即使是奇数，一样要求余的~而且在均匀分布来讲，也是一样的，取决于hash函数而已 hashmap有这么高深吗？不就一个hash函数吗 |
| 返回顶楼 | |
|
发表时间：2011-07-18
snake1987 写道 zhang34082 写道 static int indexFor(int h, int length) {
return h & (length-1);
}
“h & (length-1)”其实这里是很有讲究的，为什么是和(length-1)进行按位与运算呢？这样做是为了提高HashMap的效率。什么？这样能提高效率？且听我细细道来。 首先我们要确定一下，HashMap的数组长度永远都是偶数，即使你在初始化的时候是这样的new HashMap(15,0.75);因为在构造函数内部，上面也讲过，有这样的一段代码： while (capacity 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;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}jdk哪有这么神秘？真以为每行代码都是高效率的啊？ 这操作只是理所当然的操作，你自己去实现，一样会加这行代码：求余而已~不求余显然会出问题的，即使是奇数，一样要求余的~而且在均匀分布来讲，也是一样的，取决于hash函数而已 hashmap有这么高深吗？不就一个hash函数吗 的确，分布的均匀与否，跟与运算没关系，主要还是hash计算 |
| 返回顶楼 | |
|
发表时间：2011-07-18
hash算法分布均匀，同时要保证容量的选择能够保证hash的均匀性，二者缺一不可
|
| 返回顶楼 | |
