Jack Frost

深入Java基础(四)–哈希表(1)HashMap应用及源码详解

继续深入Java基础系列。今天是研究下哈希表,毕竟我们很多应用层的查找存储框架都是哈希作为它的根数据结构进行封装的嘛。

本系列:

(1)深入Java基础(一)——基本数据类型及其包装类

(2)深入Java基础(二)——字符串家族

(3)深入Java基础(三)–集合(1)集合父类以及父接口源码及理解

(4)深入Java基础(三)–集合(2)ArrayList和其继承树源码解析以及其注意事项


文章结构:(1)哈希概述及HashMap应用;(2)HashMap源码分析;(3)再次总结关键点


一、哈希概述及HashMap应用:

概述:详细介绍

根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。

对比:数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。哈希则是一种寻址容易,插入删除也容易的数据结构。

实际应用:

1.Hash主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说,Hash就是找到一种数据内容和数据存放地址之间的映射关系
2.查找:哈希表,又称为散列,是一种更加快捷的查找技术。我们之前的查找,都是这样一种思路:集合中拿出来一个元素,看看是否与我们要找的相等,如果不等,缩小范围,继续查找。而哈希表是完全另外一种思路:当我知道key值以后,我就可以直接计算出这个元素在集合中的位置,根本不需要一次又一次的查找!

HashMap概述:

Hash表 是一种逻辑数据结构,HashMap是Java中的一种数据类型(结构类型),它通过代码实现了Hash表 这种数据结构,并在此结构上定义了一系列操作。

HashMap关键点罗列:

1.基于数组来实现哈希表的,数组就好比内存储空间,数组的index就好比内存的地址;

2.每个记录就是一个Entry 《K, V>对象,数组中存储的就是这些对象;

3.HashMap的哈希函数 = 计算出hashCode + 计算出数组的index;

4.HashMap解决冲突:使用链地址法,每个Entry对象都有一个引用next来指向链表的下一个Entry;(也就是链地址法)

但是!JDK1.8升级了!!

JDK1.8之前:使用单向链表来存储相同索引值的元素。在最坏的情况下,这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。

在JDK1.8:为了解决在频繁冲突时hashmap性能降低的问题,使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。

在Java 8中使用常量TREEIFY_THRESHOLD来控制是否切换到平衡树来存储。目前,这个常量值是8,这意味着当有超过8个元素的索引一样时,HashMap会使用树来存储它们。
这一动态的特性使得HashMap一开始使用链表,并在冲突的元素数量超过指定值时用平衡二叉树替换链表。不过这一特性在所有基于hash table的类中并没有,例如Hashtable和WeakHashMap。目前,只有ConcurrentHashMap,LinkedHashMap和HashMap会在频繁冲突的情况下使用平衡树。

5.装填因子:默认为0.75;

(加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。)

6.继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。

这里写图片描述

7.不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。

8.影响性能的因素:“初始容量” 和 “加载因子”

容量 是哈希表中桶的数量,初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

HashMap基本操作:

二、HashTable重要的部分源码分析:(基于jdk1.8)

jdk1.8的扩容

使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

这里写图片描述

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

这里写图片描述

在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”.

既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。

对比jdk1.7:插入和扩容方法

说明:jdk1.7查询是的计算哈希,遍历单链表。因为它们怎么改结构,本质还是个哈希。而jdk1.8在冲突小于8的时候是像1.7的查询方式,但大于8的时候,就会改成红黑树,使用二叉查找树的结构性查询方式了,并且jdk1.8的插入涉及的存储结构的转换,从链地址法冲突处理到8位后就改成红黑树存储。

来看下1.7的插入和扩容机制源码,简单得不行。

找了一张好图,说明JDK1.7的。原文

这里写图片描述

假设原来大小只是2,那么扩容根据2的次幂,就是到4了。然后重新计算分配hash,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。所有的Node重新rehash的过程。

三、再次总结关键点:

(1)实现了Map、Cloneable、java.io.Serializable接口。意味着支持全部map操作,支持被克隆,支持序列化,能通过序列化去传输。

(2)HashMap的函数则是非同步的,它不是线程安全的。

若要在多线程中使用HashMap,需要我们额外的进行同步处理。 对HashMap的同步处理可以使用Collections类提供的synchronizedMap静态方法,或者直接使用JDK 5.0之后提供的java.util.concurrent包里的ConcurrentHashMap类。

(3)HashMap的key、value都可以为null。

HashMap的key、value都可以为null。 当HashMap的key为null时,HashMap会将其固定的插入table[0]位置(即HashMap散列表的第一个位置);而且table[0]处只会容纳一个key为null的值,当有多个key为null的值插入的时候,table[0]会保留最后插入的value。

(4)HashMap只支持Iterator(迭代器)遍历。是“从前向后”的遍历数组;再对数组具体某一项对应的链表,从表头开始进行遍历。

方式是:1.通过entrySet()获取“Map.Entry集合”。2. 通过iterator()获取“Map.Entry集合”的迭代器,再进行遍历。

图1

这里写图片描述

图2

这里写图片描述

(5)HashMap的工作原理:

通过hash的方法,通过put和get存储和获取对象。存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket桶位置,然后根据TREEIFY_THRESHOLD判断桶装载的类型,红黑树还是链表,再进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,然后根据TREEIFY_THRESHOLD判断桶装载的类型,并进一步调用equals()方法确定键值对。

在Java 8中,如果一个bucket桶中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

(6)equals()和hashCode()的都有什么作用?

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点

因为hashcode相同,所以它们的bucket位置相同,‘碰撞冲突’会发生。因为HashMap使用链表或红黑树存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表或红黑树中。

找到bucket桶位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。因此,设计HashMap的key类型时,如果使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。

(7)HashMap添加元素时,是使用自定义的哈希算法。HashMap不支持contains(Object value)方法,没有重写toString()方法。

(8)HashMap的大小超过了负载因子(load factor)定义的容量,会怎样?

超过了负载因子(默认0.75),则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,jdk1.7会重新计算哈希值,但是jdk1.8很少重新计算,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。

(9)重新调整HashMap大小出现的线程问题:

当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。因此在并发环境下,我们使用CurrentHashMap来替代HashMap

(10)为什么String, Interger这样的wrapper类适合作为键?

因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能

参考:此博主此文章

(11)使用的取舍:

1. 若在单线程中,我们往往会选择HashMap;而在多线程中,则会选择Hashtable。

2.若不能插入null元素,则选择Hashtable;否则,可以选择HashMap。

3.在多线程中,我们可以自己对HashMap进行同步,也可以选择ConcurrentHashMap。当HashMap和Hashtable都不能满足自己的需求时,还可以考虑新定义一个类,继承或重新实现散列表;当然,一般情况下是不需要的了。


好了,深入Java基础(四)–哈希表(1)HashMap应用及源码详解讲完了。本博客系列是这个系列的第五篇,阅读这些源码收获很大,当然过程也是很有点苦逼的,比如这篇我之前不小心没保存,前前后后4天才写完,当然也不后悔,这是积累的必经一步,我会继续出这个系列文章,分享经验给大家。欢迎在下面指出错误,共同学习!!你的点赞是对我最好的支持!!

更多内容,可以访问JackFrost的博客

码字很辛苦,转载请注明来自JackFrost《深入Java基础(四)–哈希表(1)HashMap应用及源码详解》

Leave a Reply

Your email address will not be published. Required fields are marked *