关于java:大厂必问的Java集合面试题

28次阅读

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

本文目录：

  • 常见的汇合有哪些？
  • List、Set 和 Map 的区别
  • ArrayList 理解吗？
  • ArrayList 的扩容机制？
  • 怎么在遍历 ArrayList 时移除一个元素？
  • Arraylist 和 Vector 的区别
  • Arraylist 与 LinkedList 区别

  • HashMap

    • 解决 hash 抵触的方法有哪些？HashMap 用的哪种？
    • 应用的 hash 算法？
    • 扩容过程？
    • put 办法流程？
    • 红黑树的特点？
    • 为什么应用红黑树而不应用 AVL 树？
    • 在解决 hash 抵触的时候，为什么抉择先用链表，再转红黑树?
    • HashMap 的长度为什么是 2 的幂次方？
    • HashMap 默认加载因子是多少？为什么是 0.75？
    • 个别用什么作为 HashMap 的 key?
    • HashMap 为什么线程不平安？
    • HashMap 和 HashTable 的区别？
  • LinkedHashMap 底层原理？
  • 讲一下 TreeMap？
  • HashSet 底层原理？
  • HashSet、LinkedHashSet 和 TreeSet 的区别？
  • 什么是 fail fast？
  • 什么是 fail safe？
  • 讲一下 ArrayDeque？
  • 哪些汇合类是线程平安的？哪些不平安？
  • 迭代器 Iterator 是什么？
  • Iterator 和 ListIterator 有什么区别？

  • 并发容器

    • ConcurrentHashMap

      • put 执行流程？
      • 怎么扩容？
      • ConcurrentHashMap 和 Hashtable 的区别？
    • CopyOnWrite
    • ConcurrentLinkedQueue

    • 阻塞队列

      • JDK 提供的阻塞队列
      • 原理

本文曾经收录到 github 仓库，此仓库用于分享 互联网大厂高频面试题、Java 外围常识总结，包含 Java 根底、并发、MySQL、Springboot、MyBatis、Redis、RabbitMQ 等等，面试必备！欢送大家 star！

github 地址：https://github.com/Tyson0314/…

常见的汇合有哪些？

Java 汇合类次要由两个接口 Collection 和Map派生进去的，Collection 有三个子接口：List、Set、Queue。

Java 汇合框架图如下：

List 代表了有序可反复汇合，可间接依据元素的索引来拜访；Set 代表无序不可反复汇合，只能依据元素自身来拜访；Queue 是队列汇合。Map 代表的是存储 key-value 对的汇合，可依据元素的 key 来拜访 value。

汇合体系中罕用的实现类有 ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap 等实现类。

List、Set 和 Map 的区别

  • List 以索引来存取元素，有序的，元素是容许反复的，能够插入多个 null；
  • Set 不能寄存反复元素，无序的，只容许一个 null；
  • Map 保留键值对映射；
  • List 底层实现有数组、链表两种形式；Set、Map 容器有基于哈希存储和红黑树两种形式实现；
  • Set 基于 Map 实现，Set 里的元素值就是 Map 的键值。

ArrayList 理解吗？

ArrayList 的底层是动静数组，它的容量能动静增长。在增加大量元素前，利用能够应用 ensureCapacity 操作减少 ArrayList 实例的容量。ArrayList 继承了 AbstractList，并实现了 List 接口。

ArrayList 的扩容机制？

ArrayList 扩容的实质就是计算出新的扩容数组的 size 后实例化，并将原有数组内容复制到新数组中去。默认状况下，新的容量会是原容量的 1.5 倍。以 JDK1.8 为例阐明:

public boolean add(E e) {
    // 判断是否能够包容 e，若能，则间接增加在开端；若不能，则进行扩容，而后再把 e 增加在开端
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将 e 增加到数组开端
    elementData[size++] = e;
    return true;
    }

// 每次在 add()一个元素时，arraylist 都须要对这个 list 的容量进行一个判断。通过 ensureCapacityInternal()办法确保以后 ArrayList 保护的数组具备存储新元素的能力，通过解决之后将元素存储在数组 elementData 的尾部

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果传入的是个空数组则最小容量取默认容量与 minCapacity 之间的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
  private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 若 ArrayList 已有的存储能力满足最低存储要求，则返回 add 间接增加元素；如果最低要求的存储能力 >ArrayList 已有的存储能力，这就示意 ArrayList 的存储能力有余，因而须要调用 grow(); 办法进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


private void grow(int minCapacity) {
        // 获取 elementData 数组的内存空间长度
        int oldCapacity = elementData.length;
        // 扩容至原来的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 校验容量是否够
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 若预设值大于默认的最大值，查看是否溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 调用 Arrays.copyOf 办法将 elementData 数组指向新的内存空间
         // 并将 elementData 的数据复制到新的内存空间
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

怎么在遍历 ArrayList 时移除一个元素？

foreach 删除会导致疾速失败问题，能够应用迭代器的 remove() 办法。

Iterator itr = list.iterator();
while(itr.hasNext()) {if(itr.next().equals("jay") {itr.remove();
      }
}

Arraylist 和 Vector 的区别

  1. ArrayList 在内存不够时默认是扩大 50% + 1 个，Vector 是默认扩大 1 倍。
  2. Vector 属于线程安全级别的，然而大多数状况下不应用 Vector，因为操作 Vector 效率比拟低。

Arraylist 与 LinkedList 区别

  1. ArrayList 基于动静数组实现；LinkedList 基于链表实现。
  2. 对于随机 index 拜访的 get 和 set 办法，ArrayList 的速度要优于 LinkedList。因为 ArrayList 间接通过数组下标间接找到元素；LinkedList 要挪动指针遍历每个元素直到找到为止。
  3. 新增和删除元素，LinkedList 的速度要优于 ArrayList。因为 ArrayList 在新增和删除元素时，可能扩容和复制数组；LinkedList 实例化对象须要工夫外，只须要批改指针即可。

HashMap

HashMap 应用数组 + 链表 + 红黑树（JDK1.8 减少了红黑树局部）实现的，链表长度大于 8（TREEIFY_THRESHOLD）时，会把链表转换为红黑树，红黑树节点个数小于 6（UNTREEIFY_THRESHOLD）时才转化为链表，避免频繁的转化。

解决 hash 抵触的方法有哪些？HashMap 用的哪种？

解决 Hash 抵触办法有: 凋谢定址法、再哈希法、链地址法。HashMap 中采纳的是 链地址法。

  • 凋谢定址法根本思维就是，如果 p=H(key) 呈现抵触时，则以 p 为根底，再次 hash，p1=H(p), 如果 p1 再次出现抵触，则以 p1 为根底，以此类推，直到找到一个不抵触的哈希地址 pi。因而凋谢定址法所须要的 hash 表的长度要大于等于所须要寄存的元素，而且因为存在再次 hash，所以 只能在删除的节点上做标记，而不能真正删除节点。
  • 再哈希法提供多个不同的 hash 函数，当 R1=H1(key1) 发生冲突时，再计算R2=H2(key1)，直到没有抵触为止。这样做尽管不易产生堆集，但减少了计算的工夫。
  • 链地址法将哈希值雷同的元素形成一个同义词的单链表, 并将单链表的头指针寄存在哈希表的第 i 个单元中，查找、插入和删除次要在同义词链表中进行。链表法实用于常常进行插入和删除的状况。

应用的 hash 算法？

Hash 算法：取 key 的 hashCode 值、高位运算、取模运算。

h=key.hashCode() // 第一步 取 hashCode 值
h^(h>>>16)  // 第二步 高位参加运算，缩小抵触
return h&(length-1);  // 第三步 取模运算

在 JDK1.8 的实现中，优化了高位运算的算法，通过 hashCode()的高 16 位异或低 16 位实现的：这么做能够在数组比拟小的时候，也能保障思考到高下位都参加到 Hash 的计算中，能够缩小抵触，同时不会有太大的开销。

扩容过程？

1.8 扩容机制：当元素个数大于 threshold 时，会进行扩容，应用 2 倍容量的数组代替原有数组。采纳尾插入的形式将原数组元素拷贝到新数组。1.8 扩容之后链表元素绝对地位没有变动，而 1.7 扩容之后链表元素会倒置。

1.7 链表新节点采纳的是头插法，这样在线程一扩容迁徙元素时，会将元素程序扭转，导致两个线程中呈现元素的互相指向而造成循环链表，1.8 采纳了尾插法，防止了这种状况的产生。

原数组的元素在从新计算 hash 之后，因为数组容量 n 变为 2 倍，那么 n - 1 的 mask 范畴在高位多 1bit。在元素拷贝过程不须要从新计算元素在数组中的地位，只须要看看原来的 hash 值新增的那个 bit 是 1 还是 0，是 0 的话索引没变，是 1 的话索引变成“原索引 +oldCap”（依据 e.hash & (oldCap - 1) == 0 判断）。这样能够省去从新计算 hash 值的工夫，而且因为新增的 1bit 是 0 还是 1 能够认为是随机的，因而 resize 的过程会平均的把之前的抵触的节点扩散到新的 bucket。

put 办法流程？

  1. 如果 table 没有初始化就先进行初始化过程
  2. 应用 hash 算法计算 key 的索引
  3. 判断索引处有没有存在元素，没有就直接插入
  4. 如果索引处存在元素，则遍历插入，有两种状况，一种是链表模式就间接遍历到尾端插入，一种是红黑树就依照红黑树结构插入
  5. 链表的数量大于阈值 8，就要转换成红黑树的构造
  6. 增加胜利后会查看是否须要扩容

红黑树的特点？

  • 每个节点或者是彩色，或者是红色。
  • 根节点是彩色。
  • 每个叶子节点（NIL）是彩色。
  • 如果一个节点是红色的，则它的子节点必须是彩色的。
  • 从一个节点到该节点的子孙节点的所有门路上蕴含雷同数目的黑节点。

为什么应用红黑树而不应用 AVL 树？

ConcurrentHashMap 在 put 的时候会加锁，应用红黑树插入速度更快，能够缩小期待锁开释的工夫。红黑树是对 AVL 树的优化，只要求局部均衡，用非严格的均衡来换取增删节点时候旋转次数的升高，进步了插入和删除的性能。

在解决 hash 抵触的时候，为什么抉择先用链表，再转红黑树?

因为红黑树须要进行左旋，右旋，变色这些操作来保持平衡，而单链表不须要。当元素小于 8 个的时候，链表构造能够保障查问性能。当元素大于 8 个的时候，红黑树搜寻工夫复杂度是 O(logn)，而链表是 O(n)，此时须要红黑树来放慢查问速度，然而插入和删除节点的效率变慢了。如果一开始就用红黑树结构，元素太少，插入和删除节点的效率又比较慢，节约性能。

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

Hash 值的范畴值比拟大，应用之前须要先对数组的长度取模运算，失去的余数才是元素寄存的地位也就是对应的数组下标。这个数组下标的计算方法是 (n - 1) & hash。将 HashMap 的长度定为 2 的幂次方，这样就能够应用(n - 1)&hash 位运算代替 % 取余的操作，进步性能。

HashMap 默认加载因子是多少？为什么是 0.75？

先看下 HashMap 的默认构造函数：

int threshold;             // 包容键值对的最大值
final float loadFactor;    // 负载因子
int modCount;  
int size;

Node[] table 的初始化长度 length 为 16，默认的 loadFactor 是 0.75，0.75 是对空间和工夫效率的一个均衡抉择，依据泊松散布，loadFactor 取 0.75 碰撞最小。个别不会批改，除非在工夫和空间比拟非凡的状况下：

  • 如果内存空间很多而又对工夫效率要求很高，能够升高负载因子 Load factor 的值。
  • 如果内存空间缓和而对工夫效率要求不高，能够减少负载因子 loadFactor 的值，这个值能够大于 1。

个别用什么作为 HashMap 的 key?

个别用 Integer、String 这种不可变类当 HashMap 当 key。String 类比拟罕用。

  • 因为 String 是不可变的，所以在它创立的时候 hashcode 就被缓存了，不须要从新计算。这就是 HashMap 中的 key 常常应用字符串的起因。
  • 获取对象的时候要用到 equals() 和 hashCode() 办法，而 Integer、String 这些类都曾经重写了 hashCode() 以及 equals() 办法，不须要本人去重写这两个办法。

HashMap 为什么线程不平安？

  • 多线程下扩容死循环。JDK1.7 中的 HashMap 应用头插法插入元素，在多线程的环境下，扩容的时候有可能导致 环形链表 的呈现，造成死循环。
  • 在 JDK1.8 中，在多线程环境下，会产生 数据笼罩 的状况。

HashMap 和 HashTable 的区别？

HashMap 和 Hashtable 都实现了 Map 接口。

  1. HashMap 能够承受为 null 的 key 和 value，key 为 null 的键值对放在下标为 0 的头结点的链表中，而 Hashtable 则不行。
  2. HashMap 是非线程平安的，HashTable 是线程平安的。Jdk1.5 提供了 ConcurrentHashMap，它是 HashTable 的代替。
  3. Hashtable 很多办法是同步办法，在单线程环境下它比 HashMap 要慢。
  4. 哈希值的应用不同，HashTable 间接应用对象的 hashCode。而 HashMap 从新计算 hash 值。

LinkedHashMap 底层原理？

HashMap 是无序的，迭代 HashMap 所失去元素的程序并不是它们最后放到 HashMap 的程序，即不能放弃它们的插入程序。

LinkedHashMap 继承于 HashMap，是 HashMap 和 LinkedList 的交融体，具备两者的个性。每次 put 操作都会将 entry 插入到双向链表的尾部。

讲一下 TreeMap？

TreeMap 是一个能比拟元素大小的 Map 汇合，会对传入的 key 进行了大小排序。能够应用元素的天然程序，也能够应用汇合中自定义的比拟器来进行排序。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}

TreeMap 的继承构造：

TreeMap 的特点：

  1. TreeMap 是有序的 key-value 汇合，通过红黑树实现。依据键的天然程序进行排序或依据提供的 Comparator 进行排序。
  2. TreeMap 继承了 AbstractMap，实现了 NavigableMap 接口，反对一系列的导航办法，给定具体搜寻指标，能够返回最靠近的匹配项。如 floorEntry()、ceilingEntry()别离返回小于等于、大于等于给定键关联的 Map.Entry()对象，不存在则返回 null。lowerKey()、floorKey、ceilingKey、higherKey()只返回关联的 key。

HashSet 底层原理？

HashSet 基于 HashMap 实现。放入 HashSet 中的元素实际上由 HashMap 的 key 来保留，而 HashMap 的 value 则存储了一个动态的 Object 对象。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map; // 基于 HashMap 实现
    //...
}

HashSet、LinkedHashSet 和 TreeSet 的区别？

HashSet 是 Set 接口的次要实现类，HashSet 的底层是 HashMap，线程不平安的，能够存储 null 值；

LinkedHashSet 是 HashSet 的子类，可能依照增加的程序遍历；

TreeSet 底层应用红黑树，可能依照增加元素的程序进行遍历，排序的形式能够自定义。

什么是 fail fast？

fast-fail 是 Java 汇合的一种谬误机制。当多个线程对同一个汇合进行操作时，就有可能会产生 fast-fail 事件。例如：当线程 a 正通过 iterator 遍历汇合时，另一个线程 b 批改了汇合的内容，此时 modCount（记录汇合操作过程的批改次数）会加 1，不等于 expectedModCount，那么线程 a 拜访汇合的时候，就会抛出 ConcurrentModificationException，产生 fast-fail 事件。边遍历边批改汇合也会产生 fast-fail 事件。

解决办法：

  • 应用 Colletions.synchronizedList 办法或在批改汇合内容的中央加上 synchronized。这样的话，增删汇合内容的同步锁会阻塞遍历操作，影响性能。
  • 应用 CopyOnWriteArrayList 来替换 ArrayList。在对 CopyOnWriteArrayList 进行批改操作的时候，会拷贝一个新的数组，对新的数组进行操作，操作实现后再把援用移到新的数组。

什么是 fail safe？

采纳平安失败机制的汇合容器，在遍历时不是间接在汇合内容上拜访的，而是先复制原有汇合内容，在拷贝的汇合上进行遍历。java.util.concurrent 包下的容器都是平安失败，能够在多线程下并发应用，并发批改。

原理：因为迭代时是对原汇合的拷贝进行遍历，所以在遍历过程中对原汇合所作的批改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。

毛病：基于拷贝内容的长处是防止了 Concurrent Modification Exception，但同样地，迭代器并不能拜访到批改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的汇合拷贝，在遍历期间原汇合产生的批改迭代器是不晓得的。

讲一下 ArrayDeque？

ArrayDeque 实现了双端队列，外部应用循环数组实现，默认大小为 16。它的特点有：

  1. 在两端增加、删除元素的效率较高
  2. 依据元素内容查找和删除的效率比拟低。
  3. 没有索引地位的概念，不能依据索引地位进行操作。

ArrayDeque 和 LinkedList 都实现了 Deque 接口，如果只须要从两端进行操作，ArrayDeque 效率更高一些。如果同时须要依据索引地位进行操作，或者常常须要在两头进行插入和删除（LinkedList 有相应的 api，如 add(int index, E e)），则应该选 LinkedList。

ArrayDeque 和 LinkedList 都是线程不平安的，能够应用 Collections 工具类中 synchronizedXxx()转换成线程同步。

哪些汇合类是线程平安的？哪些不平安？

线性平安的汇合类：

  • Vector：比 ArrayList 多了同步机制。
  • Hashtable。
  • ConcurrentHashMap：是一种高效并且线程平安的汇合。
  • Stack：栈，也是线程平安的，继承于 Vector。

线性不平安的汇合类：

  • Hashmap
  • Arraylist
  • LinkedList
  • HashSet
  • TreeSet
  • TreeMap

迭代器 Iterator 是什么？

Iterator 模式用同一种逻辑来遍历汇合。它能够把拜访逻辑从不同类型的汇合类中形象进去，不须要理解汇合外部实现便能够遍历汇合元素，对立应用 Iterator 提供的接口去遍历。它的特点是更加平安，因为它能够保障，在以后遍历的汇合元素被更改的时候，就会抛出 ConcurrentModificationException 异样。

public interface Collection<E> extends Iterable<E> {Iterator<E> iterator();
}

次要有三个办法：hasNext()、next()和 remove()。

Iterator 和 ListIterator 有什么区别？

ListIterator 是 Iterator 的增强版。

  • ListIterator 遍历能够是逆向的，因为有 previous()和 hasPrevious()办法，而 Iterator 不能够。
  • ListIterator 有 add()办法，能够向 List 增加对象，而 Iterator 却不能。
  • ListIterator 能够定位以后的索引地位，因为有 nextIndex()和 previousIndex()办法，而 Iterator 不能够。
  • ListIterator 能够实现对象的批改，set()办法能够实现。Iierator 仅能遍历，不能批改。
  • ListIterator 只能用于遍历 List 及其子类，Iterator 可用来遍历所有汇合。

并发容器

JDK 提供的这些容器大部分在 java.util.concurrent 包中。

  • ConcurrentHashMap: 线程平安的 HashMap
  • CopyOnWriteArrayList: 线程平安的 List，在读多写少的场合性能十分好，远远好于 Vector.
  • ConcurrentLinkedQueue: 高效的并发队列，应用链表实现。能够看做一个线程平安的 LinkedList，这是一个非阻塞队列。
  • BlockingQueue: 阻塞队列接口，JDK 外部通过链表、数组等形式实现了这个接口。非常适合用于作为数据共享的通道。
  • ConcurrentSkipListMap: 跳表的实现。应用跳表的数据结构进行疾速查找。

ConcurrentHashMap

多线程环境下，应用 Hashmap 进行 put 操作会引起死循环，应该应用反对多线程的 ConcurrentHashMap。

JDK1.8 ConcurrentHashMap 勾销了 segment 分段锁，而采纳 CAS 和 synchronized 来保障并发平安。数据结构采纳数组 + 链表 / 红黑二叉树。synchronized 只锁定以后链表或红黑二叉树的首节点，相比 1.7 锁定 HashEntry 数组，锁粒度更小，反对更高的并发量。当链表长度过长时，Node 会转换成 TreeNode，进步查找速度。

put 执行流程？

在 put 的时候须要锁住 Segment，保障并发平安。调用 get 的时候不加锁，因为 node 数组成员 val 和指针 next 是用 volatile 润饰的，更改后的值会立即刷新到主存中，保障了可见性，node 数组 table 也用 volatile 润饰，保障在运行过程对其余线程具备可见性。

transient volatile Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    volatile V val;
    volatile Node<K,V> next;
}

put 操作流程：

  1. 如果 table 没有初始化就先进行初始化过程
  2. 应用 hash 算法计算 key 的地位
  3. 如果这个地位为空则间接 CAS 插入，如果不为空的话，则取出这个节点来
  4. 如果取出来的节点的 hash 值是 MOVED(-1)的话，则示意以后正在对这个数组进行扩容，复制到新的数组，则以后线程也去帮忙复制
  5. 如果这个节点，不为空，也不在扩容，则通过 synchronized 来加锁，进行增加操作，这里有两种状况，一种是链表模式就间接遍历到尾端插入或者笼罩掉雷同的 key，一种是红黑树就依照红黑树结构插入
  6. 链表的数量大于阈值 8，就会转换成红黑树的构造或者进行扩容（table 长度小于 64）
  7. 增加胜利后会查看是否须要扩容

怎么扩容？

数组扩容 transfer 办法中会设置一个步长，示意一个线程解决的数组长度，最小值是 16。在一个步长范畴内只有一个线程会对其进行复制挪动操作。

ConcurrentHashMap 和 Hashtable 的区别？

  1. Hashtable 通过应用 synchronized 润饰办法的形式来实现多线程同步，因而，Hashtable 的同步会锁住整个数组。在高并发的状况下，性能会十分差。ConcurrentHashMap 采纳了更细粒度的锁来进步在并发状况下的效率。注：Synchronized 容器（同步容器）也是通过 synchronized 关键字来实现线程平安，在应用的时候会对所有的数据加锁。
  2. Hashtable 默认的大小为 11，当达到阈值后，每次依照上面的公式对容量进行裁减：newCapacity = oldCapacity * 2 + 1。ConcurrentHashMap 默认大小是 16，扩容时容量扩充为原来的 2 倍。

CopyOnWrite

写时复制。当咱们往容器增加元素时，不间接往容器增加，而是先将以后容器进行复制，复制出一个新的容器，而后往新的容器增加元素，增加完元素之后，再将原容器的援用指向新容器。这样做的益处就是能够对 CopyOnWrite 容器进行并发的读而不须要加锁，因为以后容器不会被批改。

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock(); //add 办法须要加锁
        try {Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1); // 复制新数组
            newElements[len] = e;
            setArray(newElements); // 原容器的援用指向新容器
            return true;
        } finally {lock.unlock();
        }
    }

从 JDK1.5 开始 Java 并发包里提供了两个应用 CopyOnWrite 机制实现的并发容器，它们是 CopyOnWriteArrayList 和 CopyOnWriteArraySet。

CopyOnWriteArrayList 中 add 办法增加的时候是须要加锁的，保障同步，防止了多线程写的时候复制出多个正本。读的时候不须要加锁，如果读的时候有其余线程正在向 CopyOnWriteArrayList 增加数据，还是能够读到旧的数据。

毛病：

  • 内存占用问题。因为 CopyOnWrite 的写时复制机制，在进行写操作的时候，内存里会同时驻扎两个对象的内存。
  • CopyOnWrite 容器不能保证数据的实时一致性，可能读取到旧数据。

ConcurrentLinkedQueue

非阻塞队列。高效的并发队列，应用链表实现。能够看做一个线程平安的 LinkedList，通过 CAS 操作实现。

如果对队列加锁的老本较高则适宜应用无锁的 ConcurrentLinkedQueue 来代替。适宜在对性能要求绝对较高，同时有多个线程对队列进行读写的场景。

非阻塞队列中的几种次要办法：
add(E e) : 将元素 e 插入到队列开端，如果插入胜利，则返回 true；如果插入失败（即队列已满），则会抛出异样；
remove()：移除队首元素，若移除胜利，则返回 true；如果移除失败（队列为空），则会抛出异样；
offer(E e)：将元素 e 插入到队列开端，如果插入胜利，则返回 true；如果插入失败（即队列已满），则返回 false；
poll()：移除并获取队首元素，若胜利，则返回队首元素；否则返回 null；
peek()：获取队首元素，若胜利，则返回队首元素；否则返回 null

对于非阻塞队列，个别状况下倡议应用 offer、poll 和 peek 三个办法，不倡议应用 add 和 remove 办法。因为应用 offer、poll 和 peek 三个办法能够通过返回值判断操作胜利与否，而应用 add 和 remove 办法却不能达到这样的成果。

阻塞队列

阻塞队列是 java.util.concurrent 包下重要的数据结构，BlockingQueue 提供了线程平安的队列拜访形式：当阻塞队列进行插入数据时，如果队列已满，线程将会阻塞期待直到队列非满；从阻塞队列取数据时，如果队列已空，线程将会阻塞期待直到队列非空。并发包下很多高级同步类的实现都是基于 BlockingQueue 实现的。BlockingQueue 适宜用于作为数据共享的通道。

应用阻塞算法的队列能够用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等形式来实现。

阻塞队列和个别的队列的区别就在于：

  1. 多线程反对，多个线程能够平安的拜访队列
  2. 阻塞操作，当队列为空的时候，生产线程会阻塞期待队列不为空；当队列满了的时候，生产线程就会阻塞直到队列不满。

办法

办法 \ 解决形式 抛出异样 返回非凡值 始终阻塞 超时退出
插入方法 add(e) offer(e) put(e) offer(e,time,unit)
移除办法 remove() poll() take() poll(time,unit)
查看办法 element() peek() 不可用 不可用

JDK 提供的阻塞队列

JDK 7 提供了 7 个阻塞队列，如下

1、ArrayBlockingQueue

有界阻塞队列，底层采纳数组实现。ArrayBlockingQueue 一旦创立，容量不能扭转。其并发管制采纳可重入锁来管制，不论是插入操作还是读取操作，都须要获取到锁能力进行操作。此队列依照先进先出（FIFO）的准则对元素进行排序。默认状况下不能保障线程拜访队列的公平性，参数 fair 可用于设置线程是否偏心拜访队列。为了保障公平性，通常会升高吞吐量。

private static ArrayBlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<Integer>(10,true);//fair

2、LinkedBlockingQueue

LinkedBlockingQueue 是一个用单向链表实现的有界阻塞队列，能够当做无界队列也能够当做有界队列来应用。通常在创立 LinkedBlockingQueue 对象时，会指定队列最大的容量。此队列的默认和最大长度为Integer.MAX_VALUE。此队列依照先进先出的准则对元素进行排序。与 ArrayBlockingQueue 相比起来具备更高的吞吐量。

3、PriorityBlockingQueue

反对优先级的 无界 阻塞队列。默认状况下元素采取天然程序升序排列。也能够自定义类实现 compareTo() 办法来指定元素排序规定，或者初始化 PriorityBlockingQueue 时，指定结构参数 Comparator 来进行排序。

PriorityBlockingQueue 只能指定初始的队列大小，前面插入元素的时候，如果空间不够的话会 主动扩容。

PriorityQueue 的线程平安版本。不能够插入 null 值，同时，插入队列的对象必须是可比拟大小的（comparable），否则报 ClassCastException 异样。它的插入操作 put 办法不会 block，因为它是无界队列（take 办法在队列为空的时候会阻塞）。

4、DelayQueue

反对延时获取元素的无界阻塞队列。队列应用 PriorityBlockingQueue 来实现。队列中的元素必须实现 Delayed 接口，在创立元素时能够指定多久能力从队列中获取以后元素。只有在提早期满时能力从队列中提取元素。

5、SynchronousQueue

不存储元素的阻塞队列，每一个 put 必须期待一个 take 操作，否则不能持续增加元素。反对偏心拜访队列。

SynchronousQueue 能够看成是一个传球手，负责把生产者线程解决的数据间接传递给消费者线程。队列自身不存储任何元素，非常适合传递性场景。SynchronousQueue 的吞吐量高于 LinkedBlockingQueue 和 ArrayBlockingQueue。

6、LinkedTransferQueue

由链表构造组成的无界阻塞 TransferQueue 队列。绝对于其余阻塞队列，多了 tryTransfer 和 transfer 办法。

transfer 办法：如果以后有消费者正在期待接管元素（take 或者待工夫限度的 poll 办法），transfer 能够把生产者传入的元素立即传给消费者。如果没有消费者期待接管元素，则将元素放在队列的 tail 节点，并等到该元素被消费者生产了才返回。

tryTransfer 办法：用来试探生产者传入的元素是否间接传给消费者。如果没有消费者在期待，则返回 false。和上述办法的区别是该办法无论消费者是否接管，办法立刻返回。而 transfer 办法是必须等到消费者生产了才返回。

原理

JDK 应用告诉模式实现阻塞队列。所谓告诉模式，就是当生产者往满的队列里增加元素时会阻塞生产者，当消费者生产了一个队列中的元素后，会告诉生产者以后队列可用。

ArrayBlockingQueue 应用 Condition 来实现：

private final Condition notEmpty;
private final Condition notFull;

public ArrayBlockingQueue(int capacity, boolean fair) {if (capacity <= 0)
        throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();}

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {while (count == 0) // 队列为空时，阻塞以后消费者
            notEmpty.await();
        return dequeue();} finally {lock.unlock();
    }
}

public void put(E e) throws InterruptedException {checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {while (count == items.length)
            notFull.await();
        enqueue(e);
    } finally {lock.unlock();
    }
}

private void enqueue(E x) {final Object[] items = this.items;
    items[putIndex] = x;
    if (++putIndex == items.length)
          putIndex = 0;
     count++;
     notEmpty.signal(); // 队列不为空时，告诉消费者获取元素}

文章对你有用的话，点个赞，反对一下~

我是大彬，非科班转码，校招拿了多家互联网中大厂 offer，专一分享 Java 技术干货，欢送关注~

正文完
java
发表至： java
2022-01-06
 0
关于java:AREX-Agent-源码解读之全链路跟踪和-Mock-数据读写
一文系列一文了解java常用集合类含源码
关于java:通过Google-Cloud-StorageGCS管理Terraform的状态State
关于java:JAVA并发编程线程池原理使用和参数设置详解