本文共 6147 字，大约阅读时间需要 20 分钟。

Java8 HashMap集合解析

1.概要:hashMap作为面试常用考点经常被问道,所以需要多加了解,带着问题去思考才是最好的学习手段,在分析之前我先提几个问题

​ 1.HashMap的put流程？

​ 2.扩容机制？

​ 3.底层数据结构？

​ 4.默认容器大小和默认负载因子？

​ 5.什么时候转红黑树什么时候又退化成链表？

​ 6.线程安全吗？为什么不安全

2.首先了解一个类之前,我们先来分析类中有哪些属性

/** * 默认的初始容器大小16 必须是2的倍数(为什么是2的倍数？) */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** * 最大的容器数量 */static final int MAXIMUM_CAPACITY = 1 << 30;/** * 默认的负载因子 */static final float DEFAULT_LOAD_FACTOR = 0.75f;/** *  *树化阈值.hash冲突的节点数量超过8则转换成红黑树 为什么是8？ */static final int TREEIFY_THRESHOLD = 8;/** * 退化树成链表的阈值6 为什么是6 *  */static final int UNTREEIFY_THRESHOLD = 6;/** * * 最小树化容量,只有数量到达64才会进行树化转换 *  * */static final int MIN_TREEIFY_CAPACITY = 64;/** *  * 底层存储容器对象数组 *  * */transient Node
   
    [] table;/**  * 容器中的存放对象的数量  */transient int size;/**  *   *记录容器的修改次数  *  */transient int modCount;/**  *   *容器扩容的零界点  *  */int threshold;
   

1.put主流程

1.0 先创建一个实例

public HashMap() {   //这里就回答了问题4 默认负载因子0.75    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

1.1 首先根据key值进行hash算法的计算得出一个int类型常量值

static final int hash(Object key) {    int h;    //这里hash一次+位运算都是为了得到一个均匀的hash分布值    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node
   
    [] tab; Node
    
      p; int n, i;    //判断容器有没有初始化过没有则进行初始化()    if ((tab = table) == null || (n = tab.length) == 0)         //进行初始化容器        n = (tab = resize()).length;        //进行hash计算得到具体的数组下表    if ((p = tab[i = (n - 1) & hash]) == null)        //没有hash冲突则直接赋值        tab[i] = newNode(hash, key, value, null);    else {        Node
     
       e; K k;        //判断是hash冲突还是新值覆盖。这里也是为什么重写hashcode一定要重写equals的原因        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;            //判断是否是树节点        else if (p instanceof TreeNode)            e = ((TreeNode
      
       )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);                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        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;        }    }    //修改次数+1    ++modCount;    //判断是否需要扩容    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}
      
     
    
   

resize()方法解析:

final Node
   
    [] resize() {    Node
    
     [] oldTab = table;    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    //第二次调用put方法走着,也就是容器已经通过put初始化过一次了    if (oldCap > 0) {        //设定最大值        if (oldCap >= MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return oldTab;        }        //扩大两倍        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)                 //这个也扩大两倍用来作为下次扩容的判断条件            newThr = oldThr << 1; // double threshold    }    //如果你new HashMap给了初始化容量大小走这里    else if (oldThr > 0) // initial capacity was placed in threshold        newCap = oldThr;     //如果你new HashMap没有给初始化容量大小走这里    else {               // zero initial threshold signifies using defaults        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }    /如果你new HashMap给了初始化容量大小走这里。处理要将newThr重新计算    if (newThr == 0) {        float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    //得到与负载因子计算后的扩容数量大小    threshold = newThr;    @SuppressWarnings({"rawtypes","unchecked"})    //扩容        Node
     
      [] newTab = (Node
      
       [])new Node[newCap];    table = newTab;    //进行数据迁移重新hash    if (oldTab != null) {        for (int j = 0; j < oldCap; ++j) {            Node
       
         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
        
         )e).split(this, newTab, j, oldCap); else { // preserve order Node
         
           loHead = null, loTail = null; Node
          
            hiHead = null, hiTail = null; Node
           
             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;}
           
          
         
        
       
      
     
    
   

概括起来:

1.2 判断容器是否初始化没有则进行相应的初始化扩容

1.3 根据取模运行得到数组下标判断是否hash冲突,未冲突则填入值到容器

1.4 冲突了则判断key值是否一样，一样表示覆盖操作则进行value值的更新

1.5 key值不一样则说明发生了hash冲突,尾插法插入到链表当中,在此之前判断冲突节点是否超过8个并且容器中的节点数量超过64.满足条件则进行链表转红黑树

1.6 判断容器数量是否超过扩容值即>容器大小*负载因子 超过则进行扩容

好了现在来回答这些问题:

​ 1.HashMap的put流程？

​ 上面已经分析了

​ 2.扩容机制？

​ 扩容机制是通过判断容器中的元素数量size>容器中的总数量*负载因子的系数，超过了则重新new一个两倍与之前的数组,并进行数据迁移。

​ 3.底层数据结构？

​ 底层数据结构是一个Node对象的数组

​ 4.默认容器大小和默认负载因子？

​ 16和0.75

​ 5.什么时候转红黑树什么时候又退化成链表？

链表节点超过8个则转红黑树,小于6则退化成链表.为什么要8才转呢:

理想状态下也就是使用java默认提供的hash算法的前提下,冲突的概率呈现为泊松分布:

* 0:    0.60653066* 1:    0.30326533* 2:    0.07581633* 3:    0.01263606* 4:    0.00157952* 5:    0.00015795* 6:    0.00001316* 7:    0.00000094* 8:    0.00000006

所以可以看出8的概率已经很低了。如果频繁超过8个说明你自己改写了对象的hash算法导致冲突概率加大

为什么退化为链表的阈值是6

上面说到，当链表长度达到阈值8的时候会转为红黑树，但是红黑树退化为链表的阈值却是6，为什么不是小于8就退化呢？比如说7的时候就退化，偏偏要小于或等于6？

主要是一个过渡，避免链表和红黑树之间频繁的转换。如果阈值是7的话，删除一个元素红黑树就必须退化为链表，增加一个元素就必须树化，来回不断的转换结构无疑会降低性能，所以阈值才不设置的那么临界。

​ 6.线程安全吗？为什么不安全

​ 不安全,并发操作下没加锁.对资源的修改都是不安全的。比如并发put

转载地址：http://nmkji.baihongyu.com/