Java中的hashCode和equals
- hashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,hashCode是用来在散列存储结构中确定对象的存储地址的
- equals和
==
用于比较引用和比较基本数据类型时具有不同的功能:比较基本数据类型,如果两个值相同,则结果为true而在比较引用时,如果引用指向内存中的同一对象,结果为true;
HashMap 简介
Map 是 Key-Value
对映射的抽象接口,该映射不包括重复的键,即一个键对应一个值。HashMap
是 Java Collection Framework
的重要成员,也是Map族(如下图所示)中我们最为常用的一种。简单地说,HashMap
是基于哈希表的 Map 接口的实现,以 Key-Value
的形式存在,即存储的对象是 Entry
(同时包含了 Key 和 Value) 。在HashMap
中,其会根据hash算法来计算key-value
的存储位置并进行快速存取。
1 | HashMap<String, Integer> map = new HashMap<String, Integer>(); |
HashMap
是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作,并允许使用 null
值和 null
键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap
的实例有两个参数影响其性能:初始容量
和 加载因子
。容量
是哈希表中桶的数量,初始容量
只是哈希表在创建时的容量。加载因子
是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash
操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。
HashMap 的数据结构
在 Java 编程语言中,最基本的结构就是两种,一个是数组,另外一个是指针(引用),HashMap 就是通过这两个数据结构进行实现。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。 HashMap 底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个 HashMap 的时候,就会初始化一个数组。
HashMap 源码
HashMap构造函数
1 | public HashMap(int initialCapacity, float loadFactor) { |
HashMap共有4个构造函数
1 | // 默认构造函数。 |
它包括几个重要的成员变量:table, size, threshold, loadFactor
。
-
table
是一个Entry[]数组类型,而Entry实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。 - size是HashMap的大小,它是HashMap保存的键值对的数量。
- threshold是HashMap的阈值,用于判断是否需要调整HashMap的容量。threshold的值=”容量*加载因子”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。
- loadFactor就是加载因子。
Entry 是一个 static class
1 | static class Entry<K,V> implements Map.Entry<K,V> { |
Entry 就是数组中的元素,每个 Entry 其实就是一个 key-value 对,它持有一个指向下一个元素的引用,这就构成了链表。 PUT储存源码
1 | public V put(K key, V value) { |
put函数大致的思路为:
- 对key的
hashCode()
做hash,然后再计算这个元素在数组中的位置(即下标); - 如果没碰撞直接放到数组对应的位置上;
- 如果碰撞了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。
- 如果碰撞导致链表过长(大于等于
TREEIFY_THRESHOLD
),就把链表转换成红黑树; - 如果节点已经存在就替换
old value
(保证key的唯一性)。 - 如果储存的元素数量满了(超过
load factor*current capacity
),就要resize。
当程序试图将一个key-value
对放入HashMap
中时,程序首先根据该 key的 hashCode()
返回值决定该 Entry
的存储位置:如果两个 Entry
的 key
的 hashCode()
返回值相同,那它们的存储位置相同。如果这两个 Entry
的 key 通过 equals
比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry的 value,但key不会覆盖。如果这两个 Entry
的 key 通过 equals
比较返回 false,新添加的 Entry
将与集合中原有 Entry
形成 Entry 链
,而且新添加的 Entry
位于 Entry 链
的头部。 GET取出源码
1 | public V get(Object key) { |
首先计算 key 的 hashCode,找到数组中对应位置的某一元素,如果是第一个然后通过 key 的 equals 方法在对应位置的链表或者树中查找需要的元素。 简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据 hash 算法来决定其在数组中的存储位置,再根据 equals 方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry 时,也会根据 hash 算法找到其在数组中的存储位置,再根据 equals 方法从该位置上的链表中取出该Entry。
hash函数的实现
在get和put的过程中,计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标,如下图所示: 在对hashCode()计算hash时具体实现是这样的:
1 | static final int hash(Object key) { |
可以看到这个函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或。
RESIZE的实现
当 HashMap 中的元素越来越多的时候,hash 冲突的几率也就越来越高,因为数组的长度是固定的。当 HashMap 中的元素个数超过数组大小 *loadFactor
时,就会进行数组扩容,loadFactor
的默认值为 0.75,在resize的过程,简单的说就是把数组扩充为2倍,之后重新计算元素位置,把节点再放到新的数组中。resize的注释是这样描述的:当超过限制的时候会resize,然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。
例如我们从16扩展为32时,具体的变化如下所示: 能表示的范围*2,多了一字节的范围。因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色)。
因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。
一些问题
- 什么时候会使用HashMap?他有什么特点? 是基于Map接口的实现,存储键值对时,它可以接收null的键值,是非同步的,HashMap存储着Entry(hash, key, value, next)对象。
- 你知道HashMap的工作原理吗? 通过hash的方法,通过put和get存储和获取对象。存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。
- 你知道get和put的原理吗?equals()和hashCode()的都有什么作用? 通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点
- 你知道hash的实现吗?为什么要这样实现? 在Java 1.8的实现中,是通过hashCode()的高16位异或低16位实现的:
(h = k.hashCode()) ^ (h >>> 16)
,主要是从速度、功效、质量来考虑的,这么做可以在bucket的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中,同时不会有太大的开销。 - 如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办? 如果超过了负载因子(默认0.75),则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法。
Referer
https://wiki.jikexueyuan.com/project/java-collection/hashmap.html https://www.w3schools.com/java/java_hashmap.asp https://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/ https://www.cnblogs.com/skywang12345/p/3310835.html https://www.cnblogs.com/yuanblog/p/4441017.html