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<K,V>[] 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<K,V>[] tab; Node<K,V> 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<K,V> 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<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);
                    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<K,V>[] resize() {
    Node<K,V>[] 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //进行数据迁移重新hash
    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;
}

概括起来:

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