Java源码角度分析HashMap用法

2023-09-18 10:10:05 59

—HashMap—

优点：超级快速的查询速度，时间复杂度可以达到O（1）的数据结构非HashMap莫属。动态的可变长存储数据（相对于数组而言）。

缺点：需要额外计算一次hash值，如果处理不当会占用额外的空间。

—HashMap如何使用—

平时我们使用hashmap如下

Mapmaps=newHashMap();
maps.put(1,"a");
maps.put(2,"b");

上面代码新建了一个HashMap并且插入了两个数据，这里不接受基本数据类型来做K,V

如果这么写的话，就会出问题了：

Mapmaps=newHashMap();

我们为什么要这样使用呢？请看源码：

publicclassHashMap
extendsAbstractMap
implementsMap,Cloneable,Serializable

这是HashMap实现类的定义。

—HashMap是一个动态变长的数据结构—

在使用HashMap的时候，为了提高执行效率，我们往往会设置HashMap初始化容量：

Maprm=newHashMap(2)

或者使用guava的工具类Maps，可以很方便的创建一个集合，并且，带上合适的大小初始化值。

Mapmap=Maps.newHashMapWithExpectedSize(7);

那么为什么要这样使用呢？我们来看他们的源码构造函数。

未带参的构造函数：

publicHashMap(){
this.loadFactor=DEFAULT_LOAD_FACTOR;
threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
table=newEntry[DEFAULT_INITIAL_CAPACITY];
init();
}

publicHashMap(){
this.loadFactor=DEFAULT_LOAD_FACTOR;
threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
table=newEntry[DEFAULT_INITIAL_CAPACITY];
init();
}

/**
*ConstructsanemptyHashMapwiththespecifiedinitial
*capacityandthedefaultloadfactor(0.75).
*
*@paraminitialCapacitytheinitialcapacity.
*@throwsIllegalArgumentExceptioniftheinitialcapacityisnegative.
*/
publicHashMap(intinitialCapacity){
this(initialCapacity,DEFAULT_LOAD_FACTOR);
}

名词解释：

DEFAULT_LOAD_FACTOR//默认加载因子，如果不制定的话是0.75
DEFAULT_INITIAL_CAPACITY//默认初始化容量，默认是16
threshold//阈（yu）值根据加载因子和初始化容量计算得出，threshold表示当HashMap的size大于threshold时会执行resize操作。

因此我们知道了，如果我们调用无参数的构造方法的话，我们将得到一个16容量的数组。

所以问题就来了：如果初始容量不够怎么办？

数组是定长的，如何用一个定长的数据来表示一个不定长的数据呢，答案就是找一个更长的，但是在resize的时候是很降低效率的。所以我们建议HashMap的初始化的时候要给一个靠谱的容量大小。

—HashMap的Put方法—

publicVput(Kkey,Vvalue){
if(key==null)//键为空的情况，HashMap和HashTable的一个区别
returnputForNullKey(value);
inthash=hash(key.hashCode());//根据键的hashCode算出hash值
inti=indexFor(hash,table.length);//根据hash值算出究竟该放入哪个数组下标中
for(Entrye=table[i];e!=null;e=e.next){//整个for循环实现了如果存在K那么就替换V
Objectk;
if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
VoldValue=e.value;
e.value=value;
e.recordAccess(this);
returnoldValue;
}
}

modCount++;//计数器
addEntry(hash,key,value,i);//添加到数组中
returnnull;
}

如果插入的数据超过现有容量就会执行

addEntry(hash,key,value,i);

voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
Entrye=table[bucketIndex];
table[bucketIndex]=newEntry(hash,key,value,e);
if(size++>=threshold)
resize(2*table.length);
}

这里显示了如果当前size++>threshold的话那么就会扩展当前的size的两倍，执行resize（2*table.length）,那么他们是如何扩展的呢？

voidresize(intnewCapacity){ Entry[]oldTable=table; intoldCapacity=oldTable.length; if(oldCapacity==MAXIMUM_CAPACITY){ threshold=Integer.MAX_VALUE; return; } Entry[]newTable=newEntry[newCapacity];new一个新的数组， transfer(newTable);//将就数组转移到新的数组中 table=newTable; threshold=(int)(newCapacity*loadFactor);//重新计算容量 }

对于转移数组transfer是如何转移的呢？

voidtransfer(Entry[]newTable){ Entry[]src=table; intnewCapacity=newTable.length; for(intj=0;je=src[j]; if(e!=null){ src[j]=null; do{ Entrynext=e.next; inti=indexFor(e.hash,newCapacity);//根据hash值个容量重新计算下标 e.next=newTable[i]; newTable[i]=e; e=next; }while(e!=null); } } }

—hashmap扩容额外执行次数—

因此如果我们要添加一个1000个元素的hashMap，如果我们用默认值那么我么需要额外的计算多少次呢

当大于16*0.75=12的时候，需要从新计算12次

当大于16*2*0.75=24的时候，需要额外计算24次

……

当大于16*n*0.75=768的时候，需要额外计算768次

所以我们总共在扩充过程中额外计算12+24+48+……+768次

因此强力建议我们在项目中如果知道范围的情况下，我们应该手动指定初始大小像这样：

Mapmaps=newHashMap(1000);

总结：这就是为什么当hashmap使用过程中如果超出初始容量后他的执行效率严重下降的原因。

以上就是本文关于Java源码角度分析HashMap用法的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

上一篇
Python简单实现socket信息发送与监听功能示例下一篇
jQuery封装animate.css的实例

热门推荐

1 毛坯房验收经验和常识看了之后再验房心里有底

2 二手房收房如何交接二手房收房注意问题

3 专业验收毛坯房的价格商品房验收合格的标准

4 精装房怎么验收精装房请验房师有用吗

5 一般要到哪里找验房师验房师有哪些作用呢

6 请人验房一般是多少钱验房师费用是多少

7 怎样测量房子面积建筑面积和使用面积怎么算

8 收房需要注意什么仔细检查不松懈

9 收房时三书一证一表是什么主要作用介绍

10 交房时交房税费有哪些本文为你一一讲解

11 验房都需要验什么要做哪些准备呢

12 毛坯房验房师有必要请吗毛坯房装修完如何验收

13 地下室防水工程质量验收规范详解

14 水性涂料、油性涂料区别介绍

15 零基础布艺DIY工坊教你做超萌猫头鹰钥匙包

16 三棵树漆怎么样？三棵树漆官方网站

17 家庭“装修套餐”中猫腻你知道吗？

18 小空间大浴望卫浴间装修巧支招

Java源码角度分析HashMap用法

热门推荐

随机推荐