美文网首页
JDK1.8HashMap源码分析

JDK1.8HashMap源码分析

作者: 不给起这个名字 | 来源:发表于2020-01-15 16:41 被阅读0次

    HashMap源码分析

    分析源码之前,先了解一下HashMap的结构,JDK1.7之前HashMap是通过数组结构+单向链表的结构存储的 (Node<K,V>[ ]),JDK1.8加入了数组结构+单向链表+红黑数 (当链表长度达到8时,就会采用红黑树来存储)
    通过Node<K,V>对象(可实现链表结构的对象)来封装map属性(hash,k,v,next)
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;  // 当前元素key的hash值
            final K key;    // 当前元素key值
            V value;        // 当前元素的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;
            }
    ......
        }
    
    HashMap的存储如下图,默认会初始化一个Entry<K,V>[] tab = new Node[16]大小为16的entry数组,所以数组有16个index索引位置(0-15),元素存放到哪个索引是通过key的hash值%数组长度-1(key的hash%15)计算出来的,当我们map.put("a","97");时,假设a的hash值%数组长度-1计算出来的结果为1(假设结果为1),那么这个元素就会被封装成Entry对象(JDK1.8实现类为上面的Node)存放到数组index为1的索引上
    image.png
    那么问题来了,如果元素索引的索引位置一样,是如何处理的,比如map.put("b","100"); key为b的索引计算出来也是1,那么是如何存放的?(这就是HashMap的哈希冲突问题)
    通过链表存储方式解决哈希冲突问题,这时会先生成"b","100"的entry对象(b),然后index下的a对象赋值的a.next=b (新的元素加入到链表最后一个位置)
    image.png
    以上就是HashMap通过数组+链表(由entry对象组成)的方式存储元素
    当获取元素时,比如map.get("a"),会计算出a的index为1,然后找到这个位置的entry对象,通过对比key是否相同,如果不相同,则获取entry.next的key继续比较,直到找出这个key对应的entry
    比如上面的例子存储了a和b,那么map.get("a")时,获取到index为1的entry为b对象,此时entry.key ==b !=a,就会拿entry.next的entry对象继续比较,发现entry.next.key==a,那么就返回entry.next.value

    写个查询的伪代码来理解

    for(Entry<K,V> e =tab[1]; e!=null; e = e.next){
        if(e.getKey()=="a"){
          return e.getValue();
        }
      return null;
    }
    
    HashMap通过entry[]数组,存储在index下的entry通过java对象的引用(next实现链表结构),来实现于存放了多个元素
    分析HashMap的无参构造方法
    public HashMap() {
            
            transient Node<K,V>[] table;  //这个HashMap的存储容器  Node是entry的实现
            static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 对扩容大小进行计算
            int threshold; // 当元素size大于threshold才进行扩容
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    

    HashMap的无参构造方法只设置了负载因子为0.75(后面讲到作用),没有对table进行任何处理,HashMap无参构造方法创建map后,table的初始化是在第一次put时进行的

    分析HashMap的put方法
    // put方法
    public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    // 对key进行hash计算
    static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    
    // 执行添加元素操作
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            // tab是map容器, p当前key计算出index下的node节点,n是容器数组的大小,i是当前key计算出来的index
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            // 判断当前容器是否为null或者容量大小为0
            if ((tab = table) == null || (n = tab.length) == 0)
                // 对map容量进行初始化(第一次扩容到16)  (扩容)
                n = (tab = resize()).length;
            // (n - 1) & hash,15&hash,奇数计算可减少index重复率,是为了减少hash冲突
            // 如果当前index下没有node,直接封装当前key的node对象存放到tab[i]下
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                // 如果是同一个key,就修改value
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)    // 这里使用了红黑树,后面再分析
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                  // 不是同一个key
                    for (int binCount = 0; ; ++binCount) {  //相当于while循环
                        if ((e = p.next) == null) {
                        // 将当前key的node节点关联对应index位置的node的next节点下
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) 
    // TREEIFY_THRESHOLD = 8,当循环8次时,说明链表长度达到了8,这时使用红黑树存储   后面再分析红黑树
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    
    HashMap的put方法,第一次put时会初始化容器大小为16,put时,先计算出key的hash,然后通过(tab.length-1)&hash计算出这个元素将要存放的index位置,然后找出index下的node节点,如果node.key和当前key相同,就修改value值,如果不同就生成这个key的node节点对象,然后将这个节点存入链表的最后一个位置(index下的node节点遍历判断node.next==null,就可找出最后一个节点,然后把最后一个节点赋值next=需要增加的key的node节点)

    分析HashMap的get方法
    public V get(Object key) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    
    final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            // 如果map容器为为null或size为0,直接返回null
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                // 如果是第一个节点,返回first
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                      // 遍历链表节点找出对应key的node          从first的node开始找,通过node.next.next.....进行查询
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }
    
    HashMap的get方法会先计算出需要查询key的index位置,找出这个链表,从第一个node节点开始遍历 node.next.next.....找出对应的node节点然后得到node.value返回结果

    分析HashMap的remove方法
    remove方法这里不就粘贴源码了,是先通过数组的方式找出链表(由多个node节点对象组成),然后遍历找到需要删除的node,这个需要删除node的上一个node关联的next赋值为需要删除node的node.next(相当于node.prev.next = node.next) (类似于上一遍讲到的LinkedList元素的删除,区别在于map用的是单向链表,没有prev节点,需要遍历时用变量存放prev节点)

    只要理解我上面画的HashMap存放元素的结构,HashMap的原理就好理解了,通过数组来存放链表(由node对象通过属性引用next组成链表),链表中的每个node节点存储key和value


    分析HashMap的扩容

    通过java.util.HashMap#resize方法进行扩容操作的,分析new HashMap(),第一次put进行扩容处理以及之后是如何扩容的
    final Node<K,V>[] resize() {
            
            Node<K,V>[] oldTab = table;
            // 第一次put时,oldCap为0
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
           // threshold为0,执行完第一次扩容后,threshold=12,看下面的代码
            int oldThr = threshold;
            int newCap, newThr = 0;
          // 第二次扩容  当if (++size > threshold) 进行扩容
            if (oldCap > 0) {
                // MAXIMUM_CAPACITY = 1 << 30;,正常来说都不会大于2的30次方
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                // 第二次进来当++size > threshold 也就是 threshold= 12 当size=12时,就会进行第二次扩容
                 // newCap = oldCap << 1  新的容量为旧容器的的2倍    newCap = 16*2 = 32
                 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    // newThr  为原来的2倍   12*2 = 24  也就是threshold为24,下一次扩容是++size>24时
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            // 容器为0时,第一次扩容,会走到这里
            else {               // DEFAULT_INITIAL_CAPACITY = 1 << 4;  2的4次方=16
                newCap = DEFAULT_INITIAL_CAPACITY;  // 默认容量设置为16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  16*0.75 = 12;
            }
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;   // 第一次扩容, threshold为12
            // 进行扩容操作,就是生成新的Node<K,V>[],然后重新计算旧Node<K,V>[]中元素的index,放到新Node<K,V>[]中
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            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)
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            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;
        }
    
    扩容分析
    首先需要源码上的几个属性的作用

    static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子,用于计算扩容的阈值,当容器的size达到多少时进行扩容
    nt threshold; //扩容的阈值, 当size达到这个值是,会进行扩容操作,当++size>threshold时

    当new HashMap()初始化容器为空,第一次put添加元素时,会将容器扩容到默认大小16,然后threshold = 160.75 = 12。当size达到threshold(12)时,会进行扩容,扩容大小为原来的2倍,也就是162=32,threshold = 32*0.75 = 24。之后每次size达到threshold时,都会扩容2倍。
    扩容时会生成一个新的Node<K,V>[]数组,循环遍历oldTab,重新oldTab每个元素的index,然后存放到新的数组中
    为什么负载因子大小是0.75?
    这是一个经过多次测试得到的合理值,能让hash冲突减小,并且index空间利用率高的一个合理的值。
    假设将负载因子设置为1(比0.75大),这时容器第二次扩容需要达到size=16时才进行扩容(之后需要达到更大才扩容),这就使得hash碰撞冲突的概率变大,因为index位置不变,需要添加更多的元素才进行扩容(可以理解成原来12个元素可以有16个位置选择,现在16个元素也只有16个位置选择),hash碰撞冲突概率就变大了。但是空间的利用率也提高了
    再假设将负载因子设置为0.5(比0.75小),这时容器第二次扩容只需要达到16*0.5=8时就进行扩容了,虽然hash碰撞冲突概率变小了,但扩容更加频繁了(扩容时会降低效率)。但是空间的利用率也降低了(可理解成8个人占16个位置)。
    负载因子大小是0.75是一个减少hash冲突,增大空间利用率的合理值。
    负载因子越大,扩容次数减少,空间利用率提高,但hash冲突的概率也变大
    负载因子越小,扩容次数增加,hash冲突的概率减小,但空间利用率下降

    JDK8HashMap中的红黑树分析

    上面提到的结构都是数组+链表,没到体现到红黑树,那么HashMap在什么情况下会使用红黑树来存放元素?
    当链表长度>8,并且数组长度>64的情况下,就会将整个链表转换成红黑树结构,如果链表长度>8,但是数组长度小于64,那么只对数组进行扩容
    当红黑树元素小于6时,又会把红黑树变回成链表

    下面分析put时,当hash冲突过大,index中链表长度大于8时,并且数组长度>64,会把链表变成红黑树结构的验证

    public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    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)
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                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) {
                            p.next = newNode(hash, key, value, null);
    // TREEIFY_THRESHOLD  = 8。当循环8次,p.next都不为空,表示链表长度大于8,会进入treeifyBin(tab, hash)方法
                            if (binCount >= TREEIFY_THRESHOLD - 1) 
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
       ......
            }
     ......
        }
    
    final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
        // MIN_TREEIFY_CAPACITY = 64  当数组长度小于64时,只进行resize()扩容。
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)   
                resize();
      // 否则,当数组长度大于64
            else if ((e = tab[index = (n - 1) & hash]) != null) {
              // 把链表node转成TreeNode类型(Map.Node的子类),里面封装了红黑树的属性
                TreeNode<K,V> hd = null, tl = null;
                do {
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else {
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                  // 把链表变成红黑树
                    hd.treeify(tab);
            }
        }
    
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;
            TreeNode(int hash, K key, V val, Node<K,V> next) {
                super(hash, key, val, next);
            }
    
            /**
             * Returns root of tree containing this node.
             */
            final TreeNode<K,V> root() {
                for (TreeNode<K,V> r = this, p;;) {
                    if ((p = r.parent) == null)
                        return r;
                    r = p;
                }
            }
    

    扩容时会重新计算index,如果index的链表长度小于6,又会把之前红黑树结构的元素变回链表

    resize() 方法的
    else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    

    问题记录:

    map的hash冲突如何解决(也就是数组一个index只能存一个值,如何使index下存储多个元素)?
    通过用数组来存储链表的方式解决,看上面的map存储结构
    计算index时为什么要length-1(hash值%数组长度-1)
    因为扩容都是*2计算容量大小的,-1能使值变成奇数,%奇数能减少index的重复(减少hash冲突)
    Java8的HashMap为什么需要使用数组+链表+红黑树
    如果index冲突过多,会导致单个链表过长,这时候查询效率会变慢,时间复杂度为o(n),如果链表长度>8的情况下,HashMap会使用红黑树来存放,,提高查询效率。查询的时间复杂度o(log n)
    jdk8对jdk7的hashMap做了哪些改进?
    1.jdk8在jdk7的数组+链表结构上添加了红黑树
    2.jdk7在多线程的情况下,扩容可能会出现死循环(因为采用的是头插法(将最新的节点做为frist节点)),jdk8解决了扩容造成的死循环问题,使用的是尾插法(将最新的节点存入链表的最尾部)
    负载因子的作用?
    计算扩容的阈值,当size达到阈值时就会进行扩容
    什么时候会对容器进行扩容?每次扩容多少
    1.当元素的size大于扩容阈值threshold时会进行扩容,扩容到原来容量的2倍
    2.当数组中某个index下的链表长度大于8,并且数组长度小于64时,会进行扩容(扩容到原来容量的2倍)
    什么情况下会把链表转成红黑树?什么情况下又会把红黑树变回链表?
    当链表长度大于8,并且数组长度大于64时,会将当前链表变成红黑树
    当红黑树中元素的个数少于6时,会把红黑树转变回链表(为什么不是8?是为了防止频繁转换)

    https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
    链表可通过二分查询法来提高查询效率(但必须是有序链表)
    hashMap通过红黑树来提高查询效率

    二叉搜索树

    二叉树节点的左子树只包含小于当前根节点的数,节点的右子树只包含大于当前根节点的数
    二叉树的每个节点只会出现两个分支,所以叫做二叉树
    会以第一个插入的节点为根节点,如图第一个插入5


    image.png

    如果全是正整数,第一个插入0就会使得树的深度过深,造成查询的时间复杂度为O(n)


    image.png

    平衡二叉树

    基本特点与二叉树一样,但是不会以第一个插入的数做为根节点,会计算出平衡点的数然后通过旋转的方式将这个数做为根节点。如下图,第一个插入0,旋转前与二叉树一致,旋转后根节点变为了1,使树的结构达到平衡,减小树的深度
    平衡条件必须满足(所有结点的左右子树高度差不超过1)


    旋转前
    旋转后
    平衡二叉树缺点:过度的追求平衡(平衡条件必须满足(所有结点的左右子树高度差不超过1)),如果插入或删除频繁,那么就会频繁出现reblance(旋转达到平衡为止),会降低效率

    红黑树

    根节点一定是为黑色
    每个节点只有红色或黑色两种颜色
    红色节点的两个子节点一定都是为黑色
    不允许两红色节点相连,如果相连就需要进行变色或左旋转或右旋转重排
    默认情况下添加的节点是为红色节点


    image.png

    红黑树是在平衡二叉树的基础上做了优化,保留了平衡二叉树所有的优点,但红黑树不是高度平衡的,算是一种折中,插入最多旋转两次,删除最多旋转三次

    应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL(平衡二叉树)还是较优于红黑树
    所以对于搜索,插入,删除操作较多的情况下,我们就用红黑树

    JDK1.7ConcurrentHashMap

    HashMap是不安全的,HashTable安全但效率低。如果在多线程并发情况,就使用ConcurrentHashMap
    JDK1.7ConcurrentHashMap是通过segment分段锁来实现安全的,ConcurrentHashMap分成16个segment,每个segment都实现了ReentrantLock,segment相当一个HashMap。里面存放HashEntry[] (数组+链表)
    JDK1.7ConcurrentHashMap的最大并发为16,这16个线程分别访问不同的segment
    在segment加锁时,所有读线程是不会受到阻塞的
    当获取size时size操作就是遍历了两次所有的Segments,每次记录Segment的modCount值,然后将两次的modCount进行比较,如果相同,则表示期间没有发生过写入操作,就将原先遍历的结果返回,如果不相同,则把这个过程再重复做一次,如果再不相同,则就需要将所有的Segment都锁住,然后一个一个遍历了
    可以理解成ConcurrentHashMap里面有16个HashMap,每个HashMap都有自己的ReentrantLock锁
    image.png

    JDK1.8ConcurrentHashMap

    JDK1.8ConcurrentHashMap,变回了HashMap的结构(数组+链表+红黑树),去掉了segment分段锁,使用CAS无锁机制加Synchronized上锁
    当put时,如果当前key所存放的index位置没有节点,直接把节点添加到数组,添加时会使用CAS来保证线程安全
    for (Node<K,V>[] tab = table;;) {
                Node<K,V> f; int n, i, fh;
                if (tab == null || (n = tab.length) == 0)
                    tab = initTable();
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                    if (casTabAt(tab, i, null,
                                 new Node<K,V>(hash, key, value, null)))    //使用CAS锁添加节点
                        break;                   // no lock when adding to empty bin
                }
    
    当put时,如果当前key所存放的index有Hash冲突的情况(已经存在节点),则直接使用synchronized锁住当前链表
    Node<K,V> f
    synchronized (f) {
                        if (tabAt(tab, i) == f) {
                            if (fh >= 0) {
                                binCount = 1;
                                for (Node<K,V> e = f;; ++binCount) {
                                    K ek;
                                    if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                         (ek != null && key.equals(ek)))) {
                                        oldVal = e.val;
                                        if (!onlyIfAbsent)
                                            e.val = value;
                                        break;
                                    }
    ......
    
    JDK1.8ConcurrentHashMap使用更细粒度的锁(锁数组index下的链表,1.7是锁整个数组),put使得效率更高,而且加入了红黑树,查询效率也提高

    相关文章

      网友评论

          本文标题:JDK1.8HashMap源码分析

          本文链接:https://www.haomeiwen.com/subject/dpqbactx.html