莜,Java 8系列之重新认识HashMap(转载),四大银行

频道:体育世界 日期: 浏览:270

摘要

HashMap是Java程序员运用频率最高的用于映射(键值对)处理的数据类型。跟着JDK(Java Developmet Kit)版别的更新,JDK1.8对HashMap底层的完成进行了优化,例如引进红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的差异,深化探讨HashMap的结构完成和功用原理。

简介

Java为数据结构中的映射界说了一个接口java.util.Map,此接口首要有四个常用的完成类,分别是HashMap、魔眼战神张钧Hashtable、LinkedHashMap和TreeMap,类承继联络如下图所示:

下面针对各个完成类的特色做一些阐明:

(1) HashMap:它依据键的hashCode值存储数据,大多数状况下能够直接定位到它的值,因而具有很快的拜访速度,但遍历次第却是不确认的。 HashMap最多只答应一条记载的键为null,答应多条记载的值为null。HashMap非线程安全,即任一时刻能够有多个线程一起写HashMap,或许会导致数据的不一致。假定需求满意线程安全,能够用 Collections的synchronizedMap办法使HashMap具有线程安全的才能,或许运用ConcurrentHashMap。

(2) Hashtable:Hashtable是留传类,许多映射的常用功用与HashMap相似,不同的是它承自Dictionary类,而且是线程安全的,任一时刻只需一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引进了分段锁。Hashtable不主张在新代码中运用,不需求线程安全的场合能够用HashMap替换,需求线程安全的场合能够用ConcurrentHashMap替换。

(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记载的刺进次第,在用Iterator遍历LinkedHashMap时,先得到的记载肯定是先刺进的,也能够在结构时带参数,依照拜访次第排序。

(4) TreeMap:TreeMap完成SortedMap接口,能够把它保存的记载依据键排序,默许是按键值的升序排序,也能够指定排序的比较器,当用Iterator遍历TreeMap时,得到的记载是排过序的。假定运用排序的映射,主张运用TreeMap。在运用TreeMap时,key有必要完成Comparable接口或许在结构TreeMap传入自界说的Comparator,不然会在运行时抛出java.lang.ClassCastException类型的反常。

关于上述四种Map类型的类,要求映射中的key是不可变目标。不可变目标是该目标在创立后它的哈希值不会被改动。假定目标的哈希值发作改变,Map目标很或许就定位不到映射的方位了。

经过上面的比较,咱们知道了HashMap是Java的Map宗族中一个一般成员,鉴于它能够满意大多数场景的运用条件,所以是运用频度最高的一个。下文咱们首要结合源码,从存储结构、常用办法剖析、扩容以及安全性等方面深化解说HashMap的作业原理。

内部完成

搞清楚HashMap,首要需求知道HashMap是什么,即它的存储结构-字段;其次弄了解它能干什么,即它的功用完成-办法。下面咱们针对这两个方面详细打开解说。

存储结构-字段

从结构完成来讲,HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)完成的,如下如所示。

这儿需求讲了解两个问题:数据底层详细存储的是什么?这样的存储办法有什么长处呢?

(1) 从源码可知,HashMap类中有一个十分重要的字段,便是 Node[] table,即哈希桶数组,显着它是一个Node的数组。咱们来看Node[JDK1.8]是何物。

static class Node implements Map.Entry {
final int hash; //用来定位数组索引方位
final K key;
V value;
Node next; //链表的下一个node
Node(int hash, K key, V value, Node next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals莜,Java 8系列之从头认识HashMap(转载),四大银行(Object o) { ... }
}

Node是HashMap的一个内部类,完成了Map.Entry接口,实质是便是一个映射(键值对)。上图中的每个黑色圆点便是一个Node目标。

(2) HashMap便是运用哈希表来存储的。哈希表为处理抵触,能够选用敞开地址法和链地址法等来处理问题,Java中HashMap选用了链地址法。链地址法,简略来说,便是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。例如程序履行下面代码:

 map.put("xx","yy");

体系将调用"美团"这个key的hashCode()办法得到其hashCode 值(该办法适用于每个Java目标),然后再经过Hash算法的后两步运算(高位运算和取模运算,下文有介绍)来定位该键值对的存储方位,有时两个key会定位到相同的方位,表明发作了Hash磕碰。当然Hash算法核算成果越涣散均匀,Hash磕碰的概率就越小,map的存取功率就会越高。

假定哈希桶数组很大,即便较差的Hash算法也会比较涣散,假定哈希桶数组数组很小,即便好的Hash算法也会出现较多磕碰,所以就需求在空间本钱和时刻本钱之间权衡,其实便是在依据实践状况确认哈希桶数组的巨细,并在此基础上规划好的hash算法削减Hash磕碰。那么经过什么办法来操控map使得Hash磕碰的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案便是好的Hash算法和扩容机制。

在了解Hash和扩容流程之前,咱们得先了解下HashMap的几个字段。从HashMap的默许结构函数源码可知,结构函数便是对下面几个字段进行初始化,源码如下:

 int threshold; // 所能包容的key-value对极限 
final float loadFactor; // 负载因子
int modCount;
int size;

首要,Node[] table的初始化长度length(默许值是16),Load factor为负载因子(默许值是0.75),threshold是HashMap所能包容的最大数据量的Node(键值对)个数。threshold = length * Load factor。也便是说,在数组界说好长度之后,负载因子越大,所能包容的键值对个数越多。

结合负载因子的界说公式可知,threshold便是在此Load factor和length(数组长度)对应下答应的最大元素数目,超越这个数目就从头resize(扩容),扩容后的HashMap容量是之前容量的两倍。默许的负载因子0.75是对空间和时刻功率的一个平衡挑选,主张咱们不要修正,除非在时刻和空间比较特别的状况下,假定内存空间许多而又对时刻功率要求很高,能够下降负载因子Load factor的值;相反,假定内存空间严重而对时刻功率要求不高,能够增加负载因子loadFactor的值,这个值能够大于1。

size这个字段其实很好了解,便是HashMap中实践存在的键值对数量。留意和莜,Java 8系列之从头认识HashMap(转载),四大银行table的长度length、包容最大键值对数量threshold的差异。而modCount字段首要用来记载HashMap内部结构发作改变的次数,首要用于迭代的快速失利。着重一点,内部结构发作改变指的是结构发作改变,例如put新键值对,可是某个key对应的value值被掩盖不属于结构改变。

在HashMap中,哈希桶数组table的长度length巨细有必要为2的n次方(一定是合数),这是一种非惯例的规划,惯例的规划是把桶的巨细规划为素数。相对来说素数导致抵触的概率要小于合数,Hashtable初始化桶巨细为11,便是桶巨细规划为素数的运用(Hashtable扩容后不能确保仍是素数)。HashMap选用这种非惯例规划,首要是为了在取模和扩容时做优化,一起为了削减抵触,HashMap定位哈希桶索引方位时,也加入了高位参加运算的进程。

这儿存在一个问题,即便负载因子和Hash算法规划的再合理,也免不了会出现拉链过长的状况,一旦出现拉链过长,则会严重影响HashMap的功用。所以,在JDK1.8版别中,对数据结构做了进一步的优化,引进了红黑树。而当链表长度太长(默许超越8)时,链表就转换为红黑树,运用红黑树快速增修正查的特色进步HashMap的功用,其间会用到红黑树的刺进、删去、查找等算法。

功用完成-办法

HashMap的内部功用完成许多,本文首要从依据key获取哈希桶数组索引方位、put办法的详细履行、扩容进程三个具有代表性的点深化打开解说。

1. 确认哈希桶数组索引方位

不论增加、删去、查找键值对,定位到哈希桶数组的方位都是很要害的第一步。前面说过HashMap的数据结构是数组和链表的结合,所以咱们当然期望这个HashMap里边的元素方位尽量散布均匀些,尽量使得每个方位上的元素数量只需一个,那么当咱们用hash算法求得这个方位的时分,立刻就能够知道对应方位的元素便是咱们要的,不必遍历链表,大大大后寿寿花优化了查询的功率。HashMap定位数组索引方位,直接决议了hash办法的离散功用。先看看源码的完成(办法一+办法二):

办法一:
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h壹药网 ^ (h >>> 16) 为第二步 高位参加运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
办法二:
static int indexFor(int h, i切nt length) { //jdk1.7的源码,jdk1.8没有这个办法,可是完成原理相同的
return h & (length-1); //第三步 取模运算
}

这儿的Hash算法实质上便是三步:取key的hashCode值、高位运算、取模运算

关于恣意给定的目标,只需它的hashCode()回来值相同,那么程序调用办法一所核算得到的Hash码值总是相同的。咱们首要想到的便是把hash值对数组长度取模运算,这样一来,元素的散布相对来说是比较均匀的。可是,模运算的耗费仍是比较大的,在HashMap中是这样做的:调用办法二来核算该目标应该保存在table数组的哪个索引处。

这个办法十分奇妙,它经过h & (table.length -1)来得到该目标的保存位,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也便是h%length,可是&比%具有更高的功率。

在JDK1.8的完成中,优化了高位运算的算法,经过hashCode()的高16位异或低16位完成的:(h = k.hashCode()) ^ (h >>> 16),首要是从速度、成效、质量来考虑的,这么做能够在数组table的length比较小的时分,也能确保考虑到凹凸Bi5号线t都参加到Hash的核算中,一起不会有太大的开支。

下面举例阐明下,n为table的长度。

2. 剖析HashMap的put办法

HashMap的put办法履行进程能够经过下图来了解,自己有爱好能够去比照源码更清楚地研讨学习。

①.判别键值对数组table[i]是否为空或为null,不然履行resize()进行扩容;

②.依据键值key核算hash值得到刺进的数组索引i,假定table[i]==null,直接新建节点增加,转向⑥,假定table[i]不为空,转向③;

③.判福建旅游景点断table[i]的首个元素是否和key相同,假定相同直接掩盖value,不然转向④,这儿的相同指的是hashCode以及equals;

④.判别table[i] 是否为treeNode,即table[i] 是否是红黑树,假定是红黑树,则直接在树中刺进键值对,不然转向⑤;

⑤.遍历table[i],判别链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中履行刺进操作,不然进行链表的刺进操作;遍历进程中若发现key现已存在直接掩盖value即可;

⑥.刺进成功后,判别实践存在的键值对数量size是否超多了最大容量threshold,假定超越,进行扩容。

JDK1.8HashMap的put办法源码如下:

 1 public V put(K key, V value) {
2 // 对key的hashCode()做hash
3 return putVal(hash(key), key, value, false, true);
4 }
5
6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
7 boolean evict) {
8 Node[] tab; Node p; int n, i;
9 // 进程①:tab为空则创立
10 if ((tab = table) == null || (n = tab.length) == 0)
11 n = (tab = resize()).length;
12 // 进程②:核算index,并对null做处理
13 if ((p = tab[i = (n - 1) & hash]) == null)
14 tab[i] = newNode(hash, key, value, null);
15 else {
16 Node e; K k;
17 // 进程③:节点key存在,直接掩盖value
18 if (p.hash == hash &&
19 ((k = p.key) == key || (key != null && key.equals(k))))
20体彩七星彩开奖成果 e = p;
21 // 进程④:判别该链为红黑树
22 else if (p instanceof TreeNode)
23 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
24 // 进程⑤:该链为链表
25 else {
26 for (int binCount = 0; ; ++binCount) {
27 if ((e = p.next) ==叶一茜女儿 null) {
28 p.next = newNode(hash, key,value,null);
//链表长度大于8转换为红黑树进行处理
29 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
30 treeifyBin(tab, hash);
31 break;
32 }
// key现已存在直接掩盖value
33 if (e.hash == hash &&
34 ((k = e.key) == key || (key != null && key.equals(k)))) break;
36 p = e;
37 }
38 }
39
40 if (e != null) { // existing mapping for key
41 V oldValue = e.value;
42 if (!onlyIfAbsent || oldValue == null)
43 e.value = value;
44 afterNodeAccess(e);
45 return oldValue;
46 }
47 }
48 ++modCount;
49 // 进程⑥:超越最大容量 就扩容
50 if (++size > threshold)
51 resize();
52 afterNodeInsertion(evict);
53 return null;
54 }

3. 扩容机制

扩容(resize)便是从头核算容量,向HashMap目标里不断的增加元素,而HashMap目标内部的数组无法装载更多的元素时,目标就需求扩展数组的长度,以便能装入更多的元素。当然Java里的数组是无法主动扩容的,办法是运用一个新的数组替代已有的容量小的数组,就像咱们用一个小桶装水,假定想装更多的水,就得换大水桶。

咱们剖析下resize的源码,鉴于JDK1.8融入了红黑树,较杂乱,为了便于了解咱们依然运用JDK1.7的代码,好了解一些,实质上差异不大,详细差异后文再说。

 1 void resize(int newCapacity) { //传入新的容量
2 Entry[] oldTable = table; //引证扩容前的Entry数组
3 int oldCapacity = oldTable.length;
4 if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的学园奶爸数组巨细假定现已到达最大(2^30)了
5 threshold = Integer.MAX_VALUE; //修正阈值为int的最大值(2^31-1),这样今后就不会扩容了
6 retshowgirl游艇门urn;
7 }
8
9 Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
10 transfer(newTable); 莜,Java 8系列之从头认识HashMap(转载),四大银行//!!将数据转移到新的Entry数组里
11 table = newTable; //HashMap的table特点引证新的Entry数组
12 threshold = (int)(newCapacity * loadFactor);//修正阈值
13 }

这儿便是运用一个容量更大的数组来替代已有的容量小的数组,transfer()办法将原有Entry数组的元素拷贝到新的Entry数组里。

 1 void transfer(Entry[] newTable) {
2 Entry[] src = table; //src引证了旧的Entry数组
3 int newCapacity = newTable.length;
4 for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
5 Entry e = src[j]; //获得旧Entry数组的每个元素
6 if (e != null) {
7 src[j] = null;//开释旧Entry数组的目标引证(for循环后,旧的Entry数组不再引证任何目标)
8 do {
9 Entry next = e.next;
10 int i = indexFor(e.hash, newCapacity); //!!从头核算每个元素在数组中的方位
11 e.next = newTable[i]; //符号[1]
12 newTable[i] = e; //将元素放在数组上
13 e = next; //拜访下一个Entry链上的元素
14 } while (e != null);
15 }
16 }
17 }

newTable[i]的引证赋给了e.next,也便是运用了单链表的头刺进办法,同一方位上新元素总会被放在链表的头部方位;这样先放在一个索引上的元素终会被放到Entry链的尾部(假定发作了hash抵触的话),这一点和Jdk1.8有区莜,Java 8系列之从头认识HashMap(转载),四大银行别,下文详解。在旧数组中同一条Entry链上的元素,经过从头核算索引方位后,有或许被放到了新数组的不同方位上。

下面举个比如阐明下扩容进程。假定了咱们的hash算法便是简略的用key人头马 mod 一下表的巨细(也便是数组的长度)。其间的哈希桶数组table的size=2, 所以key = 3、7、5,put次第依次为 5、7、3。在mod 2今后都抵触在table[1]这儿了。这儿假定负载因子 loadFactor=1,即当键值对的实践巨细size 大于 table的实践巨细时进行扩容。接下来的三个进程是哈希桶数组 resize成4,然后一切的Node从头rehash的进程。

下面咱们解说下JDK1.8做了哪些优化。经过观测能够发现,咱们运用的是2次幂的扩展(指长度扩为本来2倍),所以,元素的方位要么是在原方位,要么是在原方位再移动2次幂的方位。看下图能够了解这句话的意思,n为table的长度,图(a)表明扩容前的key1和key2两种key确认索引方位的示例,图(b)表明扩容后key1和key2两种key确认索引方位的示例,其间hash1是key1对应的哈希与高位运算成果。

元素在从头核算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(赤色),因而新的index就会发作这样的改变:

因而,咱们在扩大HashMap的时分,不需求像JDK1.7的完成那样从头核算hash,只需求看看本来的hash值新增的那个bit是1仍是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,能够看看下图为16扩大为32的resize示意图:

这个规划的确十分的奇妙,既省去了从头核算hash值的时刻,而且一起,因为新增的1bit是0仍是1能够认为是随机的,因而resize的进程,均匀的把之前的抵触的节点涣散到新的buc四物汤ket了。这一块便是JDK1.8新增的优化点。有一点留意差异,JDK1.7中rehash的时分,旧链表搬迁新链表的时分,假定在新表的数组索引方位相同,则链表元素会倒置,可是从上图能够看出,JDK1.8不会倒置。有爱好的同学能够研讨下JDK1.8的resize源码,写的很赞,如下:

1 final Node[] resize() {
2 Node[] oldTab = table;
3 int oldCap = (oldTab == null) ? 0 : oldTab.length;
4 int oldThr = threshold;
5 int newCap, newThr = 0;
6 if (oldCap > 0) {
7 // 超越最大值就不再扩大了,就只好随你磕碰去吧
8 if (oldCap >= MAXIMUM_CAPACITY) {
9 threshold = Integer.MAX_VALUE;
10 return oldTab;
11 }
12 // 没超越最大值,就扩大为本来的2倍
13 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
14 oldCap >= DEFAULT_INITIAL_CAPACITY)
15 newThr = oldThr << 1; // double threshold
16 }
17 else if (oldThr > 0) // initial capacity was placed in threshold
18 newCap = oldThr;
19 else { // zero initial threshold signifies using defaults
20 newCap = DEFAULT_INITIAL_CAPACITY;
21 n莜,Java 8系列之从头认识HashMap(转载),四大银行ewThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
22 }
23 // 核算新的resize上限
24 if (newThr == 0) {
25
26 float ft = (float)newCap * loadFactor;
27 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
28 (int)ft : Integer.MAX_VALUE);
29 }
30 thres徐州英才网hold = newThr;
31 @SuppressWarnings({"rawtypes","unchecked"})
32 Node[] newTab = (Node[])new Node[newCap];
33 table = newTab;
34 if (oldTab != null) {
35 // 把每个bucket都移动到新的buckets中
36 for (int j = 0; j < oldCap; ++j) {
37 Node e;
38 if ((e = oldTab[j]) !=流量君 null) {
39 oldTab[j] = null;
40 if (e.next == null)
41 newTab[e.hash & (newCap - 1)] = e;
42 else if (e instanceof TreeNode莜,Java 8系列之从头认识HashMap(转载),四大银行)
43 ((TreeNode)e).split(this, newTab, j, oldCap);
44 else { // 链表优化重hash的代码块
45 Node loHead = null, loTail = null;
46 Node hiHead = null, hiTail = null;
47 Node next;
48 do {
49 next = e.next;
50 // 原索引
51 if ((e.hash & oldCap) == 0) {
52 if (loTail == null)
53 loHead = e;
54 else
55 loTail.next = e;
56 loTail = e;
57 }
58 // 原索引+oldCap
59 else {
60 if (hiTail == null)
61 hiHead = e;
62 else
63 hiTail.next = e;
64 hiTail = e;
65 }
66 } while ((e = next) != null);
67 // 原索引放到bucket里
68 if (loTail != null) {
69 loTail.next = null;
70 newTab[j] = loHead;
71 }
72 // 原索引+oldCap放到bucket里
73 if (hiTa吴绮珊il != null) {
74 hiTail.next = null;
75 newTab[j + oldCap] = hiHead;
76 }
77 }
78 }
79 }
80 }
81 return newTab;
82 }

线程安全性

在多线程运用场景中,应该尽量防止运用线程不安全的HashMap,而运用线程安全的ConcurrentHashMap。那么为什么说HashMap是线程不安全的,下面举比如阐明在并发的多线程运用场景中运用HashMap或许形成死循环。代码比如如下(便于了解,依然运用JDK1.7的环境):

public class HashMapInfiniteLoop { 
private static HashMap map = new HashMap(2,0.75f);
public static void main(String[] args) {
map.put(5, "C");
new Thread("Thread1") {
public void run() {
map.put(7, "B");
System.out.println(map);
};
}.start();
newx69 Thread("莜,Java 8系列之从头认识HashMap(转载),四大银行Thread2") {
public void run() {
map.put(3, "A);
System.out.println(map);
};
}.start();
}
}

其间,map初始化为一个长度为2的数组,loadFactor=0.75,threshold=2*0.75=1,也便是说当put第二个key的时分,map就需求进行resize。

经过设置断点让线程1和线程2一起debug到transfer办法(3.3末节代码块)的首行。留意此刻两个线程现已成功增加数据。铺开thread1的断点至transfer办法的“Entry next = e.next;” 这一行;然后铺开线程2的的断点,让线程2进行resize。成果如下图。

留意,Thread1的 e 指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。

线程一被调度回来履行,先是履行 newTalbe[i] = e, 然后是e = next,导致了e指向了key(7),而下一次循环的next = e.next导致了next指向了key(3)。

e.next = newTable[i] 导致 key(3).next 指向了 key(7)。留意:此刻的key(7).next 现已指向了key(3), 环形链表就这样出现了。

所以,当咱们用线程一调用map.get(11)时,悲惨剧就出现了——Infinite艾米莉亚簿本 Loop。

JDK1.8与JDK1.7的功用比照

HashMap中,假定key经过hash算法得出的数组索引方位悉数不相同,即Hash算法十分好,那样的话,g血源咒骂etKey办法的时刻杂乱度便是O(1),假定Hash算法技能的成果磕碰十分多,假定Hash算极端差,一切的Hash算法成果得出的索引方位相同,那样一切的键值对都会集到一个桶中,或许在一个链表中,或许在一个红黑树中,时刻杂乱度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化,整体功用优于JDK1.7,下面咱们从两个方面用比如证明这一点。

Hash较均匀的状况

为了便于测验,咱们先写一个类Key,如下:

class Key implements Comparable {
private final int value;
Key(int value) {
this.value = value;
}
@Override
public int compareTo(Key o) {
return Integer.compare(this.value, o.value);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Key key = (Key) o;
return value == key.value;
}
@Override
public int hashCode() {
return value;
}
}

这个类复写了equals办法,而且供给了相当好的hashCode函数,任何一个值的hashCode都不会相同,因为直接运用value作为hashcode。为了防止频频的GC,我将不变的Key实例缓存了起来,而不是一遍一遍的创立它们。代码如下:

public class Keys {
public static final int MAX_KEY = 10_000_000;
private static final Key[] KEYS_CACHE = new Key[MAX_KEY];
static {
for (int i = 0; i < MAX_KEY; ++i) {
KEYS_CACHE[i] = new Key(i);
}
}
public static Key of(int value) {
return KEYS_CACHE[value];
}
}

现在开端咱们的实验,测验需求做的仅仅是,创立不同size的HashMap(1、10、100、......10000000),屏蔽了扩容的状况,代码如下:

 static void test(int mapSize) {
HashMap map = new HashMap(mapSize);
for (int i = 0; i < mapSize; ++i) {
map.put(Keys.of(i), i);
}
long beginTime = System.nanoTime(); //获取纳秒
for (int i = 0; i < mapSize; i++) {
map.get(Keys.of(i));
}
long endTime = System.nanoTime();
System.out.println(endTime - beginTime);
}
public static void main(String[] args) {
for(int i=10;i<= 1000 0000;i*= 10){
test(i);
}
}

在测验中会查找不同的值,然后衡量花费的时刻,为了核算getKey的均匀时刻,咱们遍历一切的get办法,核算总的时刻,除以key的数量,核算一个均匀值,首要用来比较,绝对值或许会受许多环境要素的影响。成果如下:

经过观测测验成果可知,JDK1.8的功用要高于JDK1.7 15%以上,在某些size的区域上,乃至高于100%。因为Hash算法较均匀,JDK1.8引进的红黑树作用不显着,妹子下面咱们看看Hash不均匀的的状况。

Hash极不均匀的状况

假定咱们又一个十分差的Key,它们一切的实例都回来相同的hashCode值。这是运用HashMap最坏的状况。代码修正如下:

class Key implements Comparable {
//...
@Override
public int hashCode() {
return 1;
}
}

依然履行main办法,得出的成果如下表所示:

从表中成果中可知,跟着size的变大,JDK1.7的花费时刻是增加的趋势,而JDK1.8是显着的下降趋势,而且出现对数增加安稳。当一个链表太长的时分,HashMap会动态的将它替换成一个红黑树,这话的话会将时刻杂乱度从O(n)降为O(logn)。hash算法均匀和不均匀所花费的时刻显着也不相同,这两种状况的相比照较,能够阐明一个好的hash算法的重要性。

测验环境:处理器为2.2 GHz Intel Core i7,内存为16 GB 1600 MHz DDR3,SSD硬盘,运用默许的JVM参数,运行在64位的OS X 10.10.1上。

小结

(1) 扩容是一个特别耗功用的操作,所以当程序员在运用HashMap的时分,预算map的巨细,初始化的时分给一个大致的数值,防止map进行频频的扩容。

(2) 负载因子是能够修正的,也能够大于1,可是主张不要容易修正,除非状况十分特别。

(3) HashMap是线程不安全的,不要在并发的环境中一起操作HashMap,主张运用ConcurrentHashMap。

(4) JDK1.8引进红黑树大程度优化了HashMap的功用。

(5) 还没晋级JDK1.8的,现在开端晋级吧。HashMap的功用提高仅仅是JDK1.8的冰山一角。

来历:知乎:美团技能团队,如有侵权请联络自己删去

热门
最新
推荐
标签