hashMap算法的兑现

2012-12-26

hashMap算法的实现昨天项目发布间隙，看了下hashmap的算法。关键在于：static int hash(int h) {// This func

hashMap算法的实现
   昨天项目发布间隙，看了下hashmap的算法。关键在于：
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);
}

         和
static int indexFor(int h, int length) {
        return h & (length-1);
}

这2个方法。
注意，这2个方法一定要配合使用，否则就比较难理解了。

这里我解答几个问题，
1.hash方法里传入的是对象的hashCode，而对象的hashCode是对象的内存地址，已经保证了唯一性，为什么还要再进行hash计算？
回答：由于hash表的大小有限，不可能无限大，以hashmap实现中的indexFor方法来讲，是以与操作来计算的。那么假如hashCode转换成二进制以后，末尾相同的话，
那么计算出来的index也就一样了，造成散列度不够。

2.indexFor方法为什么针对length-1做与操作？
回答：与操作将会把超出数组长度的部分截断，另外map初始化的时候会做如下操作：
while (capacity < initialCapacity)
            capacity <<= 1;
这样，length肯定为2的N次方，好处是length-1转换成2进制每一位都是1，在做&操作的时候每一个坑都有机会得到值，否则假如有1位为0的情况，那一位就会浪费。


    3.我这里对hash函数有个疑问，这个算法的目的是把原始数据分成3断进行异或操作达到散列，但是我感觉最后结果的前4位是不会发生变。假如有数据前4位不一样，刚好hash表的长度是后面的28位，那么这个时候就会出现hash冲突了。不知道我这个理解对不对，请大家指正，谢谢。

热点排行

编程

hashMap算法的兑现