浅谈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()方法还有红黑树等。

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

推荐阅读更多精彩内容

  • 众所周知,HashMap 是一个用于存储Key-Value键值对的集合,每一个键值对也叫做 Entry。 这些个键...
    luckyboy2阅读 7,550评论 0 1
  • 1.什么是HashMap 基于哈希表的Map接口的非同步实现 此实现提供所有可选的映射操作,并允许使用null值和...
    苍賢阅读 3,411评论 0 1
  • HashMap是Map接口的一个实现。Map的实现都是一个容器,用于存储键值对。 Map并不一定要通过散列表实现,...
    刘惜有阅读 3,909评论 0 1
  • 如果说Java的HashMap是数组+链表,那么JDK 8之后就是数组+链表+红黑树组成了HashMap。 在之前...
    Java_Explorer阅读 4,535评论 1 5
  • 背景 facebook开源的一个强大的图片加载组件。使用之后,不需要关心图片的加载和显示这些繁琐的事情,支持And...
    johnnycmj阅读 6,680评论 0 0