百木园-与人分享,
就是让自己快乐。

2、HashMap源码分析

目录

  • 1 一般数据结构及特点
  • 2 HashMap基本属性说明
  • 3 HashMap 数据结构
    • 3.1构造函数
    • 3.2 Node<k,v>分析
  • 4 put过程分析
    • 4.1 扩容方法resize()分析
    • 4.2 put方法分析
  • 5 关于HashMap
    • 5.1 HashMap如何实现put、get操作时间复杂度为O(1)~O(n)?
    • 5.2 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树?
    • 5.3 HashMap初始化时为什么要给自定义的初始容量?
    • 5.4 HashMap如何保证容量始终是2的幂?
    • 5.5 HashMap为何要保证容量始终是2的幂
    • 5.6 HashMap计算hash值
      • 5.6.1 key的hash值>>>16,为什么要这样做呢?
    • 5.7 HashMap为什么是线程不安全的?
  • 6 get 过程分析

特别:下文的“容量”、“数组长度”,“capacity” 都是指底层数组长度,即 table.length

1 一般数据结构及特点

  1. 数组:占用连续内存的数据结构,查找容易[O(1)],插入困难[O(n)]
  2. 链表:由一组指向(单向或者双向)的节点连接的数据结构,内存不连续,查找困难,但插入删除容易
  3. 哈希表:插入删除查找都容易的数据结构
  4. 数组下标是通过:(Node<K, V>[] 的容量-1)&(hash(key))的出来的

本章要解决的问题:

  • HashMap的数据结构实现方式
  • HashMap是怎么做到为get、put操作提供稳定的时间复杂度的
  • HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树
  • HashMap初始化时为什么要给自定义的初始容量。
  • HashMap如何保证容量始终是2的幂
  • HashMap为何要保证容量始终是2的幂
  • HashMap的hash值如何计算
  • HashMap为什么是线程不安全的

2 HashMap基本属性说明

常量部分:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子
static final int TREEIFY_THRESHOLD = 8;  //链表转红黑树阈值
static final int UNTREEIFY_THRESHOLD = 6; //红黑树转链表阈值
static final int MIN_TREEIFY_CAPACITY = 64;  //链表转转红黑树的数组最小容量
transient int size; //HashMap的元素个数
  • default_initial_capacity:初始容量=16
  • maximum_capacity:最大容量=1<<30。
  • default_load_factor:负载因子=0.75。
  • threshold:下一个触发扩容操作的阈值,threshold = capacity * load_factor。当元素数量(size值)超过阈值时触发扩容,新容量是旧容量2倍
  • treeify_threshold:链表转红黑树时链表长度阈值=8
  • untreeify_threshold: 红黑树转链表阈值=6,红黑树节点小于6就会转成链表
  • Node<K, V> implements Map.Entry<K, V> :HashMap存放数据的基本单位,里面存有hash值、key、value、next。
  • Node<K, V>[] table:存放Node节点的数组,HashMap底层数组,数组元素可以为单节点Node、多节点链表、多节点红黑树。
  • size:成员变量,表示当前Map的键值对数量,在put、remove、clear操作,会修改该值。扩容也是通过阈值跟size进行比较决定

3 HashMap 数据结构

  • HashMap是一个Node类型的数组,每个元素可以为单节点、链表、红黑树。

  • Java8之前,HashMap的数据结构如下:

数组+链表:链表是为了解决hash冲突
2、HashMap源码分析

  • Java8,HashMap的数据结构如下:
    数组+链表+红黑树
    2、HashMap源码分析

3.1构造函数

Tips:

  1. 确定加载因子
  2. 根据初始容量参数重新计算扩容阈值(大于或等于初始容量且一定等于2的幂的那个数
    tableSizeFor(initialCapacity):确定扩容阈值:大于或等于初始容量且一定等于2的幂的那个数;比如cap=8则返回8;cap=9则返回16

源码分析如下:

//构造函数一:无参构造函数:加载因子(0.75)和初始容量(16)分别使用默认值
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//构造函数二:
//指定初始容量,调用HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造函数三:同时指定初始容量和加载因子
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;
    //  确定扩容阈值:大于或等于初始容量且一定等于2的幂的那个数;比如cap=8则返回8;cap=9则返回16
    this.threshold = tableSizeFor(initialCapacity);
}
//构造函数三:创建一个跟参数有相同结构的map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

3.2 Node<k,v>分析

tips:一个简单的K-V模型的数据体,提供对key value的set get操作
源码如下:

/**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + \"=\" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value); // key value 的hash值再做异或运算
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

4 put过程分析

4.1 扩容方法resize()分析

HashMap的容量变化通常存在以下几种情况:

  1. 空参数的构造函数:实例化的HashMap默认内部数组是null,即没有实例化。第一次调用put方法时,则会开始第一次初始化扩容,长度为16。【懒加载

  2. 有参构造函数:用于指定容量。根据阈值计算方式【大于或等于初始容量且一定等于2的幂的那个数】,将这个数设置赋值给阈值。第一次调用put方法时,会将阈值赋值给容量(第一步),然后让 阈值=负载因子X容量(第二步)
     。(因此并不是我们手动指定了容量就一定不会触发扩容,超过阈值后一样会扩容!!)

  3. 如果不是第一次扩容,则容量变为原来的2倍,阈值也变为原来的2倍。(负载因子还是不变)

  4. 首次put时,先会触发扩容(底层table初始化),然后存入数据,然后判断是否需要扩容;不是首次put,则不再初始化,直接存入数据,然后再判断是否需要扩容;

参看源码:

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//当前数组
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //非首次put,扩容阈值变为原来2倍;容量变为原来的2倍
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;//达到最大值,不能扩容,返回当前数组
            }
            //数组容量扩大为原来2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // 将扩容阈值变为原来2倍
        }
        
        //第一次 put 的时候,【对应使用 new HashMap(int initialCapacity) 初始化后】
        else if (oldThr > 0) 
            newCap = oldThr; //如果初始化Map时指定了初始容量,则数组容量=扩容阈值(参照阈值的计算)
        
        //第一次 put 的时候 ,【对应使用 new HashMap() 初始化后】
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;//没有指定初始容量,则数组容量=默认初始容量
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//扩容阈值=加载因子*默认初始容量=12
        }

        //第一次put且有指定初始容量时 :重新计算扩容阈值:新扩容阈值=加载因子*新数组长度
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;

       //计算好容量初始化一个新的数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //如果第一次put,这里就直接返回newTab,扩容过程结束;
        table = newTab;
        if (oldTab != null) {
        // 开始遍历原数组,进行数据迁移。
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)//数组当前位置不存在链表或者红黑树,则直接put到该位置
                        newTab[e.hash & (newCap - 1)] = e; //返回单节点的Node数组
                    else if (e instanceof TreeNode)
                        //红黑树
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { 
                        //链表
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

4.2 put方法分析

源码分析:

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * @param hash:key的hash值
     * @param onlyIfAbsent  :false表示key存在时,覆盖value
     * @param evict if false, the table is in creation mode.  待补充
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
           //第一次put,先执行数组初始化操作
            n = (tab = resize()).length;
        //当前key对应的数组下标没有元素,则直接初始化新的Node到该数组位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null); //注意此时Node没有Next
        else {
        //当前key对应的数组下标已经存在元素
            Node<K,V> e; K k;
            // 情况一://该位置的元素跟新put进来的数据key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;    //注意这里是引用的赋值,因此后面e.value=value可以实现value覆盖
            //情况二:当前位置是红黑树结构
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //情况三:当前位置是链表结构
                for (int binCount = 0; ; ++binCount) {
                    //遍历到达链表末端
                    if ((e = p.next) == null) {
                        //创建新的Node并放在链表的末端
                        p.next = newNode(hash, key, value, null);
                        // treeify_threshold 为 8,所以,如果新插入的值是链表中的第 8 个,将链表转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //在链表当前位置找到相同的key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break; //这里break,代码后面统一对e进行value的覆盖处理
                    //此时既未遍历到链表末端,也没有发现key相等,则继续链表遍历
                    p = e;   //这个赋值,相当于链表的遍历,尾部指向下一个节点的头部,实现链表遍历
                }
            }
            if (e != null) { // existing mapping for key  key相等时
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;  //新的value覆盖旧的value值
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
        //每次put操作完成后,size自增;
        //如果size超过阈值,则在put完成后,再次执行扩容
            resize();
        afterNodeInsertion(evict);//父类抽象方法的实现,HashMap不做任何实现
        return null;
    }
  • 第一次put时扩容过程如下:
容量:C
加载因子:F
扩容阈值:T

------ 1、无参初始化:
F=0.75
C=0
T=0

------ 2、有参初始化:容量参数=7
F=0.75
C=0
T=tableSizeFor(7)=8  //1、2、4、8 。。。大于7 所以取8

------ 3、第一次put && 无参初始化时
F=0.75
C=16(默认容量)
T=16*0.75=12

------ 4、第一次put && 有参初始化时
F=0.75
C=T=8 // 容量=阈值
T=8*0.75=6 // 阈值更新:容量*加载因子

5 关于HashMap

5.1 HashMap如何实现put、get操作时间复杂度为O(1)~O(n)?

  1. 首先,对于数组的元素,如果知道index,那查找的复杂度就是O(1)级别
  2. 对于get操作,首先根据key计算出hash值,而这个hash值 执行操作hash&(n-1)就是它所在的index,在最好的情况下,该index只有一个节点且hash值与key的hash值相等,那么时间的复杂度就是O(1)。当该节点为链表或者红黑树时,时间复杂度会上升,但是由于HashMap的优化(链表长度、红黑树长度相对HashMap容量不会过长,过长会触发resize操作),所以 最坏的情况也就是O(n) ,可能还会小于这个值。【链表的查询时间复杂度是:O (n),红黑树是 O(logN),比O (n)更小
  3. 对于put操作,我们知道,数组插入元素的成本是高昂的,HashMap巧妙的 使用链表和红黑树代替了数组插入元素需要移动后续元素的消耗,这样在最好的情况下,插入一个元素,该index位置恰好没有元素的话,时间复杂度就是O(1),当该位置有元素且为链表或者红黑树的情况下,时间复杂度会上升,但是最坏的情况下也就是O(n)。

5.2 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树?

  1. 单节点转链表:当计算出来的index处有元素,且元素是单节点时,则该节点变为链表;
  2. 链表转红黑树有两个条件:
    1. 链表长度大于TREEIFY_THRESHOLD,默认阈值是8;
    2. HashMap长度大于64

5.3 HashMap初始化时为什么要给自定义的初始容量?

  1. 不指定初始容量时,HashMap底层数组的在第一次put值时,数组长度为默认初始长度即16,加载因子为0.75,扩容阈值为16*0.75=12;当元素数量大于12时,底层数组进行扩容,长度翻倍为32,扩容阈值翻倍为24,依次类推;
  2. 指定初始容量时,假设初始容量为C=1000。HashMap底层数组的在第一次put值时,数组长度初始化为 1024,扩容阈值为1024*0.75=768;当元素数量大于768时,底层数组进行扩容,长度和阈值同时翻倍。
  3. 因此,当HashMap元素足够多时,不指定初始容量要比指定初始容量进行更多次的扩容,扩容涉及数组拷贝、链表或红黑树重建,消耗更多性能。
  4. 根据要使用的HashMap大小确定初始容量,这也不是说为了避免扩容初始容量给的越大越好, 越大申请的内存就越大,如果你没有这么多数据去存,又会造成hash值过于离散,增加查询或修改的时间复杂度。

5.4 HashMap如何保证容量始终是2的幂?

HashMap使用方法tableSizeFor()来保证无论你给值是什么,返回的一定是2的幂

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

5.5 HashMap为何要保证容量始终是2的幂

  1. HashMap在定位元素在数组的index时,运算公式是 (n-1)&hash ,n为数组的长度。如果容量始终是2的次幂,例如 0000 0000 0000 0000 0000 0000 1000 0000,则n-1的二进制形式为:0000 0000 0000 0000 0000 0000 0111 1111 ,低位区一定是1,在进行 (n-1)&hash,hash低位区的0、1特征能够保留
  2. 因此,容量始终是2的幂,这样 下标index值的取值范围更广,减少hash碰撞

5.6 HashMap计算hash值

1、带着疑问
key的hashCode为什么右移16位后再进行异或运算?

2、关于 | & ^ 三种运算的特征说明

  • ^按位异或运算:位相同返回0,不同返回1;可推导出:任何数跟0异或返回任何数任何数跟1异或返回对应的取反
  • 异或运算能更好的保留各部分的特征,如果采用逻辑与&运算计算出来的值会向0靠拢(00得0,01得0,11得1 因此0的概率2/3),采用逻辑或|运算计算出来的值会向1靠拢 (00得0,01得1,11得1,因此1的概率为2/3)

3、hash()源码

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    //key.hashCode() ;hashCode是Object对象的一个native方法,由操作系统实现,跟内存地址存在某种映射关系

4、进入分析

5.6.1 key的hash值>>>16,为什么要这样做呢?

  1. h值右移16后,高16位都为0,这样h^(h>>>16)时,高16位的值不会有任何变化,但是低16位的值混杂了key的高16位的值,从而增加了hash值的复杂度,进一步减少了hash值一样的概率。
  2. 计算数组下标公式:(n-1)&hash,n-1的结果:高位趋于0;&运算的结果:高16位向0靠拢,hash的高位特征丢失
  3. 因此,如果我们不做hash值的移位和异或运算,那么在计算数组index时将丢失高区特征

简单点:

因为:(n-1)&hash中,hash的高位数将被数组长度的二进制码锁屏蔽,为确保hash的高位尽可能利用,就先对hash值先右移16位,再跟原hash值进行异或运算,同时保留高位和低位特征。

数组长度二进制码屏蔽是什么意思

数组长度的数据类型int转化为32位的二进制,因为长度值对比最大值(232位)总是比较小的,所以它的高位趋向0,与其他数进行&运算后,结果值的高位趋向0,那么其他数的高位特征就丢失了

下面用例子分析

### 计算hash
hashCode     					0000 0000 0101 0000 0000 0000 1111 1010
hashCode>>>16: 					0000 0000 0000 0000 0000 0000 0101 0000
hashCode^hashCode>>>16: 		0000 0000 0101 0000 0000 0000 0110 1010

hash=hashCode^hashCode>>>16 	0000 0000 0101 0000 0000 0000 0110 1010

### 计算index时:
(n-1) (假设n=16)            		0000 0000 0000 0000 0000 0000 0000 1111  
(n-1)&hash                  	0000 0000 0000 0000 0000 0000 0000 1010

仔细观察上文不难发现,高16位很有可能会被数组长度的二进制码锁屏蔽,
如果我们不做移位异或运算,那么在计算数组index时将丢失高区特征

2、HashMap源码分析

5.7 HashMap为什么是线程不安全的?

  1. 它没有任何的锁或者同步等多线程处理机制,无法控制并发下导致的线程冲突。
  2. 如果想要线程安全的使用基于hash表的map,可以使用ConcurrentHashMap,该实现get操作是无锁的,put操作也是分段锁,性能很好

6 get 过程分析

  1. 计算 key 的 hash 值,根据 hash 值找到对应数组下标: hash & (length-1)
  2. 判断数组该位置处的元素是否刚好就是我们要找的,如果不是,走第三步
  3. 判断该元素类型是否是 TreeNode,如果是,用红黑树的方法取数据,如果不是,走第四步
  4. 遍历链表,直到找到相等(==或equals)的 key

2、HashMap源码分析

参考资料:

  1. [良许-HashMap源码实现分析]:https://www.cnblogs.com/yychuyu/p/13357218.html

来源:https://www.cnblogs.com/knowledgeispower/p/17130618.html
本站部分图文来源于网络,如有侵权请联系删除。

未经允许不得转载:百木园 » 2、HashMap源码分析

相关推荐

  • 暂无文章

登录

注册

正在加载中...