韦德国际_韦德国际1946官方网站_韦德国际1946手机版
做最好的网站

HashMap源码深入分析,源码分析

日期:2019-05-22编辑作者:韦德国际1946官方网站

转发请表明出处   

HashMap涉及到的事物还真是挺多的.看了几篇小说也好不轻易个小结吧

一、HashMap介绍

以此类,小编深信不疑各位相对使用过,并且在面试当中,碰到的也断然不少,如,你能说下hashmap的法则吗?它里面包车型大巴负载因子是什么样?它有如何线程安全主题素材吧,它的长度为何一定要选拔贰的指好几倍?相对于jdk一.7,版本,一.八做了哪些改观等等。对于这几个主题材料,假若您只有逗留在会用hashmap的基础上,那相对会一个难点。首先呢,对于hashmap的布局,它是四个数组 链表,在一.第88中学,也是有希望是数组 红黑树结构,又或然是互相混合体,至于怎么是这么的组织,在末端会剖析出来,本文首假若针对jdk一.八本子实行分析的。

上边主要会围绕那多少个地点开始展览

一、 hashmap的构造函数

2、hashmap的node内部类

3、 hashmap的put方法完毕

4、 hashmap的扩大容积实现 

伍、 hashmap的get方法落成

陆、 对于一.柒做了怎么样改观。

置于知识

在分析HashMap此前先说一些基础的知识.

HashMap源码深入分析,源码分析。二、HashMap的函数

 在看构造函数此前,先来询问下,那一个类的局地变量,如下

 1 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16,HashMap的默认大小
 2 
 3 static final int MAXIMUM_CAPACITY = 1 << 30; HashMap的最大容量,即数组长度
 4 
 5 static final float DEFAULT_LOAD_FACTOR = 0.75f;  HashMap的负载因子,
 6 
 7 static final int TREEIFY_THRESHOLD = 8;  链表转为红黑树的阈值
 8 
 9 transient Node<K,V>[] table;  内部存储元素的数组(HashMap的核心)
10 int threshold;  若使用默认构造函数,则该值为12,即16*0.75f,若不是默认构造函数,则该值由函数tableSizeFor计算而来,在第一次插入元素后,又会被重新计算,意义在于若map里元素个数超过这个值,则扩容
11 transient int size; HashMap的元素个数,即HashMap的大小

 HashMap壹共有七个构造函数

 1   //指定HashMap的初始化大小和指定负载因子
 2   public HashMap(int initialCapacity, float loadFactor) {
 3         if (initialCapacity < 0)
 4             throw new IllegalArgumentException("Illegal initial capacity: "  
 5                                                initialCapacity);
 6         if (initialCapacity > MAXIMUM_CAPACITY)
 7             initialCapacity = MAXIMUM_CAPACITY;
 8         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 9             throw new IllegalArgumentException("Illegal load factor: "  
10                                                loadFactor);
11         this.loadFactor = loadFactor;
12         this.threshold = tableSizeFor(initialCapacity);
13     }
14 
15   //只传入初始化HashMap的大小,默认负载因子0.75f
16   public HashMap(int initialCapacity) {
17         this(initialCapacity, DEFAULT_LOAD_FACTOR);
18     }
19 
20   //使用的最多的一个构造函数,默认大小为16,负载因子为0,75f
21    public HashMap() {
22         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
23     }

 

HashCode

它是2个int类型的值由jdk依据目的计算得出.种种对象都会有其一值.这里提到到和equals方法的关系.在Java中规定,假诺equals()方法再次回到true,那么比较的hashCode必须是十分的.由此重写equals方法必供给重写hashCode方法.

三、HashMap的Node内部类

 1 static class Node<K,V> implements Map.Entry<K,V> {
 2         final int hash;
 3         final K key;
 4         V value;
 5         Node<K,V> next;
 6 
 7         Node(int hash, K key, V value, Node<K,V> next) {
 8             this.hash = hash;
 9             this.key = key;
10             this.value = value;
11             this.next = next;
12         }
13 
14         public final K getKey()        { return key; }
15         public final V getValue()      { return value; }
16         public final String toString() { return key   "="   value; }
17 
18         public final int hashCode() {
19             return Objects.hashCode(key) ^ Objects.hashCode(value);
20         }
21 
22         public final V setValue(V newValue) {
23             V oldValue = value;
24             value = newValue;
25             return oldValue;
26         }
27 
28         public final boolean equals(Object o) {
29             if (o == this)
30                 return true;
31             if (o instanceof Map.Entry) {
32                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
33                 if (Objects.equals(key, e.getKey()) &&
34                     Objects.equals(value, e.getValue()))
35                     return true;
36             }
37             return false;
38         }
39     }

 

类的协会相比较轻松,完毕了Map.Entry接口,里面有hash、key、value、next多少个变量。 

HashMap的table数组也便是三个Node数组,各类Node前边又随即二个个Node节点,由各类Node的next变量去老是。

结构如下图(来源于百度)

图片 1

 

Map的蕴藏结构

Map的当中有1个Entry类,,它是二个单链表,存放了key,value,以及下3个Entry.
Entry存储在3个数组上,2个职位放贰个单链表.

Map的贮存方式
经过key获取vlaue的经过,首先通过key的hash值获取到map数组存放的目录,然后再通过key的equals方法赢得相应的值.

map的加载因子
默以为0.75 在hashMap中实际存款和储蓄量是数组的size * 0.7五也正是size为16实际上存款和储蓄1二之上因素的时候就能够把数组尺寸扩充学一年级倍为3②.万BlackBerry载因子为一,那么数组上都会有链表.查询会特别耗费时间.假如数值偏小,那么会浪费空间.
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1);

4、HashMap的put方法达成

 1     public V put(K key, V value) {
 2         return putVal(hash(key), key, value, false, true);
 3     }
 4   //参数解释:hash:为Key的hash值,onlyIfAbsent,该值若为true时,则若有重复key插入,则不改变旧值,evict目前只知道该值留个一个子类去实现的空方法参数
 5     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 6                    boolean evict) {
 7         Node<K,V>[] tab; Node<K,V> p; int n, i;
 8         if ((tab = table) == null || (n = tab.length) == 0)//若第一次插入元素,则此时table数组为Null或者长度为0,此时则进行使用resize进行初始化
 9             n = (tab = resize()).length;
10         if ((p = tab[i = (n - 1) & hash]) == null)//使用key与数组长度-1进行定位数组坐标,若该坐标下的元素为null,则直接new一个元素进行插入
11             tab[i] = newNode(hash, key, value, null);
12         else {   //此时代表数组下标已经有其他元素插入了,就意味着要插入的话,只能插入坐标下元素的后面
13             Node<K,V> e; K k;
14             if (p.hash == hash &&   //此步是为了判断插入的key是否和定位下的坐标元素相等,若相等,则表明插入的是同一个key
15                 ((k = p.key) == key || (key != null && key.equals(k))))
16                 e = p;  //e用来临时存储
17             else if (p instanceof TreeNode)//这个表明该位置的元素链表已经被转为了红黑树结构,接下来要用到红黑树结构来插入元素。
18                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
19             else {//若以上两个条件都不满足,则进行此步。
20                 for (int binCount = 0; ;   binCount) {//这个变量的作用是用来计算链表的长度,顺便遍历链表
21                     if ((e = p.next) == null) {//若是链表最后一个,则在末尾处插入Node节点
22                         p.next = newNode(hash, key, value, null);
23                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st,若变量长度超过阈值,这将该链表转为红黑树结构
24                             treeifyBin(tab, hash);
25                         break;
26                     }
27                     if (e.hash == hash &&//同样用来判断插入的key是否相等
28                         ((k = e.key) == key || (key != null && key.equals(k))))
29                         break;
30                     p = e;
31                 }
32             }
33             if (e != null) { // existing mapping for key
34                 V oldValue = e.value;
35                 if (!onlyIfAbsent || oldValue == null)//若onlyIfAbsent为true,则对旧值不进行覆盖
36                     e.value = value;
37                 afterNodeAccess(e);//提供给子类去实现的
38                 return oldValue;//返回旧值
39             }
40         }
41           modCount;//若进行到此步操作,则表明,插入的元素key没有和之前存在的重复。
42         if (  size > threshold)//判断size和threshold的大小,若前者大,则进行扩容。
43             resize();
44         afterNodeInsertion(evict);
45         return null;
46     }

 对于上述插入操作,也可分割为这几步。

1、判断table数组有没有开始化,若未有则初阶化,有则跳过。

2、使用key与数组的长短-一进行&运算,得出数组下标,若该下标未有元素则插入,有则跳过。

三、推断插入的key是或不是和该下标的成分key是或不是等于,若相等,则用e不经常存款和储蓄该下标地方成分,未有则跳过

肆、判别该下标后的要素是或不是是红黑树结构,借使,择用红黑树结构插入元素,不然跳过

五、举办遍历链表,在遍历进度中,有两步操作,一,遍历进程中是还是不是有平等key,二.遍历进度中,是或不是到了转为红黑树结构的阈值点。若前两步都不满足,则在链表末尾处插入成分。

六、若插入元素和HahsMap中设有同样key,则此步操作不开始展览,若不存在,不然对modCount实行 一,还有看size和threshold的尺寸,满意条件则开始展览扩大体量。

如上两个步骤正是插入成分的牵线。

或许细心的人会意识,在认清1致key的时候。都用到了equals方法,所以要值得注意的是,在用有些类充当key的时候,最佳自然要重写equals方法,不然可能得不到和谐想要的结果,而要重写equals方法,必然要重写hashCode方法,所以综上,充当key的类,最棒要重写hashCode和equals方法。来保障本身想要的结果。

源码深入分析

五、HashMap的扩大容积落成

 由HashMap的插入操作,很轻便得知,在张开初阶化操作和要素个数到达一定阈值,都会触发HashMap的扩大容积操作。上边就来看下它的扩大体量是怎么落到实处的。

 1 final Node<K,V>[] resize() {
 2         Node<K,V>[] oldTab = table;//一般为了不直接操作原数据都会赋值给一个临时变量
 3         int oldCap = (oldTab == null) ? 0 : oldTab.length;//计算旧table数组的长度
 4         int oldThr = threshold; //当table数组还没初始化且使用了默认构造函数,该值默认为0,
 5         int newCap, newThr = 0;
 6         if (oldCap > 0) {//表明table数组已经初始化了
 7             if (oldCap >= MAXIMUM_CAPACITY) {//若旧table数组长度大于MAX_CAPACITY,则不扩容,并设置threshold,返回旧数组
 8                 threshold = Integer.MAX_VALUE;
 9                 return oldTab;
10             }
11             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&//新数组长度为旧数组长度*2,至于为什么*2,不用急接下来会解释。
12                      oldCap >= DEFAULT_INITIAL_CAPACITY)
13                 newThr = oldThr << 1; // double threshold,同样新的threshold为旧的两倍,即double
14         }
15         else if (oldThr > 0) // initial capacity was placed in threshold,此种情况为数组还未初始化,但threshold已经被初始化了,表明初始化hashmap实例不是用了默认构造函数
16             newCap = oldThr;//若table数组初始化执行了该步操作,则必定会重新计算threshold,计算方式看23行。
17         else {               // zero initial threshold signifies using defaults,表明使用了默认构造函数,且是table数组的初始化。
18             newCap = DEFAULT_INITIAL_CAPACITY;//使用默认长度16,
19             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//初始化操作,threshold值为 0.75f*length。
20         }
21         if (newThr == 0) {//重新计算threshold值
22             float ft = (float)newCap * loadFactor;
23             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
24                       (int)ft : Integer.MAX_VALUE);
25         }
26         threshold = newThr;
27         @SuppressWarnings({"rawtypes","unchecked"})
28         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//建立一个新的长度的Node数组
29         table = newTab;
30         if (oldTab != null) {//此种情况表明是空间不足,引起的扩容,而不是初始化引起的扩容
31             for (int j = 0; j < oldCap;   j) {//将旧的数组元素赋给新数组,并且对key重新进行hash
32                 Node<K,V> e;
33                 if ((e = oldTab[j]) != null) {
34                     oldTab[j] = null;//为了更好的配合垃圾回收
35                     if (e.next == null)//该下标元素为null,直接插入
36                         newTab[e.hash & (newCap - 1)] = e;
37                     else if (e instanceof TreeNode)//红黑树结构另做处理
38                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
39                     else { // preserve order
40                         Node<K,V> loHead = null, loTail = null;
41                         Node<K,V> hiHead = null, hiTail = null;
42                         Node<K,V> next;
43                         do {//值得注意的是,赋值分了两步操作,该步循环是为了先连接好链表,即不用从数组下标开始一个一个的进行连接,先把链表串起来
44                             next = e.next;
45                             if ((e.hash & oldCap) == 0) {//第一步,表明key的hash值与旧数组长度化为二进制最高为不相同(如。10011和100000),这两个值&运算值为0
46                                 if (loTail == null)
47                                     loHead = e;
48                                 else
49                                     loTail.next = e;
50                                 loTail = e;
51                             }
52                             else {//第二步,与第一步相反,如果觉得难理解的话,可以将第一步理解为hash值小于旧数组长度,第二步hash值大于旧数组长度(说明:这种理解只是帮助理解,不是一定正确)
53                                 if (hiTail == null)
54                                     hiHead = e;
55                                 else
56                                     hiTail.next = e;
57                                 hiTail = e;
58                             }
59                         } while ((e = next) != null);
60                         if (loTail != null) {//和数组串起来
61                             loTail.next = null;
62                             newTab[j] = loHead;
63                         }
64                         if (hiTail != null) {//和数组串起来
65                             hiTail.next = null;
66                             newTab[j   oldCap] = hiHead;
67                         }
68                     }
69                 }
70             }
71         }
72         return newTab;//返回新的数组
73     }

 以上正是全体扩大体量操作,具体可分为这几步

一、先判别是初步化操作,照旧真的空间不够去扩大体积。

2、扩大体量的最大尺寸为MAXIMUM_CAPACITY。

三、重新总计threshold和数老总度的值。

4、假使真的要扩大体量,则张开数据迁移。

 上面也可以有商榷为啥数经理度一定是2的指好好多倍,上面来深入分析一下。

我们都精晓2的指好几倍化成贰进制,则最高位为1,其他位为0,若其减一,则退一人,且别的位都为1,若有任何二个数组和它举办&运算,则结果必然小于2的指好几倍,

此为其壹,是为着key的hash值能落在数组范围内。

这种结果和求余运算的结果壹致,能够使插入进来的成分相对于其余的测算能够更均匀的布满在数组中,不形成有些坐标成分众多,有些坐标未有的结果。

构造函数
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: "  
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: "  
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

并不曾实际创制三个Map,数组也并未创制.真正的创始是在put方法里调用的inflateTable()

本文由韦德国际发布于韦德国际1946官方网站,转载请注明出处:HashMap源码深入分析,源码分析

关键词: 看看jdk