本帖最后由 biu波儿了罢 于 2020-3-18 14:55 编辑
HashMap实现原理和扩容机制 1.实现原理: HashMap的底层实现是一个哈希表即数组+链表;
HashMap初始容量大小16,扩容因子为0.75,扩容倍数为2;
HashMap本质是一个一定长度的数组,数组中存放的是链表。 当向HashMap中put(key,value)时,会首先通过hash算法计算出存放到数组中的位置,比如位置索引为i,将其放入到Entry中,如果这个位置上面已经有元素了,那么就将新加入的元素放在链表的头上,最先加入的元素在链表尾。比如,第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起,也就是说数组中存储的是最后插入的元素。 HashMap的get(key)方法是:首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到,如果每个位置上的链表只有一个元素,那么hashmap的get效率将是最高的。所以我们需要让这个hash算法尽可能的将元素平均的放在数组中每个位置上。
2.扩容机制
当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容。
[Java] 纯文本查看 复制代码 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // HashMap初始容量大小(16)
static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap最大容量
transient int size; // The number of key-value mappings contained in this map
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子
HashMap的容量size乘以负载因子[默认0.75] = threshold; // threshold即为开始扩容的临界值
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // HashMap的基本构成Entry数组
当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置。
0.75这个值成为负载因子,那么为什么负载因子为0.75呢?这是通过大量实验统计得出来的,如果过小,比如0.5,那么当存放的元素超过一半时就进行扩容,会造成资源的浪费;如果过大,比如1,那么当元素满的时候才进行扩容,会使get,put操作的碰撞几率增加。
HashMap中扩容是调用resize()方法,方法源码:
[Java] 纯文本查看 复制代码 void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果当前的数组长度已经达到最大值,则不在进行调整
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根据传入参数的长度定义新的数组
Entry[] newTable = new Entry[newCapacity];
//按照新的规则,将旧数组中的元素转移到新数组中
transfer(newTable);
table = newTable;
//更新临界值
threshold = (int)(newCapacity * loadFactor);
}
//旧数组中元素往新数组中迁移
void transfer(Entry[] newTable) {
//旧数组
Entry[] src = table;
//新数组长度
int newCapacity = newTable.length;
//遍历旧数组
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);//放在新数组中的index位置
e.next = newTable;//实现链表结构,新加入的放在链头,之前的的数据放在链尾
newTable = e;
e = next;
} while (e != null);
}
}
}
可以看到HashMap不是无限扩容的,当达到了实现预定的MAXIMUM_CAPACITY,就不再进行扩容。
|