|
锁定老帖子 主题：深入理解HashMap
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-12-03
看到一本书，为了减少hashmap的冲突，内部容量长度应是优先选择“素数”，
而不是2^N. 不知道这么一点性能优势的价值能有多少。 |
| 返回顶楼 | |
|
发表时间：2009-12-03
虽然精华了，但是还是要挑挑刺。
annegu 写道 看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！ 所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。这就是真正得原因，很多人即使看过源代码也不知道原因。 说道÷到这里，我们再回头看一下hashmap中默认的数组大小是多少，查看源代码可以得知是16，为什么是16，而不是15，也不是20呢，看到上面annegu的解释之后我们就清楚了吧，显然是因为16是2的整数次幂的原因，在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。 所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)：[/size] // Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
这一段的描述是有些容易误导读者，主要原因是因为搞混了因果关系。 java的hash实现用的是除法求模的方式，是设计一个hash算法最简单的方式之一。 而return h & (length-1);只不过是当length为2的幂的时候的一种求模的代码级的优化而已。为了速度。 如果hashmap的size是15或者其他值时，这行代码会变为return h%size;如此而已。 就hash的算法而言，size是不是2的幂是不重要的，并不会出现lz说的浪费空间问题。这个是由算法决定的。 就java的实现而言，以2的幂为size的大小，是可以得到一些速度上的优势，但是也是有它自己的缺陷的。 那就是hash值的高位没有参与到hash计算中。 如 size=0x100，则对0xab11,0xac11,0xee11的hash计算结果是一样的，都为0x11。在一些特殊的输入，如高位变化，低位不变的情况下，hash冲突很严重。其原因就是只有低位参与了hash计算。 由于2在计算机程序的特殊性，以上也是一个要考虑的东西，所以大部分的算法书在介绍除法模式的hash时，都是建议用质数的。 |
| 返回顶楼 | |
|
发表时间：2009-12-03
blueskit 写道 看到一本书，为了减少hashmap的冲突，内部容量长度应是优先选择“素数”，
而不是2^N. 不知道这么一点性能优势的价值能有多少。 当你用 HashMap 做大数据量缓存的时候，你就能体会到好处了 |
| 返回顶楼 | |
|
发表时间：2009-12-03
最后修改：2009-12-03
blueskit 写道 看到一本书，为了减少hashmap的冲突，内部容量长度应是优先选择“素数”，
而不是2^N. 不知道这么一点性能优势的价值能有多少。 你看的是thinking in java吧，我也曾经被误导过，第4版上写的还是1.5倍后的素数，但是他在注释中写道：经过大量测试表明2的幂作为size效率是最高的，但是遗憾的是作者并没有详细分析原因，如果分析了，那么也不会误导这么多人了，包括lss。 引用 如果hashmap的size是15或者其他值时，这行代码会变为return h%size;如此而已。
这个结论是哪里来的？？ HashTable中是以%的方式来hash的，不过HashTable中更消耗时间是同步 |
| 返回顶楼 | |
|
发表时间：2009-12-03
zhang_xzhi_xjtu 写道 虽然精华了，但是还是要挑挑刺。
annegu 写道 看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！ 所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。这就是真正得原因，很多人即使看过源代码也不知道原因。 说道÷到这里，我们再回头看一下hashmap中默认的数组大小是多少，查看源代码可以得知是16，为什么是16，而不是15，也不是20呢，看到上面annegu的解释之后我们就清楚了吧，显然是因为16是2的整数次幂的原因，在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。 所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)：[/size] // Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
这一段的描述是有些容易误导读者，主要原因是因为搞混了因果关系。 java的hash实现用的是除法求模的方式，是设计一个hash算法最简单的方式之一。 而return h & (length-1);只不过是当length为2的幂的时候的一种求模的代码级的优化而已。为了速度。 如果hashmap的size是15或者其他值时，这行代码会变为return h%size;如此而已。 就hash的算法而言，size是不是2的幂是不重要的，并不会出现lz说的浪费空间问题。这个是由算法决定的。 就java的实现而言，以2的幂为size的大小，是可以得到一些速度上的优势，但是也是有它自己的缺陷的。 那就是hash值的高位没有参与到hash计算中。 如 size=0x100，则对0xab11,0xac11,0xee11的hash计算结果是一样的，都为0x11。在一些特殊的输入，如高位变化，低位不变的情况下，hash冲突很严重。其原因就是只有低位参与了hash计算。 由于2在计算机程序的特殊性，以上也是一个要考虑的东西，所以大部分的算法书在介绍除法模式的hash时，都是建议用质数的。 事实上，HashMap考虑了你说到的这种情况，对hash值做了处理，加入了高位的计算：
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
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);
}
|
| 返回顶楼 | |
|
发表时间：2009-12-03
zhang_xzhi_xjtu 写道 虽然精华了，但是还是要挑挑刺。
annegu 写道 看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！ 所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。这就是真正得原因，很多人即使看过源代码也不知道原因。 说道÷到这里，我们再回头看一下hashmap中默认的数组大小是多少，查看源代码可以得知是16，为什么是16，而不是15，也不是20呢，看到上面annegu的解释之后我们就清楚了吧，显然是因为16是2的整数次幂的原因，在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。 所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)：[/size] // Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
这一段的描述是有些容易误导读者，主要原因是因为搞混了因果关系。 java的hash实现用的是除法求模的方式，是设计一个hash算法最简单的方式之一。 而return h & (length-1);只不过是当length为2的幂的时候的一种求模的代码级的优化而已。为了速度。 如果hashmap的size是15或者其他值时，这行代码会变为return h%size;如此而已。 就hash的算法而言，size是不是2的幂是不重要的，并不会出现lz说的浪费空间问题。这个是由算法决定的。 就java的实现而言，以2的幂为size的大小，是可以得到一些速度上的优势，但是也是有它自己的缺陷的。 那就是hash值的高位没有参与到hash计算中。 如 size=0x100，则对0xab11,0xac11,0xee11的hash计算结果是一样的，都为0x11。在一些特殊的输入，如高位变化，低位不变的情况下，hash冲突很严重。其原因就是只有低位参与了hash计算。 由于2在计算机程序的特殊性，以上也是一个要考虑的东西，所以大部分的算法书在介绍除法模式的hash时，都是建议用质数的。 引用 高位变化，低位不变的情况下，hash冲突很严重
高位低位先求和，然后再hash函数的吧！ |
| 返回顶楼 | |
|
发表时间：2009-12-03
哎呀！大哥
最近找工作正在学习回顾这些东西 受教了 另外 困惑于 Map 如何实现Key的快速查找？ |
| 返回顶楼 | |
|
发表时间：2009-12-03
这都精华了，
哎，我写了个介绍各种常见数据结构（ArrayList Hashmap/table。。。）的jdk实现和.net实现的原理分析的， 发到 算法和数据结构版本，被新手帖了。。。 哎，以后写啥都发java版。 |
| 返回顶楼 | |
|
发表时间：2009-12-03
楼主我现身啦~
zhang_xzhi_xjtu 写道 java的hash实现用的是除法求模的方式，是设计一个hash算法最简单的方式之一。 而return h & (length-1);只不过是当length为2的幂的时候的一种求模的代码级的优化而已。为了速度。 这句话是对的，用“与”操作确实是为了速度。 zhang_xzhi_xjtu 写道 如果hashmap的size是15或者其他值时，这行代码会变为return h%size;如此而已。 这是错的！hashmap的代码里面根本没有“%”。hashmap的table[]的大小也不会是15这种不是2的次方的，table的大小一定是2次幂。看下面： // Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
table = new Entry[capacity];
|
| 返回顶楼 | |
|
发表时间：2009-12-03
火星来客 写道 blueskit 写道 看到一本书，为了减少hashmap的冲突，内部容量长度应是优先选择“素数”，
而不是2^N. 不知道这么一点性能优势的价值能有多少。 你看的是thinking in java吧，我也曾经被误导过，第4版上写的还是1.5倍后的素数，但是他在注释中写道：经过大量测试表明2的幂作为size效率是最高的，但是遗憾的是作者并没有详细分析原因，如果分析了，那么也不会误导这么多人了，包括lss。 引用 如果hashmap的size是15或者其他值时，这行代码会变为return h%size;如此而已。
这个结论是哪里来的？？ HashTable中是以%的方式来hash的，不过HashTable中更消耗时间是同步 请从理论上阐明2的幂作为size效率是最高的。 HashMap是用的&,HashTable用的是%,这里我的意思是说求模是算法，而如何求是实现。不知道??是问什么？ |
| 返回顶楼 | |
