浅谈HashMap中的hash算法

HashMap是我们常见的一种数据结构,实现Map接口,用来存储键值对,允许null键/值、非同步、不保证有序(比如插入的顺序)。那HashMap中最核心的部分就是哈希函数,又称散列函数。也就是说,哈希函数是通过把key的hash值映射到数组中的一个位置来进行访问。比如:

存在一组哈希值 10,13,7,5,4,20
存在一个长度为10的数组 arrays
定义一个hash函数 int index = h % arrays.length; 

10 % 10 = 0 那么 哈希值为10的对象放在数组索引为0的位置上;
13 % 10 = 3 那么 哈希值为13的对象放在数组索引为3的位置上;
......
20 % 10 = 0 那么 哈希值为13的对象放在数组索引为0的位置上;

这时候大家看出了一个问题,哈希值为10的对象和哈希值为20的对象,放在了一个索引上。发生了碰撞,那么怎么解决这样碰撞呢,有很多种方式,这里不展开叙述。HashMap中维护了一个链表组成的数组。如果冲突的话就添加到链表中,下面来看下hashmap中的hash算法,以Java8源码为例。

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

其中,key.hashCode()是Key自带的hashCode()方法,返回一个int类型的散列值。我们大家知道,32位带符号的int表值范围从-2147483648到2147483648。这样只要hash函数松散的话,一般是很难发生碰撞的,因为HashMap的初始容量只有16。但是这样的散列值我们是不能直接拿来用的。用之前需要对数组的长度取模运算。得到余数才是索引值。我们来看下HashMap中怎么实现的。

int index = hash & (arrays.length-1);

那么这也就明白了为什么HashMap的数组长度是2的整数幂。比如以初始长度为16为例,16-1 = 15,15的二进制数位00000000 00000000 00001111。可以看出一个基数二进制最后一位必然位1,当与一个hash值进行与运算时,最后一位可能是0也可能是1。但偶数与一个hash值进行与运算最后一位必然为0,造成有些位置永远映射不上值。
但是这时,又出现了一个问题,即使散列函数很松散,但只取最后几位碰撞也会很严重。这时候hash算法的价值就体现出来了,
扰动函数
hashCode右移16位,正好是32bit的一半。与自己本身做异或操作(相同为0,不同为1)。就是为了混合哈希值的高位和地位,增加低位的随机性。并且混合后的值也变相保持了高位的特征。

HashMap中用到的编码思想确实很值得我们学习。HashMap在Java1.8后又进行了优化,比如引入红黑树的数据结构和扩容的优化等。有机会我们再结合Java1.8聊聊,HashMap get()和put()实现原理,装载因子,resize()方法还有红黑树等。