关于java:彻底拿下HashMap面试问题

45次阅读

共计 12334 个字符，预计需要花费 31 分钟才能阅读完成。

本文目录

  • HashMap 的设计思维

    • HashMap 的底层构造
    • 为什么不一开始就应用 HashMap 构造
    • 为什么 Map 中的节点超过 8 个时才转换成红黑树

  • 为什么 HashMap 不是线程平安的

    - [同时 put 碰撞导致数据失落](# 同时 put 碰撞导致数据失落)
- [扩容期间取出的值不精确](# 扩容期间取出的值不精确)

  • HashMap 在 java7 和 java8 中的区别

     - [底层数据结构比照](# 底层数据结构比照)
 - [插入方式比照](# 插入方式比照)
 - [扩容形式比照](# 扩容形式比照)

  • ConcurrentHashMap 在 java7 和 java8 中的区别

     - [数据结构](# 数据结构)
 - [并发水平](# 并发水平)
 - [遇到 Hash 碰撞](# 遇到 Hash 碰撞)

HashMap 的设计思维

HashMap 的底层构造

本文次要是解说 jdk1.8 中的 HashMap 源码，会对 jdk1.7 中的 HashMap 做一些简略的解说用来和 jdk1.8 中的 HashMap 进行比照。

咱们先通过下图来了解 HashMap 的底层构造：

首先咱们通过下面的内容咱们能够看到 HashMap 构造都是这样一个特点：最开始 Map 时空的，而后往里面放元素
时会计算 hash 值，计算 hash 值之后，第一个 value 值会占用一个桶（也就是槽点），当前再来雷同 hash 值的 value 那么便会用链表的模式在该槽点后持续延长
这就是拉链法。

当链表的长度大于或者等于阙值的（默认是 8）的时候，并且同时还满足以后 HashMap 的容量大于或等于 MIN_TREEIFY_CAPACITY(默认 64)的要求，就会把链表转成
红黑树结构，如果后续因为删除或者其它起因调整了大小，当红黑树的节点小于或等于 6 个当前，又会复原链表构造。

为什么不一开始就应用 HashMap 构造

官网给出的解释是：

Because TreeNodes are about twice the size of regular nodes, 
we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD).
 And when they become too small (due to removal or resizing) they 
are converted back to plain bins.

翻译就是：因为 TreeNodes 的大小大概是一般 Node 节点的两倍，
所以只有在节点足够多的状况下才会把 Nodes 节点转换成 TreeNodes 节点，
是否足够多又由 TREEIFY_THRESHOLD 决定，而当桶中的节点的数量因为移除或者调整大小变少后，
它们又会被转换回一般的链表构造以节俭空间。

通过源码中得悉，当链表长度达到 8 就转成红黑树结构，当树节点小于等于 6 时就转换回去，此处体现了工夫和空间的均衡思维。

为什么 Map 中的节点超过 8 个时才转换成红黑树

这个问题官网给的解释是：

In usages with well-distributed user hashCodes, tree bins are rarely used.  Ideally, 
under random hashCodes, the frequency of nodes in bins follows a Poisson distribution 
(http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 
on average for the default resizing threshold of 0.75, although with a large variance 
because of resizing granularity. Ignoring variance, the expected occurrences of list 
size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
      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
      more: less than 1 in ten million

下面的意思是：在应用散布良好的用户的 hashCodes 时，很少应用红黑树结构，因为在现实状况下，链表的节点频率遵循泊松散布（意思就是链表各个长度的命中率顺次递加），当命中第 8 次的时候，
链表的长度是 8，此时的概率仅为 0.00000006，小于千万分之一。

然而，HashMap 中决定某一个元素落到哪一个桶中，是和某个对象的 hashCode 无关的，如果咱们本人定义一个极其不平均的 hashCode，例如：

public int hashCode(){return 1;}

因为上述的 hashCode 办法返回的 hash 值全部都是 1，那么就会导致 HashMap 中的链表比那的很长，如果数据此时咱们向 HashMap 中放很多节点的话，HashMap 就会转换成红黑树结构，所以链表长度超过 8 就转换成红黑树的设计更多的是为了避免用户本人实现了不好的哈希算法
而导致链表过长，影响查问效率，而此时通过转换红黑树结构用来保障极其状况下的查问效率。

HashMap 初始化

HashMap 的默认初始化大小是 16，加载因子是 0.75，扩容的阙值就是 12（16*0.75），如果进行 HashMap 初始化的时候传入了自定义容量大小参数 size，那么初始化的大小就是正好大于 size 的 2 的整数次方，比方传入 10，大小就是 16，传入 30 大小就是 32，源码如下：

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;//n>>>1 示意 n 的二进制向右挪动 1 位，以下同理，而后跟挪动前的 n 进行异或操作
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

上述源码中，通过将 n 的高位第一个 1 一直的右移，而后把高位 1 前面的全变为 1，在最初 return 的时候返回 n +1，就合乎 HashMap 容量都是 2 的整数次幂了。
例如下图：

为什么 HashMap 初始化的容量肯定是 2 的整数次幂

不论咱们传入的参数是怎么样的数值，HashMap 外部都会通过 tableSizeFor 办法计算出一个正好大于咱们传入的参数的 2 的整数次幂的数值，那么为什么肯定要是 2 的整数次幂呢？
咱们先来看看计算 key 的 hash 办法如下：

// 计算 key 的 hash 值，hash 值是 32 位 int 值，通过高 16 位和低 16 进行 & 操作计算。static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

失去了 key 的 hash 值后，在计算 key 在 table 中的地位索引的时候，代码如下：

if ((p = tab[i = (n - 1) & hash]) == null)

正是因为 n 是 2 的整数次幂，比方当 n 是 2 时，它的二进制是 10，4 时是 100，8 时是 1000，16 时是 10000….，那么（n-1）的二进制与之对应就是（2-1）是 1，（4-1）是 11，（8-1）是 111，（16-1）是 1111，为什么要用 (n – 1) & hash
来计算数组的地位索引呢，正是因为(n – 1) & hash 的索引肯定是落在 0～（n-1）之间的地位，而不必管 hash 值是多少，因为“与”操作的后果就是散列值的高位全副归零，只保留低位值，用来做数组下标拜访。以初始长度 16 为例，
16-1=15，2 进制示意是 00000000 00000000 00001111。和某散列值做“与”操作如下，后果就是截取了最低的四位值。

为什么 HashMap 不是线程平安的

咱们先来看 HashMap 中的 put 办法的源码，如下：

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 容量为空，则进行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 计算 hash 值在表 table 中的地位，这里采纳 & 操作是为了更快的计算出地位索引，// 而不是取模运算，如果该地位为空，则间接将元素插入到这个地位
        // 此处也会产生多线程 put，值笼罩问题。if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 判断 tab 表中存在雷同的 key。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，则进行遍历此时 e 指向反复的 key
                for (int binCount = 0; ; ++binCount) {
                    //jdk1.7 采纳的是头差法，jdk1.8 采纳的是尾差法
                    if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                        // 判断链表的长度是否大于 TREEIFY_THRESHOLD，如果大于则转换红黑树结构
                        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;
                }
            }
            // 发现了反复的 key，判断是否笼罩，如果笼罩返回旧值，if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 持续更新次数，不是原子操作，多线程 put 存在并发平安问题
        ++modCount;
        // 如果大于阙值(这个阙值和下面那个不一样，这个等于以后容量 * 加载因子, 默认是 16*0.75 = 12)，进行扩容。if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上图局部源码中能够看出 HashMap 的 put 办法中有一行代码是 ++modCount，
咱们都晓得这段代码并不是一个原子操作，它实际上是三个操作，
执行步骤分为三步：读取、减少、保留，而且每步操作之间能够交叉其它线程的执行，
所以导致线程不平安。

另外还有导致线程不平安的状况还有：

同时 put 碰撞导致数据失落

//put 办法中局部源码
if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

比方下面的源码中，如果当初有两个线程 A 和 B，它们的 key 的 hash 值正好一样，而后它们同时执行到了这个 if 判断，并且都发现 tab 中 i 的地位是空，那么线程 A 就将本人的元素放到该地位，然而线程 B 之前也是判断到这个地位为空，
所以他在 A 之后也将本人的元素放到了该地位而笼罩了之前线程 A 的元素，这就是多线程同时 put 碰撞导致数据失落的场景，所以 HashMap 是非线程平安的

扩容期间取出的值不精确

咱们先来看看 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;
        // 如果数组时空的，或者以后槽点是空的，阐明 key 所对应的 value 不存在，间接返回 null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 判断第一个节点是否是咱们须要的节点，如果是则间接返回
            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);
                // 遍历链表，查找 key
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
}

下面的 get 办法的源码中能够看出 get 办法次要是以下步骤：

  1. 计算 Hash 值，并由此值找到对应的槽点。
  2. 如果数组是空的或者该地位为 null，那么间接返回 null 就能够了。
  3. 如果该地位处的节点刚好就是咱们须要的，间接返回该节点的值。
  4. 如果该地位节点是红黑树或者正在扩容，就用 find 办法持续查找。
  5. 否则那就是链表，就进行遍历链表查找。

首先 HashMap 的 get 办法是从 table 中查问咱们要查找的 key 是否存在，如果存在则返回，不存在则间接返回 null，
那么如果是在扩容期间，为什么获取的后果不精确呢？咱们再来看看 HashMap 的扩容办法 resize()，局部源码如下：

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;
                    .
                    .
                    .// 此处疏忽
                }
            }
        }

下面的源码是 HashMap 的 resize 办法的一小部分，首先咱们晓得 HashMap 的扩容会把旧数组的数据迁徙到新数组中（怎么迁徙的咱们前面再说），在搬迁的过程中会把旧数组正在迁徙的桶置为空比方，正如
下面代码 oldTab[j] = null 这一行代码，正是把索引 j 的桶（或者槽点）置为空了，然而如果此时还没有实现所有的数据的迁徙，那么 HashMap 中依然是应用的旧数组，
此时咱们通过 get 办法查问的 key 的所以正好在这个旧数组中索引地位是 oldTab[j]的地位，因为这个地位曾经置空了，所以就会返回 null，所以产生了扩容期间读取数据不精确。

HashMap 在 java7 和 java8 中的区别

底层数据结构比照

java7 的 HashMap 的构造示意图如下：

上图中能够看出 jdk1.7 中 HashMap 采纳的数据结构是数组 + 链表的构造。

java8 中的 HashMap 构造示意图如下：

从图中咱们能够看出，java8 中的 HashMap 有三种数据结构：

  1. 第一种构造是就是数组，数组中空着的地位（槽）代表以后没有数据来填充
  2. 第二种是和 jdk1.7HashMap 相似的拉链构造，在每一个槽中会首先填入第一个节点，后续如果计算出雷同的 Hash 值，就用链表的模式往后延长
  3. 第三种是红黑树结构，这个是 java7 中 HashMap 中没有的数据结构，当第二种状况的链表长度大于某一个阙值（默认为 8）的时候，HashMap 便会把这个链表从链表构造转化为红黑树的模式，目标是为了保障查找效率，

这里简略介绍一下红黑树，红黑树是一种不严格的均衡二叉查找树, 次要解决二叉查找树因为动静更新导致的性能进化, 其中的均衡的意思代表着近似均衡, 等价于性能不会进化. 红黑树中的节点分为两类: 彩色节点和红色节点, 一颗红黑树须要满足:

  1. 根节点是彩色。
  2. 每个叶子节点都是彩色的空节点(null)。
  3. 任何相邻的节点都不能同时为红色, 也就是说红色节点是被彩色离开的。
  4. 每个节点，从该节点达到其可达到的叶子节点的所有门路，都蕴含雷同数目的彩色节点。

因为红黑树的自均衡特点，所以其查找性能近似于二分查找，工夫复杂度是 O(log(n))，相比于链表构造，
如果产生了最坏的状况，可能须要遍历整个链表能力找到指标元素，工夫复杂度为 O(n)，远远大于红黑树的 O(log(n))，
尤其是在节点越来越多的状况下，O(log(n))

插入方式比照

jdk1.7 中插入新节点采纳的是头查法，就是如果来了新节点，将新节点插入到数组中，原数组中的原始节点作为新节点的后继节点，而且是先判断是否须要扩容，在插入。

jdk1.8 中插入新节点的形式是尾查法，就是将新来的节点插入到数组中对应槽点的尾部，插入时先插入，在判断是否须要扩容。

扩容形式比照

jdk1.8 中采纳的是原地位不变或者地位变为索引 + 旧容量大小，resize()办法局部源码如下：

//jdk1.8 代码扩容形式
// 其中的 loHead 结尾的示意低位链表结尾节点，loTail 示意低位链表尾部节点，hiHead 结尾的示意高位链表结尾节点，hiTail 示意高位链表尾部节点
// 因为扩容时，容量为之前的两倍，而扩容的办法又是原地位不变或者地位变为索引 + 旧容量大小，所以这里把扩容的容量分为两局部
// 一部分是原容量大小，用 loHead 和 loTail 示意首尾地位节点，一部分是新扩容的容量大小，用 hiHead 和 hiTail 示意首尾地位节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    // 该办法是扩容时采纳的尾查法
    next = e.next;
    // 如果判断等于 0，则节点在上面插入新数组中的地位索引等于其在旧数组中的地位索引
    if ((e.hash & oldCap) == 0) {if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    // 如果不能于 0，节点在上面插入新数组中的地位索引等于在旧数组中的地位索引 + 旧数组容量大小
    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;
}

jdk1.7 中的 HashMap 扩容的时候须要对原数组中的元素进行从新 Hash 定位在新数组中的地位，transfer 办法的源码如下：。

//jdk1.7HashMap 的扩容办法
void resize(int newCapacity) {Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return;
    }
 
    Entry[] newTable = new Entry[newCapacity];
    // transfer()办法把原数组中的值放到新数组中，同时根据 initHashSeedAsNeeded(newCapacity)返回的 boolean 值决定是否从新 hash
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 设置 hashmap 扩容后为新的数组援用
    table = newTable;
    // 设置 hashmap 扩容新的阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
  int newCapacity = newTable.length;
  for (Entry<K,V> e : table) {while(null != e) {
      // 保留 e 的后继节点。Entry<K,V> next = e.next;
      // 从新 hash 在新数组中的地位
      if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);
      }
      // 计算节点 e 在新数组中的地位索引
      int i = indexFor(e.hash, newCapacity);
      // 将原节点 e 的后继节点指向 newTable[i]，采纳的是头插法
      e.next = newTable[i];
      // 将节点 e 放到 newTable[i]数组中，newTable[i] = e;
      // 将 next 付给 e，开始下一次循环
      e = next;
    }
  }
}

同时因为 jdk1.7 中 HashMap 的扩容办法中调用的 transfer 办法内采纳的是头插法，头插法会使链表产生反转，多线程环境下，会产生循环链表，
下面代码咱们联合图来了解头插法和为什么多线程环境下会产生循环链表：
首先假如此时有原 HashMap 表的外部数据存储如下图：

此时达到了扩容要求，而后线程 1 和线程 2 此时同时进行扩容，线程 1 和线程 2 扩容时的新数组（newTable）如下图：

假如线程 2 先执行 transfer 办法，并且当它正好执行完了 Entry<K,V> next = e.next; 这行代码后，cpu 工夫片切换到了线程 1 来执行，并且线程 1 执行完了 transfer 办法，如下图：
线程 1 插入 A 节点到本人的新表中

线程 1 插入 B 节点到本人的新表中

线程 1 插入 C 节点到本人的新表中

当线程 1 执行完了 transfer 办法后，还没有执行 table = newTable 这行代码，此时 cpu 工夫片有切换到了线程 2，那么线程 2 持续接着之前的地位执行，此处须要留神因为
因为之前线程 2 切换线程 1 之前曾经执行完了 Entry<K,V> next = e.next 这行代码，因而在线程 2 中
变量 e 存的是 A 节点了，变量 next 存的是 B 节点，而且又因为线程 1 执行完了 transfer 办法后，原数组的节点指向如上图能够看出是 C 指向 B， B 是指向 A 的，所以切换到线程 2 的时候，线程 2 中的节点指向如下图：

线程 2 插入 A 节点到本人的新表中

线程 2 插入 B 节点到本人的新表中

因为 B 节点指向 A 节点，所以下次插入产生了链表循环，如下图：

综上就是 HashMap 采纳头插法的时候产生链表循环的场景。

jdk1.8 中在对 HashMap 进行扩容的时候放弃头插法而改为尾插法了，扩容代码我曾经在下面的扩容形式代码中标出，通过尾插法就防止了因为链表反转导致多线程环境下产生链表循环的状况。

ConcurrentHashMap 在 java7 和 java8 中的区别

数据结构

咱们先看一下 jdk1.7 中 ConcurrentHashMap 的底层数据结构，如下图：

图中咱们能够看出 concurrentHashMap 外部进行了 Segment 分段，Segment 继承了 ReentrantLock，能够了解为一把锁，
各个 Segment 之间互相独立上锁，互不影响，相比 HashTable 每次操作都须要锁住整个对象而言，效率大大晋升，正是因为 concurrentHashMap
的锁粒度是针对每个 Segment 而不是整个对象。

每个 Segment 的底层数据结构又和 HashMap 相似，还是数组和链表组成的拉链构造，默认有 0～15 共 16 个 Segment，所以最多
能够同时反对 16 个线程并发操作（每个线程别离散布在不同的 Segment 上）。16 这个默认值能够在初始化的时候设置为其余值，一旦设置确认初始化
之后，是不能够扩容的。

jdk1.8 中的 ConcurrentHashMap 的底层数据结构，如下图：

通过下面两个图中能够看出，jdk1.8 中的 ConcurrentHashMap 在数据结构上比 jdk1.7 中多了红黑树结构，引入红黑树结构是为了避免查问效率升高。

并发水平

这里咱们简略通过 java7 和 java8 的 ConcurrentHashMap 的含参构造函数看一下比照，首先 java7 的 ConcurrentHashMap 的构造函数代码如下：

// 通过指定的容量，加载因子和并发等级创立一个新的 ConcurrentHashMap
public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, int concurrencyLevel) {
    // 对结构参数做判断
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    // 限度并发等级不能够大于最大等级
    if (concurrencyLevel > MAX_SEGMENTS)
        concurrencyLevel = MAX_SEGMENTS;
    //sshift 用来记录向左按位挪动的次数
    int sshift = 0;
    //ssize 用来记录 Segment 数组的大小
    int ssize = 1;
    //Segment 的大小为大于等于 concurrencyLevel 的第一个 2 的 n 次方的数
    while (ssize < concurrencyLevel) {
        ++sshift;
        // 2 的幂次方，2^1,2^2....
        ssize <<= 1;
    }

    this.segmentShift = 32 - sshift;
    this.segmentMask = ssize - 1;
    // 限度最大初始化容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // c 统计每个 Segment 内有多少元素
    int c = initialCapacity / ssize;
    // 如果有余数，则 Segment 数量加 1
    if (c * ssize < initialCapacity)
        ++c;
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    while (cap < c)
        cap <<= 1;

    // 创立第一个 Segment，并放入 Segment[]数组中，作为第一个 Segment
    Segment<K,V> s0 =
        new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                         (HashEntry<K,V>[])new HashEntry[cap]);
    // 初始化 Segment 数组大小
    Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
    this.segments = ss;
}

jdk1.7 中的并发等级（concurrencyLevel）用 Segment 的数量来确定，Segment 的个数为大于等于 concurrencyLevel 的第一个 2 的 n 次方的整数，例如当 concurrencyLevel 为 12,13,14,15,16 时，此时的 Segment 的数量为 16

java8 中的源码汇总保留了 Segment 片段，然而并没有应用，构造函数如下：

public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        // 如果并发等级大于初始化容量，则限度初始化容量，// 这样的话就是一个槽点对应一个线程，那么现实状况下，最大的并发水平就是数组长度
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }

通过下面的代码的比照能够得出一下论断：

  1. java7 中采纳 Segment 分段锁来保障平安，每个 Segment 独立加锁，最大并发数就是 Segment 的个数，默认是 16。
  2. java8 中放弃了 Segment 设计，采纳 Node+CAS+synchronized 保障线程平安，锁粒度更新，现实状况下 table 数组元素的个数（也就是数组长度）就是反对并发的最大个数。

遇到 Hash 碰撞

  1. java7 中遇到 Hash 抵触，采纳拉链法，查找时间复杂度是 O(n)，n 是链表的长度。
  2. java8 中遇到 Hash 抵触，先采纳拉链法，查找时间复杂度是 O(n)，当链表长度超过肯定阙值时，

将链表转换为红黑树结构，来保障查找效率，查找时间复杂度升高为 O(log(n))，n 为树中的节点个数。

微信公众号：程序员内功心法

正文完
java
发表至： java
2021-03-08
 0
关于java:聊一聊责任链模式
dubbo负载均衡策略及对应源码分析
关于java:线程池的状态
关于java:本地缓存系统简易设计