面霸篇：Java 核心集合容器全解（核心卷二）

387次阅读  |  发布于2年以前

从面试角度作为切入点提升大家的 Java 内功，所谓根基不牢，地动山摇。

在 《[Redis 系列] 》的开篇 [Redis 为什么这么快] 中说过：学习一个技术，通常只接触了零散的技术点，没有在脑海里建立一个完整的知识框架和架构体系，没有系统观。这样会很吃力，而且会出现一看好像自己会，过后就忘记，一脸懵逼。

我们需要一个系统观，清晰完整的去学习技术，在「[面霸篇：Java 核心基础大满贯（卷一）] 」中，码哥梳理了 Java 高频核心知识点。

本篇将一举攻破 Java 集合容器知识点，跟着「码哥」一起来提纲挈领，梳理一个完整的 Java 容器开发技术能力图谱，将基础夯实。

集合容器概述

什么是集合？

顾名思义，集合就是用于存储数据的容器。

集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。

❝码老湿，可以说下集合框架的三大块内容具体指的是什么吗？

接口

面向接口编程，抽象出集合类型，使得我们可以在操作集合的时候不必关心具体实现，达到「多态」。

就好比密码箱，我们只关心能打开箱子，存放东西，并且关闭箱子，至于怎么加密咱们不关心。

接口实现

每种集合的具体实现，是重用性很高的数据结构。

算法

集合提供了数据存放以及查找、排序等功能，集合有很多种，也就是算法通常也是多态的，因为相同的方法可以在同一个接口被多个类实现时有不同的表现。

事实上，算法是可复用的函数。它减少了程序设计的辛劳。

集合框架通过提供有用的数据结构和算法使你能集中注意力于你的程序的重要部分上，而不是为了让程序能正常运转而将注意力于低层设计上。

集合的特点

集合与数组的区别

由于有多种集合容器，因为每一个容器的自身特点不同，其实原理在于每个容器的内部数据结构不同。

集合容器在不断向上抽取过程中，出现了集合体系。在使用一个体系的原则：参阅顶层内容。建立底层对象。

集合框架有哪些优势

有哪些常用的集合类

Java 容器分为 Collection 和 Map 两大类，Collection 集合的子接口有 Set、List、Queue 三种子接口。

我们比较常用的是 Set、List，Map 接口不是 collection 的子接口。

Collection 集合主要有 List 和 Set 两大接口

Map 是一个键值对集合，存储键、值和之间的映射。Key 无序，唯一；value 不要求有序，允许重复。

Map 没有继承于 Collection 接口，从 Map 集合中检索元素时，只要给出键对象，就会返回对应的值对象。

Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

集合的底层数据结构

Collection

  1. List

2 . Set

Map

集合的 fail-fast 快速失败机制

Java 集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。

原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。

集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。

每当迭代器使用 hashNext()/next()遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。

解决办法：

  1. 在遍历过程中，所有涉及到改变 modCount 值得地方全部加上 synchronized。
  2. 使用 CopyOnWriteArrayList 来替换 ArrayList

Collection 接口

List 接口

Itertator 是什么

Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。

迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程中移除元素。

List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){
  String obj = it. next();
  System. out. println(obj);
}

如何边遍历边移除 Collection 中的元素？

Iterator<Integer> it = list.iterator();
while(it.hasNext()){
   *// do something*
   it.remove();
}

一种最常见的错误代码如下：

for(Integer i : list){
   list.remove(i)
}

运行以上错误代码会报 ConcurrentModificationException 异常。

如何实现数组和 List 之间的转换？

ArrayList 和 LinkedList 的区别是什么？

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

为什么 ArrayList 的 elementData 加上 transient 修饰？

ArrayList 中的数组定义如下：

private transient Object[] elementData;

ArrayList 的定义：

public class ArrayList<E> extends AbstractList<E>
     implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。

transient 的作用是说不希望 elementData 数组被序列化。

每次序列化时，先调用 defaultWriteObject()方法序列化 ArrayList中的非 transient元素，然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。

介绍下 CopyOnWriteArrayList？

CopyOnWriteArrayList 是 ArrayList 的线程安全版本，也是大名鼎鼎的 copy-on-write（COW，写时复制）的一种实现。

在读操作时不加锁，跟 ArrayList 类似；在写操作时，复制出一个新的数组，在新数组上进行操作，操作完了，将底层数组指针指向新数组。

适合使用在读多写少的场景。例如 add(Ee)方法的操作流程如下：使用 ReentrantLock 加锁，拿到原数组的 length，使用 Arrays.copyOf 方法从原数组复制一个新的数组（length+1），将要添加的元素放到新数组的下标 length 位置，最后将底层数组指针指向新数组。

List、Set、Map 三者的区别?

Set 接口

说一下 HashSet 的实现原理？

hashCode（）与 equals（）的相关规定：

  1. 如果两个对象相等，则 hashcode 一定也是相同的
  2. 两个对象相等，对两个 equals 方法返回 true
  3. 两个对象有相同的 hashcode 值，它们也不一定是相等的
  4. 综上，equals 方法被覆盖过，则 hashCode 方法也必须被覆盖
  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与 equals 的区别

  1. ==是判断两个变量或实例是不是指向同一个内存空间 equals 是判断两个变量或实例所指向的内存空间的值是不是相同
  2. == 是指对内存地址进行比较 equals() 是对字符串的内容进行比较
  3. ==指引用是否相同， equals() 指的是值是否相同。

Queue

BlockingQueue 是什么？

Java.util.concurrent.BlockingQueue 是一个队列，在进行检索或移除一个元素的时候，线程会等待队列变为非空；

当在添加一个元素时，线程会等待队列中的可用空间。

BlockingQueue 接口是 Java 集合框架的一部分，主要用于实现生产者-消费者模式。

Java 提供了几种 BlockingQueue的实现，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等。

在 Queue 中 poll()和 remove()有什么区别？

Map 接口

Map 整体结构如下所示：

Hashtable 比较特别，作为类似 Vector、Stack 的早期集合相关类型，它是扩展了 Dictionary 类的，类结构上与 HashMap 之类明显不同。

HashMap 等其他 Map 实现则是都扩展了 AbstractMap，里面包含了通用方法抽象。

不同 Map 的用途，从类图结构就能体现出来，设计目的已经体现在不同接口上。

HashMap 的实现原理？

在 JDK 1.7 中 HashMap 是以数组加链表的形式组成的，JDK 1.8 之后新增了红黑树的组成结构，当链表大于 8 并且容量大于 64 时，链表结构会转换成红黑树结构。

HashMap 基于 Hash 算法实现的：

  1. 当我们往 Hashmap 中 put 元素时，利用 key 的 hashCode 重新 hash 计算出当前对象的元素在数组中的下标。
  2. 存储时，如果出现 hash 值相同的 key，此时有两种情况。

3 . 获取时，直接找到 hash 值对应的下标，在进一步判断 key 是否相同，从而找到对应值。

4 . 理解了以上过程就不难明白 HashMap 是如何解决 hash 冲突的问题，核心就是使用了数组的存储方式，然后将冲突的 key 的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

JDK1.7 VS JDK1.8 比较

JDK1.8 主要解决或优化了一下问题：

  1. resize 扩容优化
  2. 引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考
  3. 解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。
不同 JDK 1.7 JDK 1.8
存储结构 数组 + 链表 数组 + 链表 + 红黑树
数组 + 链表 + 红黑树 单独函数：inflateTable() 直接集成到了扩容函数resize()中
hash 值计算方式 hash 值计算方式 扰动处理 = 9 次扰动 = 4 次位运算 + 5 次异或运算
存放数据的规则 存放数据的规则 无冲突时，存放数组；冲突 & 链表长度 < 8：存放单链表；冲突 & 链表长度 > 8：树化并存放红黑树
插入数据方式 头插法（先讲原位置的数据移到后 1 位，再插入数据到该位置） 尾插法（直接插入到链表尾部/红黑树）
扩容后存储位置的计算方式 全部按照原来方法进行计算（即 hashCode ->> 扰动函数 ->> (h&length-1)） 按照扩容后的规律计算（即扩容后的位置=原位置 or 原位置 + 旧容量）

如何有效避免哈希碰撞

主要是因为如果使用 hashCode 取余，那么相当于参与运算的只有 hashCode 的低位，高位是没有起到任何作用的。

所以我们的思路就是让 hashCode 取值出的高位也参与运算，进一步降低 hash 碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的 hash()函数如下：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
}

HashMap 的 put 方法的具体流程？

当我们 put 的时候，首先计算 key的hash值，这里调用了 hash方法，hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作，高 16bit 补 0，一个数和 0 异或不变，所以 hash 函数大概的作用就是：高 16bit 不变，低 16bit 和高 16bit 做了一个异或，目的是减少碰撞。

①.判断键值对数组 table[i]是否为空或为 null，否则执行 resize()进行扩容；

②.根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加，转向 ⑥，如果 table[i]不为空，转向 ③；

③.判断 table[i]的首个元素是否和 key 一样，如果相同直接覆盖 value，否则转向 ④，这里的相同指的是 hashCode 以及 equals；

④.判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向 ⑤；

⑤.遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value 即可；

⑥.插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。

HashMap 的扩容操作是怎么实现的？

①.在 jdk1.8 中，resize 方法是在 hashmap 中的键值对大于阀值时或者初始化时，就调用 resize 方法进行扩容；

②.每次扩展的时候，都是扩展 2 倍；

③.扩展后 Node 对象的位置要么在原位置，要么移动到原偏移量两倍的位置。

在 1.7 中，扩容之后需要重新去计算其 Hash 值，根据 Hash 值对其进行分发.

但在 1.8 版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为 0，0 -表示还在原来位置，否则就移动到原数组位置 + oldCap。

重新进行 hash 分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上。

任何类都可以作为 Key 么？

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：

为什么 HashMap 中 String、Integer 这样的包装类适合作为 K？

String、Integer 等包装类的特性能够保证 Hash 值的不可更改性和计算准确性，能够有效的减少 Hash 碰撞的几率。

  1. 都是 final 类型，即不可变性，保证 key 的不可更改性，不会存在获取 hash 值不同的情况
  2. 内部已重写了equals()、hashCode()等方法，遵守了 HashMap 内部的规范（不清楚可以去上面看看 putValue 的过程），不容易出现 Hash 值计算错误的情况；

HashMap 为什么不直接使用 hashCode()处理后的哈希值直接作为 table 的下标？

hashCode()方法返回的是 int 整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有 40 亿个映射空间，而 HashMap 的容量范围是在 16（初始化默认值）~2 ^ 30，HashMap 通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；

HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

这个算法应该如何设计呢？

我们首先可能会想到采用 % 取余的操作来实现。

但是，重点来了：取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。

并且采用二进制位操作 &，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

那为什么是两次扰动呢？

答：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少 Hash 冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

HashMap 和 ConcurrentHashMap 的区别

  1. ConcurrentHashMap 对整个桶数组进行了分割分段(Segment)，每一个分段上都用 lock 锁进行保护，相对于 HashTable 的 synchronized 锁的粒度更精细了一些，并发性能更好，而 HashMap 没有锁机制，不是线程安全的。（JDK1.8 之后 ConcurrentHashMap 启用了一种全新的方式实现,利用 synchronized + CAS 算法。）
  2. HashMap 的键值对允许有 null，但是 ConCurrentHashMap 都不允许。

ConcurrentHashMap 实现原理

JDK1.7

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

在 JDK1.7 中，ConcurrentHashMap 采用 Segment + HashEntry 的方式进行实现，结构如下：

一个 ConcurrentHashMap 里包含一个 Segment 数组。

Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

  1. 该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；
  2. HashEntry 内部使用 volatile 的 value 字段来保证可见性，get 操作需要保证的是可见性，所以并没有什么同步逻辑。
  3. Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个 HashEntry 数组里得元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。

get 操作需要保证的是可见性，所以并没有什么同步逻辑

public V get(Object key) {
        Segment<K,V> s; // manually integrate access methods to reduce overhead
        HashEntry<K,V>[] tab;
        int h = hash(key.hashCode());
       //利用位操作替换普通数学运算
       long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        // 以Segment为单位，进行定位
        // 利用Unsafe直接进行volatile access
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
            (tab = s.table) != null) {
           //省略
          }
        return null;
    }

而对于 put 操作，首先是通过二次哈希避免哈希冲突，然后以 Unsafe 调用方式，直接获取相应的 Segment，然后进行线程安全的 put 操作：

 public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        // 二次哈希，以保证数据的分散性，避免哈希冲突
        int hash = hash(key.hashCode());
        int j = (hash >>> segmentShift) & segmentMask;
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);
        return s.put(key, hash, value, false);
    }

其核心逻辑实现在下面的内部方法中：

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            // scanAndLockForPut会去查找是否有key相同Node
            // 无论如何，确保获取锁
            HashEntry<K,V> node = tryLock() ? null :
                scanAndLockForPut(key, hash, value);
            V oldValue;
            try {
                HashEntry<K,V>[] tab = table;
                int index = (tab.length - 1) & hash;
                HashEntry<K,V> first = entryAt(tab, index);
                for (HashEntry<K,V> e = first;;) {
                    if (e != null) {
                        K k;
                        // 更新已有value...
                    }
                    else {
                        // 放置HashEntry到特定位置，如果超过阈值，进行rehash
                        // ...
                    }
                }
            } finally {
                unlock();
            }
            return oldValue;
        }

JDK1.8

在JDK1.8 中，放弃了 Segment 臃肿的设计，取而代之的是采用 Node + CAS + Synchronized 来保证并发安全进行实现。

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

另外，需要注意的是，“线程安全”这四个字特别容易让人误解，因为ConcurrentHashMap 只能保证提供的原子性读写操作是线程安全的。

误区

我们来看一个使用 Map 来统计 Key 出现次数的场景吧，这个逻辑在业务代码中非常常见。

开发人员误以为使用了 ConcurrentHashMap 就不会有线程安全问题，于是不加思索地写出了下面的代码：

// 共享数据
ConcurrentHashMap<String, Long> freqs = new ConcurrentHashMap<>(ITEM_COUNT);

public void normaluse(String key) throws InterruptedException {

      if (freqs.containsKey(key)) {
        //Key存在则+1
        freqs.put(key, freqs.get(key) + 1);
      } else {
        //Key不存在则初始化为1
        freqs.put(key, 1L);
      }
}

大错特错啊朋友们，需要注意 ConcurrentHashMap 对外提供的方法或能力的限制：

正确写法：

//利用computeIfAbsent()方法来实例化LongAdder，然后利用LongAdder来进行线程安全计数
freqs.computeIfAbsent(key, k -> new LongAdder()).increment();

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8