HashMap原理的深入了解 - 极悦
首页 课程 师资 教程 报名

HashMap原理的深入了解

  • 2021-07-12 16:49:01
  • 887次 极悦

1.hashing(哈希法)的概念

散列法(Hashing)是一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法,称为散列法,也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快,这种方法一般用来在数据库中建立索引并进行搜索,同时还用在各种解密算法中。

对比:Hashtable、HashMap、TreeMap

Hashtable是早期Java类库提供的一个哈希表实现,本身是同步的,不支持null键和值,由于同步导致的性能开销,所以已经很少被推荐使用。

HashMap与HashTable主要区别在于HashMap不是同步的,支持null键和值等。通常情况下,HashMap进行put或者get操作,可以达到常数时间的性能,所以它是绝大部分利用键值对存取场景的首选。

TreeMap则是基于红黑树的一种提供顺序访问的Map,和HashMap不同,它的get、put、remove之类操作都是O(log(n))的时间复杂度,具体顺序可以由指定的Comparator来决定,或者根据键的自然顺序来判断。

2.HashMap概念和底层结构

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。HashMap储存的是键值对,HashMap很快。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

HashMap内部结构:可以看作是数组和链表结合组成的复合结构,数组被分为一个个桶(bucket),每个桶存储有一个或多个Entry对象,每个Entry对象包含三部分key(键)、value(值),next(指向下一个Entry),通过哈希值决定了Entry对象在这个数组的寻址;哈希值相同的Entry对象(键值对),则以链表形式存储。如果链表大小超过树形转换的阈值(TREEIFY_THRESHOLD=8),链表就会被改造为树形结构。

hashMap的结构示意图如下:

HashMap原理的深入了解

查询时间复杂度:HashMap的本质可以认为是一个数组,数组的每个索引被称为桶,每个桶里放着一个单链表,一个节点连着一个节点。很明显通过下标来检索数组元素时间复杂度为O(1),而且遍历链表的时间复杂度是O(n),所以在链表长度尽可能短的前提下,HashMap的查询复杂度接近O(1)

数组:存储区间连续,占用内存严重,寻址容易,插入删除困难;

链表:存储区间离散,占用内存比较宽松,寻址困难,插入删除容易;

Hashmap综合应用了这两种数据结构,实现了寻址容易,插入删除也容易。

3.HashMap的工作原理

HashMap的工作原理:HashMap是基于散列法(又称哈希法)的原理,使用put(key,value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket(桶)位置来储存Entry对象。HashMap是在bucket中储存键对象和值对象,作为Map.Entry。并不是仅仅只在bucket中存储值。

HashMap具体的存取过程:

put存值的方法,过程如下:

HashMap原理的深入了解

  • 判断键值对数组table<i>是否为空或为null,否则执行resize()进行扩容;
  • 根据键值key计算hash值得到插入的数组索引i,如果table<i>==null,直接新建节点添加,转向⑥,如果table<i>不为空,转向③;
  • 判断table<i>的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;
  • 判断table<i>是否为treeNode,即table<i>是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;
  • 遍历table<i>,判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
  • 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

get取值的方法,过程如下:

  • 指定key通过hash函数得到key的hash值int hash=key.hashCode();
  • 调用内部方法getNode(),得到桶号(一般为hash值对桶数求模)int index=hash%Entry[].length;jdk1.6版本后使用位运算替代模运算,int index=hash&(Entry[].length-1);
  • 比较桶的内部元素是否与key相等,若都不相等,则没有找到。相等,则取出相等记录的value。
  • 如果得到key所在的桶的头结点恰好是红黑树节点,就调用红黑树节点的getTreeNode()方法,否则就遍历链表节点。getTreeNode方法使通过调用树形节点的find()方法进行查找。由于之前添加时已经保证这个树是有序的,因此查找时基本就是折半查找,效率很高。
  • 如果对比节点的哈希值和要查找的哈希值相等,就会判断key是否相等,相等就直接返回;不相等就从子树中递归查找。

4.如何重新调整HashMap的大小

“如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?”

HashMap的扩容阈值(threshold=capacity*loadFactor容量范围是16~2的30次方),就是通过它和size进行比较来判断是否需要扩容。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,将会创建原来HashMap大小的两倍的bucket数组(jdk1.6,但不超过最大容量),来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

5.解决hash冲突的常见方法

针对哈希表直接定址可能存在hash冲突,举一个简单的例子,例如:

  • 第一个键值对A进来,通过计算其key的hash得到的index=0。记做:Entry[0]=A。
  • 第二个键值对B,通过计算其index也等于0,HashMap会将B.next=A,Entry[0]=B,
  • 第三个键值对C,通过计算其index也等于0,那么C.next=B,Entry[0]=C;

这样我们发现index=0的地方事实上存取了A,B,C三个键值对,它们通过next这个属性链接在一起。对于不同的元素,可能计算出了相同的函数值,这样就产生了hash冲突,那要解决冲突,又有哪些方法呢?具体如下:

  • 链地址法:将哈希表的每个单元作为链表的头结点,所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
  • 开放定址法:即发生冲突时,去寻找下一个空的哈希地址。只要哈希表足够大,总能找到空的哈希地址。
  • 再哈希法:即发生冲突时,由其他的函数再计算一次哈希值。
  • 建立公共溢出区:将哈希表分为基本表和溢出表,发生冲突时,将冲突的元素放入溢出表。

6.HashMap采用哪种方法解决冲突的呢?

HashMap就是使用链地址法来解决冲突的(jdk8中采用平衡树来替代链表存储冲突的元素,但hash()方法原理相同)。当两个对象的hashcode相同时,它们的bucket位置相同,碰撞就会发生。此时,可以将put进来的K-V对象插入到链表的尾部。对于储存在同一个bucket位置的链表对象,可通过键对象的equals()方法用来找到键值对。

以上就是极悦小编介绍的"HashMap原理的深入了解",希望对大家有帮助,想了解更多可查看Java基础教程,如有疑问,请在线咨询,有专业老师随时为您服务。

选你想看

你适合学Java吗?4大专业测评方法

代码逻辑 吸收能力 技术学习能力 综合素质

先测评确定适合在学习

在线申请免费测试名额
价值1998元实验班免费学
姓名
手机
提交