|
锁定老帖子 主题：三顾java.util.HashMap
精华帖 (0) :: 良好帖 (1) :: 新手帖 (0) :: 隐藏帖 (2)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-04-12
贾懂凯 写道 s929498110 写道 贾懂凯 写道 s929498110 写道 第三点
我感觉装载因子好像不推荐修改吧？ 如果一次性容量扩充比较大的话 可以自己设定扩充倍数数量级的 但是说实话。装载因子的使用经验几乎为零。。。现在读大二，实战经验也没多少。就不发表意见了。。。 如何自己设定扩充数量级？ 下面的是我在HashMap中见到的方法， 这个方法应该可以将原来为 2^n 的容量扩充为 2^m 的容量吧？ 说实话。。。没试过。。。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
 话说， 我们系有一个女生叫贾轶凯，名字挺像的容量扩充的倍数在方法addEntry里面写死了： if (size++ >= threshold) resize(2 * table.length); 为2 没有必要自定义扩容呀，再说，写Java的人，很少关注算法，如果算法强的话，可以自行研究一套算法重新实现。 至于为什么是倍数是2，是为了防止hash 冲突。 |
| 返回顶楼 | |
|
发表时间：2011-04-12
贾懂凯 写道 s929498110 写道 贾懂凯 写道 s929498110 写道 第三点
我感觉装载因子好像不推荐修改吧？ 如果一次性容量扩充比较大的话 可以自己设定扩充倍数数量级的 但是说实话。装载因子的使用经验几乎为零。。。现在读大二，实战经验也没多少。就不发表意见了。。。 如何自己设定扩充数量级？ 下面的是我在HashMap中见到的方法， 这个方法应该可以将原来为 2^n 的容量扩充为 2^m 的容量吧？ 说实话。。。没试过。。。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
话说， 我们系有一个女生叫贾轶凯，名字挺像的容量扩充的倍数在方法addEntry里面写死了： if (size++ >= threshold) resize(2 * table.length); 为2 被封装起来了？ 没注意。。。不好意思啊 那样如果想使用估计得自己写一个子类实现了 |
| 返回顶楼 | |
|
发表时间：2011-04-13
看下C数据结构里面的Hash
|
| 返回顶楼 | |
|
发表时间：2011-04-13
要向楼主学习了。
|
| 返回顶楼 | |
|
发表时间：2011-04-13
贾懂凯 写道 b 这个算法我不是很理解 static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
这个方法到底何用，注解了说使得哈希码的重码率降低了，我还是不明白如何能使其降低呢？难道这个方法里的算法有什么精妙之处？大家发发言 这个是和indexFor 联合起来用的，因为HashMap 的table size 都是2 的倍数，而且index = h & (length - 1)，所以获得的index 的位置一般都取决于hash 的低位bits。你可以根据这个hash 算法移位看下，在低四位（也就是hashMap size 16）的情况下，这个int 里面的32bits总共有多少bits 参与了hash 运算，这就是最大可能保证了不冲突的情况 |
| 返回顶楼 | |
|
发表时间：2011-04-13
最后修改：2011-04-13
引用 这个是和indexFor 联合起来用的，因为HashMap 的table size 都是2 的倍数，而且index = h & (length - 1)，所以获得的index 的位置一般都取决于hash 的低位bits。你可以根据这个hash 算法移位看下，在低四位（也就是hashMap size 16）的情况下，这个int 里面的32bits总共有多少bits 参与了hash 运算，这就是最大可能保证了不冲突的情况
一时也看不出为什么用这个算法，也许经过测试这个算法误码率相对比较低并且各种情况下表现都比较好吧。 |
| 返回顶楼 | |
|
发表时间：2011-04-13
dopic 写道 看下C数据结构里面的Hash
个人觉得算法和数据结构应该无关实现语言。 |
| 返回顶楼 | |
