HashMap的脚标寻址浅谈

HashMap的脚标对应的是应散列表的脚标,是通过hash得到的散列码进行映射的。JDK中hash算法的实现及脚标映射决定着HashMap的性能。下面我简单地聊聊HashMap中的hash及脚标映射算法。
首先解释一下hashCode,所谓hashCode指的是系统经过hash算法生成的唯一的32位整数值。
HashMap的hash函数源码如下:

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

(h = key.hashCode()) ^ (h >>> 16)操作是将key的hashCode的高16位移到低16位,然后再于key的hashCode取异或运算,这样使得计算出的hash值具有高位和低位的性质。
而寻址或者插入元素时,采用hash函数计算出来的hashCode与散列表的大小减一做位与运算,确定脚标的代码为:

(tab.length - 1) & hash(key)  //tab.length指的是散列表的大小

以上代码表名散列表中元素的脚标实质上是其key的hashCode值对散列表的大小进行“除留余数法”后得到的值。式中公式有一个前提,当且仅当B为2的正整数倍时,下列等式成立:
A % B = A & (B - 1)
这也就解释了,为什么Java建议初始化HashMap时初始大小为2的整数倍,当然不设置为2的整数倍也没关系,HashMap初始化时会调用tableSizeFor方法,将散列表大小设置为不小于指定数值的2的最小次幂,源代码如下:

    static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

可以看出,HashMap由key进行寻址时的算法非常巧妙,通过key的hashCode位移并高低位异或运算使得到的值均匀地散列开,再通过“除留余数法”得到该key对应的散列表的脚标。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容