文档章节

HashMap 扩容机制

天王盖地虎626
 天王盖地虎626
发布于 06/19 10:02
字数 1037
阅读 9
收藏 0

HashMap:

 
复制代码
public HashMap(int initialCapacity, float loadFactor) {     
//初始容量不能<0  
if (initialCapacity < 0)         
throw new IllegalArgumentException("Illegal initial capacity: "                 + initialCapacity);     
//初始容量不能 > 最大容量值,HashMap的最大容量值为2^30     
if (initialCapacity > MAXIMUM_CAPACITY)         
initialCapacity = MAXIMUM_CAPACITY;     
//负载因子不能 < 0     
if (loadFactor <= 0 || Float.isNaN(loadFactor))         
throw new IllegalArgumentException("Illegal load factor: "                 + loadFactor);     
// 计算出大于 initialCapacity 的最小的 2 的 n 次方值。    
 int capacity = 1;     
while (capacity < initialCapacity)        
 capacity <<= 1;    
 this.loadFactor = loadFactor;     
//设置HashMap的容量极限,当HashMap的容量达到该极限时就会进行扩容操作    
 threshold = (int) (capacity * loadFactor);     
//初始化table数组    
 table = new Entry[capacity];     init(); 
}
复制代码
 

在这里提到了两个参数:初始容量,加载因子。

这两个参数是影响HashMap性能的重要参数,其中容量表示哈希表中桶的数量,初始容量是创建哈希表时的容量,

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。

对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;

如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。系统默认负载因子为0.75,一般情况下我们是无需修改的。

加载因子:

 loadFactor

 

扩容:

 
复制代码
void addEntry(int hash, K key, V value, int bucketIndex) {    
 Entry<K,V> e = table[bucketIndex];        
 table[bucketIndex] = new Entry<K,V>(hash, key, value, e);         
if (size++ >= threshold) // 这里是关键,一旦大于等于threshold的数值             
resize(2 * table.length); // 将会引起容量2倍的扩大     
}
复制代码
 
复制代码
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); // 重新计算threshold的值    
 }
复制代码
复制代码
void transfer(Entry[] newTable) {          
// 保留原数组的引用到src中,         
 Entry[] src = table;          
// 新容量使新数组的长度          
int newCapacity = newTable.length;       
// 遍历原数组          
for (int j = 0; j < src.length; j++) {              
// 获取元素e              
Entry<K,V> e = src[j];              
if (e != null) {                 
 // 将原数组中的元素置为null                  
src[j] = null;                  
// 遍历原数组中j位置指向的链表                  
do {                      
Entry<K,V> next = e.next;                      
// 根据新的容量计算e在新数组中的位置                      
int i = indexFor(e.hash, newCapacity);                      
// 将e插入到newTable[i]指向的链表的头部                      
e.next = newTable[i];                      
newTable[i] = e;                      
e = next;                  
}
 while (e != null);              
}          
}      
}
复制代码

通过上面的transfer方法可以看出,

e.next=newTable[i];

newTable[i]=e;

链表存储倒过来了,最先出来的会将其next指向null,后面的就指向前一个,当然数据只有原来的一部分。

===================================================================

随着HashMap中元素的数量越来越多,发生碰撞的概率就越来越大,所产生的链表长度就会越来越长,这样势必会影响HashMap的速度,

为了保证HashMap的效率,系统必须要在某个临界点进行扩容处理。

该临界点在当HashMap中元素的数量等于table数组长度*加载因子。

但是扩容是一个非常耗时的过程,因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。

所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

问题:

当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。

在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。

如果条件竞争发生了,那么就死循环了。

本文转载自:https://www.cnblogs.com/hqlong/p/6802487.html

天王盖地虎626

天王盖地虎626

粉丝 32
博文 527
码字总数 20708
作品 0
南京
私信 提问
添加200个元素到ArrayList后内部的数组大小是多少?

面试时,面试官问我添加200个元素到ArrayList后内部的数组大小是多少? 我思考了1分钟尴尬的回答不知道。 ArrayList的内部是一个数组,随着添加元素的增多,内部的数组会动态的扩容,扩容的机...

ijava
2017/12/05
0
0
HashMap中傻傻分不清楚的那些概念

很多人在通过阅读源码的方式学习Java,这是个很好的方式。而JDK的源码自然是首选。在JDK的众多类中,我觉得HashMap及其相关的类是设计的比较好的。很多人读过HashMap的代码,不知道你们有没有...

2018/05/20
0
0
JDK 1.7 HashMap原理及源码解析

简介 类定义 3. 具体使用 3.1 主要使用API(方法、函数) 3.2 使用流程 在具体使用时,主要流程是: 声明1个 HashMap 的对象 向 HashMap 添加数据(成对 放入 键 - 值对) 获取 HashMap 的某...

TonyStarkSir
2018/08/08
37
0
手把手带你源码分析 HashMap 1.7

前言 HashMap 在 Java 和 Android 开发中非常常见 今天,我将带来 HashMap 的全部源码分析,希望你们会喜欢。 目录 1. 简介 类定义 3. 具体使用 3.1 主要使用API(方法、函数) 3.2 使用流程...

烂猪皮
2018/04/21
57
1
HashMap高并发

首先讲一下HashMap的Resize机制: 1.Hashmap在插入元素过多的时候需要进行Resize,Resize的条件是 HashMap.Size >= Capacity * LoadFactor。 Resize:HashMap的容量是有限的。当经过多次元素插...

qq_39566598
2017/12/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Redis集群搭建

服务器资源 ip 账号 配置 操作系统 xxx.70 root/xxx 磁盘50G(/)+150G(/home)、内存16G、CPU 16core CentOS Linux release 7.2.1511 (Core) xxx.74 root/xxx 磁盘50G(/)+150G(/home)、......

jxlgzwh
24分钟前
3
0
avro

一、 ```我们已经接触过很多序列化框架(或者集成系统),比如protobuf、hessian、thrift等,它们各有优缺点以及各自的实用场景,Avro也是一个序列化框架,它的设计思想、编程模式都和thi...

hexiaoming123
25分钟前
5
0
QML TextInput的字体超出控件范围

本文链接:https://blog.csdn.net/chyuanrufeng/article/details/54691998 问题描述 :QML TextInput输入内容超过TextInput的大小 当输入过多的字符串时,会出现内容超过TextInput的大小,字...

shzwork
27分钟前
4
0
《Java 8 in Action》Chapter 10:用Optional取代null

1965年,英国一位名为Tony Hoare的计算机科学家在设计ALGOL W语言时提出了null引用的想法。ALGOL W是第一批在堆上分配记录的类型语言之一。Hoare选择null引用这种方式,“只是因为这种方法实...

HelloDeveloper
28分钟前
3
0
进击的 Java ,云原生时代的蜕变

作者| 易立 阿里云资深技术专家<br /> <br />导读:云原生时代的来临,与Java 开发者到底有什么联系?有人说,云原生压根不是为了 Java 存在的。然而,本文的作者却认为云原生时代,Java 依然...

阿里巴巴云原生
30分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部