剖析java中hashmap数据结构的源码及其性能优化

《剖析java中hashmap数据结构的源码及其性能优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、剖析Java中HashMap数据结构的源码及其性能优化这篇文章主要介绍了Java中HashMap数据结构的源码及其性能优化,文中以Java8后HashMap的性能提升來讨论了HashMap的一些优化点，需要的朋友可以参考下存储结构首先，HashMap是基于哈希表存储的。它内部有一个数组，当元素要存储的时候，先计算其key的哈希值，根据哈希值找到元素在数组中对应的下标。如杲这个位置没有元素，就直接把当前元素放进去，如果有元素了（这里记为A）,就把当前元素链接到元素A的前面，然后把当前元素放入数组屮。所以在Hashmap数组其实保存的是链表的首节点。下面是百度百科的一张图：EntryEn

2、tryEntryKeyKeyEntryValueValueEnttyEntryEntryEntryEnttyEntryEntry如上图，每个元素是一个Entry对象，在其屮保存了元素的key和value,还有一个指针可用于指向下一个对象。所有哈希值相同的key（也就是冲突了）用链表把它们串起来，这是拉链法。内部变量〃默认初始容量staticfinalintDEFAULT_INITIAL_CAPACITY=16;〃最大容量staticfinalintMAXIMUM_CAPACITY=1«30;〃默认装载因子staticfinalfloatDEFAULT_LOAD_FACTOR=0.75

3、f;〃哈希表transientEntry[]table;〃键值对的数量transientintsize;〃扩容的阈值intthreshold;〃哈希数组的装载因子finalfloatloadFactor;在上面的变量中，capacity是指哈希表的长度，也就是table的大小，默认为16。装载因子loadFactor是哈希表的“装满程度”，JDK的文档是这样说的：Theloadfactorisameasureofhowfullthehashtableisallowedtogetbeforeitscapacityisautomaticallyincreased・Whenthe

4、numberofentriesinthehashtableexceedstheproductoftheloadfactorandthecurrentcapacity,thehashtableisrehashed(thatis,internaldatastructuresarerebuilt)sothatthehashtablehasapproximatelytwicethenumberofbuckets・大体意思是：装载因子是哈希表在扩容之前能装多满的度量值。当哈希表中“键值对”的数量超过当前容M(capacity)和装载因子的乘积后，哈希表重新散列(也就是内部的数据结构重建了)，并

5、且哈希表的容量大约变为原来的两倍。从上面的变量定义可以看出，默认的装载因子DEFAULT_LOAD_FACTOR是0.75。这个值越大,空间利用率越高，但查询速度(包括get和put)操作会变慢。明白了装载因子之后，threshold也就能理解了，它其实等于容量*装载因子。构造器publicHashMap(intinitialCapacity,floatloadFactor){if(initialcapacity<0)thrownewHlegalArgumentException("lllegalinitialcapacity:"+initialcapacity);if(initia

6、lCapacity>MAXIMUM_CAPACITY)initialcapacity=MAXIMUM_CAPACITY;if(loadFactor<=011Float.isNaN(loadFactor))thrownewHlegalArgumentException("Illegalloadfactor:"+loadFactor);//Findapowerof2>=initialcapacityintcapacity=1;while(capacity

7、ctor;threshold=(int)Math.min(capacity*loadFactor,MAXIMUM_CAPACITY+1);table=newEntry[capacity];〃给哈希表分配空间useAltHashing=sun.misc.VM.isBooted()&&(capacity>=Holder.ALTERNATIVE_HASHING_THRESHOLD);init();}构造器有好儿个，最终都会调用上面的这个。它接受两个参数，一个是初