影响HashMap性能的两个重要参数以及HashMap的几个重要成员变量
1.初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
初始容量用来规定哈希表数组的长度,默认值为16,因为16是2的整数次幂的原因,再小数据量下的情况下,能减少哈希冲突,提高性能。在大存储容量数据的时候,也尽量将数组长度定义为2的幂次方,这样能更好的与索引计算公式i=(n-1)&hash配合使用,从而提升性能。
2.加载因子
final float loadFactor;
用来表示HashMap集合中元素的填满程度,默认为0.75f。越大则表示允许填满的元素就多,集合的空间利用率就越高,但是冲突的机会增加。反之,越小则冲突的机会就会越少,但是空间很多就浪费。
所以在设置初始容量时,应优先考虑到初始容量及其他加载因子,预估设置初始容量,最大程度的减少rehash重建内部数据结构的次数,极大的减少了扩容操作。
- 底层数组
transient Node<K,V>[] table;
保存KV键值对的数组,每个KV键值对都被封装成一个Node对象。
- 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;//1073741824
HashMap的最大容量值,扩容时如果超出,则不扩容。
- 扩容阈值
int threshold
用于判断数组是否需要扩,扩容阈值threshold=数组容量×加载因子。
- KV键值对数量
int size
HashMap底层存储机制概述
jdk1.8以前HashMap内部数据结构使用数组+链表进行存储。(了解即可)
jdk1.8以后HashMap内部数据结构使用数组+链表+红黑树进行存储。
//数组
transient Node<K,V>[] table;
//链表节点类
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//哈希值
final K key;//键
V value;//值
Node<K,V> next;//下一个元素
}
数组类型为Node[],每个Node都保存了某个KV键值对元素的key、value、hash、next等值。由于next的存在,所以每个Node对象都是一个单向链表中的组成节点。
当新添加一个KV键值对元素时,通过该元素的key的hash值,计算该元素在数组中应该保存的下标位置。如果该下标位置如果已经存在其它Node对象,则采用链地址法处理,即将新添加的KV键值对元素将以链表形式存储。将新元素封装成一个新的Node对象,插入到该下标位置的链表尾部(尾插法)。当链表的长度超过8并且数组长度大于64时,为了避免查找搜索性能下降,该链表会转换一个红黑树。
(附带大佬做的好图一张,仅供参考理解)
HashMap的初始化与扩容方式
1.初始化
HashMap的构造方法进行了重载,具有无参、有参等多种构造方式。
无参构造:默认定义加载因子为0.75。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
static final float DEFAULT_LOAD_FACTOR = 0.75f;
指定容量的有参构造:传入所需的最小容量值,依旧使用默认加载因子。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
指定容量和加载因子的有参构造方法:指定容量值与加载因子。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
2.扩容方式
HashMap底层采用数组+链表+红黑树,扩容过程中需要按照数组容量和加载因子来进行判断。文章来源:https://www.toymoban.com/news/detail-838962.html
HashMap的扩容方法是resize()方法,发生下列几种情况时,会发生扩容:文章来源地址https://www.toymoban.com/news/detail-838962.html
// 添加新元素
final V putVal(int hash, K key, V value){
//...
// 判断当前集合中的元素数量,是否超过阈值threshol
if (++size > threshold)
resize();
}
//...
- 当我们第一次添加KV键值对时,如果数组此时为空,则会默认扩容为16。
- 加入元素时,如果链表长度大于阈值(默认为8)并且数组长度小于6,就会产生数组扩容。
- 添加元素后,当HashMap中的元素个数超过【数组大小×加载因子】时,原数组扩容2倍。例如:加载因子的默认值为0.75,数组容量默认为16,当HashMap中的元素个数超过16×0.75=12时,数组容量扩容16×2=32。
- HashMap加入新元素时,如果链表长度大于8时,会尝试将当前链表转换为红黑树。在转换红黑树之前,会判断数组长度,如果小于64,会产生数组扩容。如果数组长度大于64,才会将链表转换为红黑树。
final void treeifyBin(Node<K,V>[] tab, int hash) {
//...
//如果数组长度n小于64或者数组长度为空,
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();//数组扩容
//
else if ((e = tab[index = (n - 1) & hash]) != null) {
//遍历链表节点,转换为红黑树
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
总结
- HashMap的数据结构采用数组+链表+红黑树。
- HashMap的按照key的hash值计算数组中的存储位置下标,计算方式:(n-1)&hash。
- 如果在该下标位置已经存在元素,代表产生哈希冲突,则采用链地址法处理,以单向链表的形式,将新元素存储在链表的尾部(尾插法)。
- 当链表中Node节点的数量大于8并且数组的长度大于64时,链表会转换成一个红黑树,有利于查找搜索。
- HashMap的默认容量为16,加载因子为0.75f,当集合元素个数超过扩容阈值【容量×加载因子】时,HashMap会将底层数组容量按照2倍进行扩容。
到了这里,关于HashMap的数据结构(超详细版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!