day24–Java集合07


Java集合07

14.HashMap底层机制

hashMap底层机制08201904

  1. (k,v)是一个Node,实现了Map.Entry<K,V>,查看HashMap的源码可以看到
  2. jdk7.0 的HashMap底层实现[数组+链表],jdk8.0底层[数组+链表+红黑树]

14.1HashMap扩容机制(和HashSet完全相同)

详见10.2HashSet的底层扩容机制

  1. HashMap底层维护了Node类型的数组table,默认为null
  2. 当创建对象时,将加载因子(loadfactor)初始化为0.75
  3. 当添加key-value时,通过key的哈希值得到在table的索引。然后判断该索引处是否有元素,如果没有元素则直接添加;如果该索引处有元素,继续判断该元素的key是否和准备加入的key相等。若相等,则直接替换value;若不相等,需要判断是树结构还是链表结构,作出相应处理。如果添加是发现容量还不够,则需要扩容。
  4. 第一次添加,则需要扩容table容量为16,临界值(threshold)为(0.75*16=)12
  5. 以后再扩容,则需要扩容为table的容量为之前的两倍,临界值也为原来的两倍,即24.以此类推
  6. 在Java8中,如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认为8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)。

例子:

package li.map.hashmap;

import java.util.HashMap;

@SuppressWarnings("all")
public class HashMapSource {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("java",10);//ok
        map.put("php",10);//ok
        map.put("java",20);//替换value

        System.out.println(map);//{java=20, php=10}
    }
}

执行过程如下:

  1. 执行构造器 newHashMap();

    初始化加载因子 loadfactor = 0.75

    HashMap$Node[ ] = null

  2. 执行put(),调用hash()方法计算key的值

    可以看到,如果传入的参数key为空的话,就返回0;如果不为空,则求出 key 的 hashCode 值,然后将hashCode 值右移16位并且与原来的 hashCode 值进行 ^(按位异或) 操作,并返回这个哈希值

public V put(K key, V value) {//K="java" value= 10
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3.调用putVal方法:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {//
    Node<K,V>[] tab; Node<K,V> p; int n, i;//定义了辅助变量
    //这里定义的tablejiushi HashMap的一个数组,类型是Node[]数组
    if ((tab = table) == null || (n = tab.length) == 0)//if 语句表示,如果当前table是null,或者大小=0,则进行第一次扩容,扩容到16个空间
        n = (tab = resize()).length;//如果为第一次扩容,此时初始的table已经变成容量为16的数组
    
    /*
    1.根据key,得到hash 去计算key应该放到table表的哪个索引位置,并且把这个未知的对象赋给赋值变量p  	     2.再判断p是否为空 
    	2.1如果p为空,表示该位置还没存放元素,就创建一个Node (key="java", value=PRESENT)并把数         据放在该位置--table[i]=newNode(hash, key, value, null);
    */
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    
    else {
      //2.2如果不为空,就会进入else语句
        Node<K,V> e; K k;//定义辅助变量
       /*这里的p指向当前索引所在的对象(由上面的p = tab[i = (n - 1) & hash])计算出索引位置),如          果当前索引位置对应链表的第一个元素的哈希值 和 准备添加的key的哈希值 一样,
       并且 满足下面两个条件之一:
        1.准备加入的key 和 p指向的Node节点 的key 是同一个对象:(k = p.key) == key
        2.p指向的Node节点的key 的equals()和准备加入的key比较后相同 并且key不等于null:(key !=               null && key.equals(k))
       就不加入  只是换原来的元素(不插入新结点只是替换值)
        */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        //再判断p是否是一颗红黑树
        //如果是红黑树,就调用putTreeVal()方法来进行添加
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        else { //如果table对应索引位置已经是一个链表了,就使用for循环依次比较
               //(1)依次和该链表的每个元素都比较后 都不相同,就则将数据加入到该链表的最后
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {//先赋值再判断
                    p.next = newNode(hash, key, value, null);
                    //注意:把元素添加到链表之后立即 判断该链表是否已经达到8个节点,如果已经达到则                         //调用 treeifyBin()对当前链表进行树化(转成红黑树)
                    //在转成红黑树时 还要进行一个判断:
                    //如果该table数组的为空或者大小小于64,则对table数组进行扩容
                    //如果上面条件不成立,即数组大小大于等于64且链表数量达到8个,就转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                 //(2)如果在依次和该链表的每个元素比较的过程中发现如果有相同情况,就直接break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;//在上面for循环条件已经把p.next赋值给e了,这里e又赋值给p 其实就是将p指针指                         //向p.next,然后再进行新一轮的判断,如此循环,直到有满足上面if语句的条件为止
            }
     }
        
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;//替换,key对应value
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    
    ++modCount;//每增加一个Node,就size++
    if (++size > threshold)//当使用的容量 > 临界值时,就扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

PS:关于树化

        for (int binCount = 0; ; ++binCount) {
            //(1)依次和该链表的每个元素都比较后 都不相同,就则将数据加入到该链表的最后
                if ((e = p.next) == null) {//先赋值再判断
                    p.next = newNode(hash, key, value, null);
                    
                    //注意:把元素添加到链表之后立即 判断该链表是否已经达到8个节点,如果已经达到则                         //调用 treeifyBin()对当前链表进行树化(转成红黑树)
                    //在转成红黑树时 还要进行一个判断:
                    //如果该table数组的为空或者大小小于64,则对table数组进行扩容
                    //如果上面条件不成立,即数组大小大于等于64且链表数量达到8个,就转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                 //(2)如果在依次和该链表的每个元素比较的过程中发现如果有相同情况,就直接break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;//在上面for循环条件已经把p.next赋值给e了,这里e又赋值给p 其实就是将p指针指                         //向p.next,然后再进行新一轮的判断,如此循环,直到有满足上面if语句的条件为止
            }

遍历过程中p从第一个节点遍历到最后一个节点,但由于binCount是从0开始计数,所以在做树化判断时binCount

的值等于 链表长度 – 1(注意此时的链表长度没有算新插入的节点)

判断条件为 binCount >= TREEIFY_THRESHOLD – 1 ==> binCount+1(链表长度) >= TREEIFY_THRESHOLD

但此时链表新插入了一个节点

 p.next = newNode(hash, key, value, null);

所以链表树化的那一刻,它的真实长度应该时binCount+1+1 => 链表长度>TREEIFY_THRESHOLD(8)

即:

链表长度大于8时,treeifyBin()方法被调用

(在做树化判断时,链表长度 = binCount+1(从零计数)+1(新插入节点) = bincount +2)

(判断条件: (bincount >= 8-1) => (bincount>=7) => (bincount+2>=9) => (链表长度>=9) 长度是整数 大于等于9也就是大于8)

ps:剪枝—>如果有链表树化之后,树中的节点经过删除之后越来越少,当元素个数减少到一定程度,树会转变为了链表

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/281895.html

(0)
上一篇 2022年8月23日
下一篇 2022年8月24日

相关推荐

发表回复

登录后才能评论