Java集合知识

阅读 1

2020-11-25

1、ArrayList和LinkedList、vector 不同

ArrayList底层是数组结构，查询快，增删慢，线程不安全，效率高。
LinkedList底层是链表数据结构，查询慢，增删快，线程不安全，效率高。
Vector底层是数组结构，查询快，增删慢，线程安全，效率低。

Vector与ArrayList唯一的区别是，Vector是线程安全的

2、ArrayList的扩容机制

ArrayList 的底层是数组队列，相当于动态数组。与Java 中的数组相比，它的容量能动态增长。初始化长度是10的数组，当10个已满时会扩容1.5倍，每次扩容是通过arrayCopy的方式进行扩容。

改成线程安全的用
protected static List<Object> safeArrayList = Collections.synchronizedList(new ArrayList<Object>());

3、HashMap、HashTable、ConcurrentHashMap 不同

HashMap 是线程不安全的 key和value都允许为null，Java 1.5版本引入
HashTable 是线程安全的 key和value不允许为null，Java 1.2版本引入
ConcurrentHashMap 是线程安全的HashMap。它是把一个集合分成了n段(默认16)，每一段其实就是一个HashTable。HashTable是放对象的时候把对象加锁。ConcurrentHashMap是通过hash算法计算放入的对象在哪一段，然后把这一段加锁。所有效率会很高。

HashMap 初始16 超过75% 就会触发扩容机制 newsize = oldsize*2
HashTable 初始默认容量为 11，默认填充率为 0.75。newsize = oldsize*2 1
都是在插入后计算扩容所以如果计算前扩容了又没有新的元素进来就会出现无效扩容。
ConcurrentHashMap，默认初始容量等于 16 默认填充率等于 0.75
超过75% 就会触发扩容机制 newsize = oldsize*2分段加锁，扩容加锁

4、ConcurrentHashMap原理

ConcurrentHashMap是一种强大的数据结构，可以对数据进行快速、线程安全的操作。
该映射的工作原理是允许每个线程安全地访问和修改数据，而不必担心其他线程的干扰。
这是通过使用一种特殊的锁定机制实现的，该机制一次只允许一个线程访问数据。
这种锁定机制称为分段锁。它的工作原理是将数据分成小段，然后允许每个线程一次锁定一个段。这样，多个线程可以同时处理数据，但它们永远不会同时处理相同的数据。
分段锁是使用称为ReentrantLock的特殊 Java 类实现的。ReentrantLock是一个强大的同步工具，它允许线程安全地锁定数据结构。它被许多 Java 类使用，包括ConcurrentHashMap。
ReentrantLock类有两个主要方法：lock()和unlock()。当线程调用lock()时，它将尝试获取数据结构的锁。如果锁可用，线程将获得它，然后可以安全地访问和修改数据。
在没有锁的情况下，线程将等待直到另一个线程释放它。一旦线程获得了锁，它就可以执行临界区代码，然后通过调用unlock()方法释放它。
ReentrantLock类还有一个tryLock ()方法，它允许线程无需等待就可以尝试获取锁。这在您不想在锁不可用时阻塞其他线程的情况下很有用。

在JDK1.8中
JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组链表红黑树的实现方式来设计，内部大量采用CAS操作
Put流程
1. 如果没有初始化就先调用initTable（）方法来进行初始化过程
2. 如果没有hash冲突就直接CAS插入
3. 如果还在进行扩容操作就先进行扩容
4. 如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，
5. 最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环
6. 如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容

5、HashSet实现原理和去重原理

依赖两个方法：hashCode()和equals()
执行顺序：
    首先比较哈希值是否相同
        相同：继续执行equals()方法
               返回true：元素已存在，不添加
               返回false：元素不存在，把元素添加到集合
        不同：就把元素添加到集合

6、CopyOnWriteArrayList原理

CopyOnWriteArrayList类是在JDK 1.5中引入的，它实现了List接口。
它是ArrayList 的增强版本，其中所有修改（添加、设置、删除等）都是通过制作新副本来实现的。它位于java.util.concurrent包中。它是为在并发环境中使用而创建的数据结构。
顾名思义，CopyOnWriteArrayList 创建底层 ArrayList 的克隆副本，对于特定点的每个更新操作，两者都会自动同步，由 JVM 负责。因此，对正在执行读取操作的线程没有影响。
使用成本很高，因为每次更新操作都会创建一个克隆副本。因此，如果我们的频繁操作是读取操作，CopyOnWriteArrayList 是最佳选择。

通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。
这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

7、TreeMap

Java TreeMap 类是一个基于红黑树的实现。它提供了一种按排序顺序存储键值对的有效方法。

TreeMap与AbstractMap类一起用于实现Map接口和NavigableMap 。映射根据其键的自然顺序进行排序，或者根据使用的构造函数在映射创建时提供的比较器进行排序。这被证明是排序和存储键值对的有效方式。treemap 维护的存储顺序必须与 equals 一致，就像任何其他排序的 map 一样，无论显式比较器如何。树图实现不是同步的，因为如果一个映射被多个线程同时访问，并且至少有一个线程在结构上修改了该映射，则它必须在外部进行同步。
其中AbstractMap表明TreeMap为一个Map即支持key-value的集合 NavigableMap则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法。
内部通过comparator比较器来完成比较。

8、常用List集合初始化方式

8.1 先创建List再赋值

先创建集合对象，然后逐个调用add方法初始化。

import java.util.ArrayList;
import java.util.List;

public class TestList {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");

    }
}

8.2 使用Arrays.asList

使用Arrays的静态方法asList初始化。返回的list集合是不可变的！

import java.util.Arrays;
import java.util.List;

public class TestList2 {
    public static void main(String[] args) {
       List<Integer> integerList = Arrays.asList(1, 2, 3);
    }
}

8.3 使用Java 8的新特性 Stream

使用JDK8引入的Stream的of方法生成一个stream对象，调用collect方法进行收集，形成一个List集合。

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class TestList3 {
    public static void main(String[] args) {
       List<Integer> integerList = Stream.of(1, 2, 3).collect(Collectors.toList());
    }
}

9、Comparable和Comparator区别

Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。而Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。

Comparable提供了单一的排序序列。换句话说，我们可以根据 id、name 和 price 等单个元素对集合进行排序。
Comparable 影响原始类，即修改了实际类。
Comparable 提供 compareTo() 方法对元素进行排序。
Comparable 存在于 java.lang 包中。
可以通过 Collections.sort(List) 方法对 Comparable 类型的列表元素进行排序。

Comparator 提供了多种排序顺序。换句话说，我们可以根据 id、name 和 price 等多个元素对集合进行排序。
Comparator不影响原始类，即不修改实际类。
Comparator 提供了compare() 方法来对元素进行排序。
Comparator 存在于java.util包中。
可以通过Collections.sort(List, Comparator)方法对 Comparator 类型的列表元素进行排序。

10、java8 Stream原理

Streams 支持对元素流进行函数式操作，流操作分为中间操作和终端操作，它们组合在一起形成流管道。流管道由源（例如集合、数组、生成器函数或 I/O 通道）组成；后跟零个或多个中间操作，
中间操作返回一个新流。他们总是懒惰；执行诸如 filter() 之类的中间操作实际上并不执行任何过滤，而是创建一个新流，该流在遍历时包含与给定谓词匹配的初始流的元素。管道源的遍历直到管道的结束操作被执行后才开始。
中间操作又可以分为无状态（Stateless）操作与有状态（Stateful）操作，前者是指元素的处理不受之前元素的影响；后者是指该操作只有拿到所有元素之后才能继续下去。
Stream 内部分成三步
一、创建Stream
从一个数据源，如集合、数组中获取流。
二、中间操作
一个操作的中间链，对数据源的数据进行操作。
三、终止操作
一个终止操作，执行中间操作链，并产生结果。

11、Weakhashmap

WeakHashMap 是 Map 接口的实现，它只存储对其键的弱引用。仅存储弱引用允许键值对在其键不再在 WeakHashMap 之外引用时被垃圾收集。当任何线程不再可以访问其键时，条目的效用就会消失。
弱引用- 如果对对象的唯一引用是弱引用，垃圾收集器可以随时回收对象的内存。它不必等到系统内存耗尽。通常，它会在下次垃圾收集器运行时被释放。

为什么需要WeakHashMap
WeakHashMap正是由于使用的是弱引用，因此它的对象可能被随时回收。更直观的说，当使用 WeakHashMap 时，即使没有删除任何元素，它的尺寸、get方法也可能不一样。

上一篇： JAVA知识 Java8新特性

下一篇：Java多线程

类别