深入理解HashMap

HashMap是Java中Map的一个实现类。是一个双列结构,插入和查询的效率都很高

HashMap介绍

HashMap是Java中Map的一个实现类。是一个双列结构,插入和查询的效率都很高;
允许null键和null值。
HashMap的键唯一,值可以重复,元素存储无序
HashMap是线程不安全的。
HashMap是一个散列表。
JDK1.8对HashMap使用了红黑树进行优化。

HashMap的双列结构

HashMap采用数组+链表的双列结构
hashMap的双列结构

HashMap中的成员变量

在HashMap中有6个重要的成员变量:
transient Entry[] table
transient Set<Entry<K,V>> entrySet
transient int size
transient int modCount
transient int threshold
transient float loadFactor

transient Entry[] table

table对应的是双列结构的数组,默认长度为16(即图“HashMap简单结构示意图”中的竖向数组。 在HashMap类中,table的实际类型是Node[] table,Node实现了Entry接口:
Node的定义

transient Set<Entry<K,V>> entrySet

entrySet是一个Entry类型的集合,存放Map中所有的Entry
在遍历HashMap时会用到entrySet

transient int size

键值对的个数

transient int modCount

HashMap扩容的次数

tranHashMap的阈值

threshold=数组容量*loadFactor

当size>threshold时,需要对HashMap进行扩容。
ient int threshold

### transient float loadFactor
加载因子

## HashMap中的常量
HashMap中存在几个常量
HashMap中的常量

# 哈希冲突
HashMap调用put方法存储元素的时候,会根据key的hash值计算它的索引,比如索引为n,则将元素存储到table [n]这个位置。

HashMap在计算索引时尽量保证元素的离散,但也会存在索引一致的情况,这种问题称为Hash冲突。

HashMap中的Node类是解决冲突的关键,当遇到冲突元素时,使用单链表存储,即通过Node.next扩展对应的table[n]。

同一索引下的元素构成单链表结构,这是HashMap双列结构的链表结构。

# HashMap的实现
## put()方法的实现
put()源码实现如下:
put
put()方法调用putVal()方法进行具体实现,putVal()的逻辑如下:
1. 计算容量:如果size>theshold,对数组扩容2倍
2. 计算hash值:根据key的hash值和数组长度计算索引
Hash函数
3. 存储数据,假设计算的hash值为i,数组为tab[]
1. 如果tab[i]==null即当前索引处没有元素,直接创建一个新的Node
newNode
2. 如果tab[i]!=null,再调用equals()方法依次判断该索引下元素的key是否和当前元素的key相等,如果相等,覆盖,如果不相等,继续判断下一个。
3. 如果以上两种都不成立,即tab[i]!=null且key值无重复,发生冲突.JDK8后,采用红黑树来解决这种冲突问题:红黑树在进行插入和删除操作时通过特定算法保持二叉查找树的平衡,以获得较高的查找性能。HashMap判断当前数组上的元素tab[i]是否是红黑树,如果是,调用红黑树的putTreeVal的put()方法,将新元素以红黑树结构存储到数组中。
4. 如果以上都不成立,即发生冲突但没有转成红黑树结构,只需要将新元素插入链表的尾部。

## get()方法的实现
get()方法的实现如下:
get
get()方法的核心是getNode()方法,参数为hash值和key值。
get()方法的实现逻辑如下:
1. 通过hash值和数组长度找到数组索引
2. 获得当前数组(链表)的首元素first,判断key值是否相等,如果相等,直接返回key的value
3. 如果不是first,判断是否为红黑树结构,如果是,调用红黑树的getTreeNode()方法查询;
4. 如果不是红黑树结构,从first开始遍历链表,直到找到key值对应的元素,没有则返回null.

## 扩容与二次哈希
调用put()方法时,会使用resize()方法对哈希表进行扩容,扩容之后原来在同一链表中的元素可能会改变位置或者不变。
同一链表的元素在扩容后,它们的索引只有两种可能:

1. 保持原索引
2. 数组原长度+原索引

Node类的实现

Node类是存储键值对的基本单位,在其内部实现了getKey(),getValue()方法,所以在遍历Map可以用Map.entrySet().
Node类

hash函数与索引计算

HashMap中的hash()函数实现如下:
hash函数
对于HashMap来说,要确定元素所在的索引值,是通过hash(key)和数组长度取模实现的,公式如下:

hash(key)&(length-1)

下面以二进制为例说明计算的过程:
假设数组原长度16,扩容后为32
16-1:0000 1111
32-1:0001 1111
假设hash(key)的值为0000 1010(从右向左第log₂length位为0):
前后索引是相同的,都是1010
假设hash(key)的值为0001 1010(从右向左第log₂length位为1):
前索引为0 1010,后索引为1 1010,索引增加了length.
这就是扩容时同一链表中元素索引变化的两种情况。

总结

  1. HashMap底层采用数组+链表的双列结构,数组默认长度16
  2. HashMap是一个散列表,根据hash(key)和数组长度查找索引,发生冲突采用拉链式存储元素,即单向链表。
  3. Java7中,如果hash冲突,导致链表过长影响遍历效率,因此在Java8中添加了红黑树结构,当链表长度超过8时,将其转为红黑树结构,如果长度小于6,重新转为普通链表
  4. 再哈希时,同一链表的元素的索引只可能是不变或者增加原长度
  5. HashMap扩容时的所有元素都要重新计算索引,这是很耗时的,所以使用时要注意这个问题。
smartpig wechat
扫一扫关注微信公众号
0%