(SUB)java集合类-map_hashmap转换为红黑树的条件

目录

hashmap

hashmap转红黑树条件：

JDK 1.8 的 hash 方法

类的属性：

源码分析

构造方法

put 方法

resize 方法

tablesizefor（）方法：

ConcurrentHashMap

hashmap

HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一。

JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。

hashmap转红黑树条件：

JDK1.8 之后 HashMap 的组成多了红黑树，在满足下面两个条件之后，会执行链表转红黑树操作，以此来加快搜索速度。

• 链表长度大于阈值（默认为 8）
• HashMap 数组长度超过 64（当长度小于64时，认为扩容要比转成树好）

JDK 1.8 的 hash 方法

static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

类的属性：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table;
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;
    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
}

源码分析

构造方法

HashMap 中有四个构造方法，它们分别如下：

 
 
    // 默认构造函数。
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
     }
 
     // 包含另一个“Map”的构造函数
     public HashMap(Map<? extends K, ? extends V> m) {
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         putMapEntries(m, false);//下面会分析到这个方法
     }
 
     // 指定“容量大小”的构造函数
     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;
         this.threshold = tableSizeFor(initialCapacity);
     }

putMapEntries 方法：

如何设置一个合理的初始化容量
       当我们使用HashMap(int initialCapacity)来初始化容量的时候，jdk会默认帮我们计算一个相对合理的值当做初始容量。当HashMap的容量值超过了临界值（threshold)时就会扩容，threshold = HashMap的容量值*0.75，比如初始化容量为8的HashMap当大小达到8*0.75=6时将会扩容到16。当我们设置HashMap的初始化容量是遵循expectedSize /0.75+1，比如expectedSize是6时 6/0.75+1=9，此时jdk处理后会被设置成16，大大降低了HashMap被扩容的几率。
            float ft = ((float)s / loadFactor) + 1.0F;

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化，s为m的实际元素个数，
 
 
如何设置一个合理的初始化容量
       当我们使用HashMap(int initialCapacity)来初始化容量的时候，jdk会默认帮我们计算一个相对合理的值当做初始容量。当HashMap的容量值超过了临界值（threshold)时就会扩容，threshold = HashMap的容量值*0.75，比如初始化容量为8的HashMap当大小达到8*0.75=6时将会扩容到16。当我们设置HashMap的初始化容量是遵循expectedSize /0.75+1，比如expectedSize是6时 6/0.75+1=9，此时jdk处理后会被设置成16，大大降低了HashMap被扩容的几率。//
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

put 方法

resize 方法

参考

HashMap的扩容机制(JDK1.8)_1.8hashmap扩容如何计算下标_绅士jiejie的博客-CSDN博客

注：当阈值存在而容量为0表示容器刚初始化，且此时用户制定了初始容量HashMap(int initialCapacity, float loadFactor)，构造函数会调用tablesizefor（）方法 得到初始阈值（该阈值其实为后续的新初始容量非真实阈值）。

具体容量初始化位置在后续的第一次put() ——>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;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

--->resize()的该分支，进行初始化新容量

        //如果老数组的长度oldCap并没有大于0，说明还没做初始化操作，但是这时它的旧阈值oldThr却大于0，这说明了构造HashMap时传入了初始容量，而HashMap会根据传入的初始容量来定义阈值，这里给出部分代码参考:this.threshold = tableSizeFor(initialCapacity)，而数组的初始化其实是在put()方法里才完成的，这也就能理解为什么有阈值而数组却还没初始化了
        else if (oldThr > 0)
            //那就把阈值值赋值给代表新数组长度的变量newCap
            newCap = oldThr;

tablesizefor（）方法：

由此可以看到，当在实例化HashMap实例时，如果给定了initialCapacity，由于HashMap的capacity都是2的幂，因此这个方法用于找到大于等于initialCapacity的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数）。  

// 这个方法返回大于输入参数且最接近的2的整数次幂的数
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;
}

为啥hash的数组容量非得要2的n次方呢？因为Hashmap进行hash后取数组坐标的时候是这样运算的。

1. static int indexFor(int h, int length) {

2. return h & (length-1);

3. }

如果length为非2的n次方。比如是3，那么3-1的二进制位0010，其hash后的坐标除了table[2]外，其他的都hash到table[0]上面了。

也就是说，如果非2的n次方的话，hash定位的时候冲突就会成倍增长。

ConcurrentHashMap

https://blog.csdn.net/aqin1012/article/details/131403059

源码分析：

putVal

/*
putVal(K key, V value, boolean onlyIfAbsent)方法干的工作如下：
1、检查key/value是否为空，如果为空，则抛异常，否则进行2
2、进入for死循环，进行3
3、检查table是否初始化了，如果没有，则调用initTable()进行初始化然后进行 2，否则进行4
4、根据key的hash值计算出其应该在table中储存的位置i，取出table[i]的节点用f表示。
    根据f的不同有如下三种情况：
    1）如果table[i]==null(即该位置的节点为空，没有发生碰撞)，则利用CAS操作直接存储在该位置，如果CAS操作成功则退出死循环。
    2）如果table[i]!=null(即该位置已经有其它节点，发生碰撞)，碰撞处理也有两种情况
        2.1）检查table[i]的节点的hash是否等于MOVED，如果等于，则检测到正在扩容，则帮助其扩容
        2.2）说明table[i]的节点的hash值不等于MOVED，
             如果table[i]为链表节点，则将此节点插入链表中即可
             如果table[i]为树节点，则将此节点插入树中即可。
        插入成功后，进行 5
5、如果table[i]的节点是链表节点，则检查table的第i个位置的链表是否需要转化为数，如果需要则调用treeifyBin函数进行转化
*/

initTable

/** * Initializes table, using the size recorded in sizeCtl. */
    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)//如果sizeCtl为负数，则说明已经有其它线程正在进行扩容，即正在初始化或初始化完成
                Thread.yield(); // lost initialization race; just spin
                //如果CAS成功，则表示正在初始化，设置为 -1，否则说明其它线程已经对其正在初始化或是已经初始化完毕
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {//再一次检查确认是否还没有初始化
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);//即sc = 0.75n。
                    }
                } finally {
                    sizeCtl = sc;//sizeCtl = 0.75*Capacity,为扩容门限
                }
                break;
            }
        }
        return tab;
    }

treeifyBin

/* *链表转树：将将数组tab的第index位置的链表转化为 树 */
    private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)// 容量<64，则table两倍扩容，不转树了
                tryPresize(n << 1);
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                synchronized (b) { // 读写锁 
                    if (tabAt(tab, index) == b) {
                        TreeNode<K,V> hd = null, tl = null;
                        for (Node<K,V> e = b; e != null; e = e.next) {
                            TreeNode<K,V> p =
                                new TreeNode<K,V>(e.hash, e.key, e.val,
                                                  null, null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

检查下table的长度是否大于等于MIN_TREEIFY_CAPACITY（64），如果不大于，则调用tryPresize方法将table两倍扩容就可以了，就不将链表转化为树了。如果大于，则就将table[i]的链表转化为树。

get

/* 功能：根据key在Map中找出其对应的value，如果不存在key，则返回null， 其中key不允许为null，否则抛异常 */
    public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());//两次hash计算出hash值
        if ((tab = table) != null && (n = tab.length) > 0 &&//table不能为null，是吧
            (e = tabAt(tab, (n - 1) & h)) != null) {//table[i]不能为空，是吧
            if ((eh = e.hash) == h) {//检查头结点
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)//table[i]为一颗树
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {//链表，遍历寻找即可
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

1、根据key调用spread计算hash值；并根据计算出来的hash值计算出该key在table出现的位置i.

2、检查table是否为空；如果为空，返回null，否则进行3

3、检查table[i]处桶位不为空；如果为空，则返回null，否则进行4

4、先检查table[i]的头结点的key是否满足条件，是则返回头结点的value；否则分别根据树、链表查询。

sumCount

    final long sumCount() {
        ConcurrentHashMap.CounterCell[] cs = this.counterCells;
        long sum = this.baseCount;
        if (cs != null) {
            ConcurrentHashMap.CounterCell[] var4 = cs;
            int var5 = cs.length;
 
            for(int var6 = 0; var6 < var5; ++var6) {
                ConcurrentHashMap.CounterCell c = var4[var6];
                if (c != null) {
                    sum += c.value;
                }
            }
        }
 
        return sum;
    }
其中ConcurrentHashMap.CounterCell[]数组（this.counterCells）表示竞争时，每个线程追加元素的个数（每个线程的计数），若不存在竞争则直接在baseCount上计数

(十一) 深度分析ConcurrentHashMap中的并发扩容机制_concurrenthashmap扩容_跟着Mic学架构的博客-CSDN博客