您的位置 首页 java

Java HashMap

什么是哈希?

翻译成 “散列” ,就是把任意长度的输入,通过散列算法,变成固定长度的输出,该输出就是 散列值 ,这个映射函数叫做散列函数,存放记录的数组叫做 散列表

假设现在有100个盒子,每个盒子随机放有编号1-100的数字,如果现在我们要找出49号数字,那么就需要一个一个盒子找下去,最坏情况就是在最后一个盒子中才找出来49号,这种查找方式太慢了。

如何快速找到我们想要的数字呢?

可以通过hash算法,在盒子中放入编号n的时候,通过一个方法fn(),计算出对应盒子的index,找的时候再通过对应的编号n,通过方法fn(),同样计算出index,就可以快速的定位到具体的盒子。哈希其实就是通过fn()计算出来的index,哈希方法就是fn()。

什么是完美哈希?

如果存在函数h(x)将 集合 U映射到集合S并且没有碰撞, 我们就可以说h(x)是集合U到集合S的完美 hash函数 完美哈希函数 是静态的,就意味着事前必须知道需要哈希哪些数据。同时生成的算法比较复杂,需要很长的时间来建立 索引 。没有办法实时添加更新。

什么是哈希冲突?

通过上面100个盒子的示例,假设现在有101个数字需要放入100个盒子,多出来的这个数字如果一定要放入某个盒子,那么必定会跟某个数字挤在一个盒子里面,其实这个时候就出现了冲突。

我们知道哈希值是通过哈希函数计算出来的,那么哈希冲突就是两个不同值的东西,通过哈希函数计算出来的哈希值相同,这样他们存在数组中的时候就会发生冲突,这就是哈希冲突。

怎么解决哈希冲突?

1.开放地址法

这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。

就是说当发生冲突时,就去寻找下一个空的地址把数据存入其中,只要 哈希表 足够大,就总能找到这样一个空的地址。

2.拉链法

将所有关键字为同义字的记录存储在一个单链表中

3.再哈希法

在发生冲突的时候再用另外一个哈希函数算出哈希值,直到算出的哈希值不同为止。

4.建立公共溢出区

在创建哈希表的同时,再额外创建一个公共溢出区,专门用来存放发生哈希冲突的元素。查找时,先从哈希表查,查不到再去公共溢出区查。

HashMap JDK1.7

JDK 1.7中 HashMap 的底层数据结构是数组 + 链表 ,使用 Entry 类存储 Key 和 Value。结构如下:

如果出现哈希冲突那么,结构就会变成:

那么当哈希冲突的次数比较多的时候,这个时候链表将会越来越长,查找的性能就会降低。

HashMap JDK1.8

JDK 1.8 中 HashMap 的底层数据结构是数组 + 链表 / 红黑树 ,用 Node 类存储 Key 和 Value.这里的Node其实跟Entry结构基本一致。

当链表的长度大于 8 的时候就会转换为红黑树,不过在转换之前,会先去查看 table 数组的长度是否大于 64,如果数组的长度小于 64,那么 HashMap 会优先选择对数组进行扩容 ,而不是把链表转换成红黑树,如下图:

HashMap数组扩容

通过之前可以知道,数组容量是有限的,如果数据多次插入并到达一定的数量就会进行数组扩容,也就是 resize 方法。什么时候会进行 resize 呢?与两个因素有关:

1) Capacity :HashMap 当前最大容量/长度

2) LoadFactor :负载因子,默认值0.75f

如果当前存入的数据数量大于 Capacity * LoadFactor 的时候,就会进行数组扩容 resize 。就比如当前的 HashMap 的最大容量大小为 100,当你存进第 76 个的时候,判断发现需要进行 resize了,那就进行扩容。当然, Hash Map 的扩容不是简单的扩大点容量这么简单的。

扩容 resize 分为两步

1)扩容:创建一个新的 Entry/Node 空数组,长度是原数组的 2 倍

2)ReHash:遍历原 Entry/Node 数组,把所有的 Entry/Node 节点重新 Hash 到新数组

为什么要 ReHash 呢?直接复制到新数组不行吗?

显然是不行的,因为数组的长度改变以后,Hash 的规则也随之改变。index 的计算公式是这样的:

  • index = HashCode (key) & (Length – 1)

比如说数组原来的长度(Length)是 4,Hash 出来的值是 2 ,然后数组长度翻倍了变成 16,显然 Hash 出来的值也就会变了。画个图解释下:

HashMap 的默认初始数组长度是多少?为什么是这么多?

默认数组长度是 16,其实只要是 2 的次幂都行,至于为啥是 16 呢,我觉得应该是个经验值问题, Java 作者是觉得 16 这个长度最为常用。

那为什么数组长度得是 2 的次幂呢?

首先,一般来说,我们常用的 Hash 函数 是这样的:index = HashCode(key) % Length,但是因为 位运算 的效率比较高嘛,所以 HashMap 就相应的改成了这样:index = HashCode(key) & (Length – 1)。

文章来源:智云一二三科技

文章标题:Java HashMap

文章地址:https://www.zhihuclub.com/185325.shtml

关于作者: 智云科技

热门文章

网站地图