今天给大家分享一下HashMap内部的实现原理, 这一块也是在面试过程当中基础部分被问得比较多的一部分。
想要搞清楚HashMap内部的实现原理,我们需要先对一些基本的概念有一些了解, 这些概念包括什么是hash、什么是hash表、什么是hashcode? 有了这些基本概念之后, 我们再去分析Hashmap,就相对来讲简单了一些。
什么是Hash
哈希(hash)简单理解就是将任意长度的输入通过散列算法转换成固定长度的输出，建立一种一一对应的关系.这个输出一般称之为散列码或哈希值。
常见hash算法
上面是文字概念如果你还不是太明白的话, 接下来列举一些常见的hash算法:
比如我们的MD5加密,假设你的密码为1234通过MD5加密后就变成了 81dc9bdb52d04dc20036dbd8313ed055这样一串加密。1234和81dc9bdb52d04dc20036dbd8313ed055就建立了一种对应的关系。 1234今后使用MD5加密得到的结果就是固定的81dc9bdb52d04dc20036dbd8313ed055值，得到的这个值我们称为hash值。
再比如我们的ASSIC码表,它也是一种hash算法,我们的一个字符'A'与数字65建立的这一种映射关系。我们的'A' 通过hash算法后,总是能找到固定数字 65，这个65我们就称它是Hash值。
Hash表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
如果我们想要存储多个字母, 存储多个值. 在Java当中可以使用数组来实现。如果我们直接把字母按照数组的角标进行存储的话, 按照如下方式进行存储。
假设此时我们想要获取到b的值 , 我们就须要先遍历,取出每一个元素判断是否等于b.这样效率就比较低。
现在就可以结合上面的上面讲的hash值来进行存储, 每一个字符都会有一个assic码的值, 我们可以获取该字母的assic值进行存储. 放到对象assic码值所在的角标位置,如下图:
通过这种方式存储,我们假设想要获取的内容,就只需要先算出a的assic码值97 在取的时候的时候直接arr[97] 即可直接取出对应位置的字码.无需再遍历数组进行比较。 这样的一个数组,根据关键码值(Key value)直接进行访问的数据结构,我们就称为是hash表。
HashCode
在上面存储字母a的时候,有同学可能会有疑问, 假设我的数组只有16个空间大小存储范围只有0到15. 字母a的assic码是97,直接进行存储的话, 不会是发生异常吗? 的确会是有这样的问题,所以我们在拿到hash值后, 并不是立即进行存储. 在这里我们先对获取的hash码值%16(16就是我们数组的长度),除以16取余数,这样就可以把范围固定在0-15之间,97%16得到结果1. 我们就把字母a存到1角标的位置arr[1]=a , 在取的时候我们使用同样的方式先获取a的assic码再%16 就可以直接获取到对应的值.如下图:
在这里面计算出来的数字1 也就是在数组当中存储的角标,我们就可以称它是a的hashcode码,hashcode码就是在hash表中有对应的位置.
HashCode的存在主要是为了查找的快捷性，HashCode是用来在散列存储结构中确定对象的存储地址的.
Object类中的hashCode方法
Java语言中，JVM每new一个Object,它都会将这个Object丢到一个Hash哈希表中去,这样的话,下次做 Object的比较或者取这个对象的时候,它会依据对象的hashcode再从Hash表中取这个对象。这样做的目的是提高取对象的效率。Object对象有个特殊的方法：hashcode() 此方法作用是到获取对应的hashcode码值。
HashMap内部数据结构:
有了上面的知识储备之后, 我们再来看HashMap的原理实现.hashmap内部的实现原理在JDK1.7与1.8当中有一个大的改变.
JDK1.7中使用的数据结构是:数组+链表
JDK1.8中使用的数据结构是:数组+链表+红黑树
接收下来我们先以JDK1.7当中的实现来去给大家讲,JDK1.7明白之后,1.8是在1.7的基本上加了一个红黑树。
HashMap实现原理
我们先来看一下hashMap的基本使用,如下图:
其中put方法中第一个参数为key(key必须是引用数据类型),第二个参数为value。 这一组key:value 我们称之为Entry,在hashmap中对应的是HashMap当中一个内部类,如下图:
我们每put一组key和value的时候, 就会给我们创建一个Entry对象. 把创建的entry对象放到数组当中去.在hashMap源码中我们可以看到如下的一些属性,其中就定义了数组的初始容量和空的数组。
我们的Entry对象会被放到table这个数组当中,如果下图.
在put一个元素时, 会先判断数组是否为空, 如果数组为空就去创建数组.
第26行位置帮我们初始化数组.从put方法的源码中我们可以看到, 内部的数组是懒加载的. 我们进入到该方法中查看
Entry对象往数组当中进行存放的时候,并不是直接按角标的形式进行存放. 采用hash表的形式进行存储。
在put元素时,entry对的的key必须一个引用数据类型. 引用数据类型在使用的时候可以调用hashcode()这个方法. 返回的是一串int类型的数字. 它这串数字当作是hash值进行存储到数组当中的对象位置. 这串数字比较大, 数组的存储空间大小只有16. 所以要对该数据进行取模 %16把结果限制在0-15之间(注:hashmap当中并不是直接取模,而是采用的位运算达到同样目的,这点后面介绍). 过程如下图:
在存储的过程当中可能会发生hash碰撞
什么是hash碰撞
所谓hash碰撞指的是经过hash算法之后, 计算出的hash码是同一个值,如下图:
在hashmap中为了解决这种情况,引入了链表,也就是我们在上面看Entry内部类声明的时候有一有个next的属性.如果产生了hash冲突,就会以链表头插发的形式来记录对应的数据.
举例: 假设现在角标9的位置被张三实体占用,是第一个放到角标9的位置
下一次再存放李四,假设李四经过hash之后,得到的位置也是9
会采用链表来解决hash冲突
后面如果再产生hash冲突,会遍历链表,查看有没有相同的entry对象,如果有,则进行更新操作,如果没有的话, 把该对象插入到链表头部. 如果没有产生hash冲突,直接存放到对应角标.
以下为put方法源码:
本篇内容就先介绍到这里, 关于hashmap的内容里面还有很多, 本篇内容主要先对hashmap内部的数组+链表有一个全局的认识. 里面还有很多问题我们还没有去分析. 比如:为什么数组的长度一定要为2幂次方, 添加元素时扩容的问题, 在1.7当中扩容转多数据时,多线程情况下为什么可能会产生cpu使用率100%的情况?. jdk1.8中加入了红黑树是什么意思?这些将会在下次给大家一个一个的进行分析.
