Java集合面试篇-EW帮帮网

ArrayList是容量可变的非线程安全列表，其底层使用数组实现。当几何扩容时，会创建更大的数组，并把原数组复制到新数组。ArrayList支持对元素的快速随机访问，但插入与删除速度很慢。
LinkedList本质是一个双向链表，与ArrayList相比，，其插入和删除速度更快，但随机访问速度更慢。

Set不允许存在重复的元素，与List不同，set中的元素是无序的。常用的实现有HashSet，LinkedHashSet和TreeSet。

HashSet通过HashMap实现，HashMap的Key即HashSet存储的元素，所有Key都是用相同的Value，一个名为PRESENT的Object类型常量。使用Key保证元素唯一性，但不保证有序性。由于HashSet是HashMap实现的，因此线程不安全。
LinkedHashSet继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。
TreeSet通过TreeMap实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。

Map 是一个键值对集合，存储键、值和之间的映射。Key 无序，唯一；value 不要求有序，允许重复。Map 没有继承于 Collection 接口，从 Map 集合中检索元素时，只要给出键对象，就会返回对应的值对象。主要实现有TreeMap、HashMap、HashTable、LinkedHashMap、ConcurrentHashMap

HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突），JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
HashTable：数组+链表组成的，数组是 HashTable 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap：红黑树（自平衡的排序二叉树）
ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

1.3.Java中的线程安全的集合是什么？

在 java.util 包中的线程安全的类主要 2 个，其他都是非线程安全的。

Vector：线程安全的动态数组，其内部方法基本都经过synchronized修饰，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
Hashtable：线程安全的哈希表，HashTable 的加锁方法是给每个方法加上 synchronized 关键字，这样锁住的是整个 Table 对象，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用，如果要保证线程安全的哈希表，可以用ConcurrentHashMap。

java.util.concurrent 包提供的都是线程安全的集合：

并发Map：

ConcurrentHashMap：它与 HashTable 的主要区别是二者加锁粒度的不同，在JDK1.7，ConcurrentHashMap加的是分段锁，也就是Segment锁，，每个Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。在JDK 1.8 ，它取消了Segment字段，直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率。对于put操作，如果Key对应的数组元素为null，则通过CAS操作（Compare and Swap）将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。
ConcurrentSkipListMap：实现了一个基于SkipList（跳表）算法的可排序的并发集合，SkipList是一种可以在对数预期时间内完成搜索、插入、删除等操作的数据结构，通过维护多个指向其他元素的“跳跃”链接来实现高效查找。

1.4.集合遍历的方法有哪些？

在Java中，集合的遍历方法主要有以下几种：

普通 for 循环： 可以使用带有索引的普通 for 循环来遍历 List。
增强 for 循环（for-each循环）： 用于循环访问数组或集合中的元素。
Iterator 迭代器： 可以使用迭代器来遍历集合，特别适用于需要删除元素的情况。
ListIterator 列表迭代器：ListIterator是迭代器的子类，可以双向访问列表并在迭代过程中修改元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

ListIterator<String> listIterator=list.listIterator();
while(listIterator.hasNext()) {
   String element = listIterator.next();
   System.out.println(element);
}

使用 forEach 方法： Java 8引入了 forEach 方法，可以对集合进行快速遍历。

Stream API： Java 8的Stream API提供了丰富的功能，可以对集合进行函数式操作，如过滤、映射等。

2.List

常见的List集合（非线程安全）：

ArrayList基于动态数组实现，它允许快速的随机访问，即通过索引访问元素的时间复杂度为 O (1)。在添加和删除元素时，如果操作位置不是列表末尾，可能需要移动大量元素，性能相对较低。适用于需要频繁随机访问元素，而对插入和删除操作性能要求不高的场景，如数据的查询和展示等。
LinkedList基于双向链表实现，在插入和删除元素时，只需修改链表的指针，不需要移动大量元素，时间复杂度为 O (1)。但随机访问元素时，需要从链表头或链表尾开始遍历时间复杂度为 O (n)。适用于需要频繁进行插入和删除操作的场景，如队列、栈等数据结构的实现，以及需要在列表中间频繁插入和删除元素的情况。

常见的List集合（线程安全）：

Vector和ArrayList类似，也是基于数组实现。Vector中的方法大多是同步的，这使得它在多线程环境下可以保证数据的一致性，但在单线程环境下，由于同步带来的开销，性能会略低于ArrayList。
CopyOnWriteArrayList在对列表进行修改（如添加、删除元素）时，会创建一个新的底层数组，将修改操作应用到新数组上，而读操作仍然在原数组上进行，这样可以保证读操作不会被写操作阻塞实现了读写分离，提高了并发性能。适用于读操作远远多于写操作的并发场景，如事件监听列表等，在这种场景下可以避免大量的锁竞争，提高系统的性能和响应速度。

2.1.list可以一边遍历一边修改元素吗？

在 Java 中，List在遍历过程中是否可以修改元素取决于遍历方式和具体的List实现类，以下是几种常见情况：

使用普通for循环遍历：可以在遍历过程中修改元素，只要修改的索引不超出List的范围即可。

使用foreach循环遍历：一般不建议在foreach循环中直接修改正在遍历的List元素，因为这可能会导致意外的结果或ConcurrentModificationException异常。在foreach循环中修改元素可能会破坏迭代器的内部状态，因为foreach循环底层是基于迭代器实现的，在遍历过程中修改集合结构，会导致迭代器的预期结构和实际结构不一致。

使用迭代器遍历：可以使用迭代器的remove方法来删除元素，但如果要修改元素的值，需要通过迭代器的set方法来进行，而不是直接通过List的set方法，否则也可能会抛出ConcurrentModificationException异常。

对于线程安全的List，如CopyOnWriteArrayList，由于其采用了写时复制的机制，，在遍历的同时可以进行修改操作，不会抛出ConcurrentModificationException异常，但可能会读取到旧的数据，因为修改操作是在新的副本上进行的。

2.2.Arraylist和LinkedList的区别，哪个集合是线程安全的？

ArrayList和LinkedList都是Java中常见的集合类，它们都实现了List接口。

底层数据结构不同：ArrayList使用数组实现，通过索引进行快速访问元素。LinkedList使用链表实现，通过节点之间的指针进行元素的访问和操作。
插入和删除操作的效率不同：ArrayList在尾部的插入和删除操作效率较高，但在中间或开头的插入和删除操作效率较低，需要移动元素。LinkedList在任意位置的插入和删除操作效率都比较高，因为只需要调整节点之间的指针，但是LinkedList是不支持随机访问的，所以除了头结点外插入和删除的时间复杂度都是0(n)，效率也不是很高所以LinkedList基本没人用。
随机访问的效率不同：ArrayList支持通过索引进行快速随机访问，时间复杂度为O(1)。LinkedList需要从头或尾开始遍历链表，时间复杂度为O(n)。
空间占用：ArrayList在创建时需要分配一段连续的内存空间，因此会占用较大的空间。LinkedList每个节点只需要存储元素和指针，因此相对较小。
使用场景：ArrayList适用于频繁随机访问和尾部的插入删除操作，而LinkedList适用于频繁的中间插入删除操作和不需要随机访问的场景。
线程安全：这两个集合都不是线程安全的，Vector是线程安全的。

2.3.ArrayList线程安全吗？把ArrayList变成线程安全有哪些方法？

不是线程安全的，ArrayList变成线程安全的方式有：

使用Collections类的synchronizedList方法将ArrayList包装成线程安全的List：

使用CopyOnWriteArrayList类代替ArrayList，它是一个线程安全的List实现：

使用Vector类代替ArrayList，Vector是线程安全的List实现：

2.4为什么ArrayList不是线程安全的，具体来说是哪里不安全？

在高并发添加数据下，ArrayList会暴露三个问题;

部分值为null（我们并没有add null进去）
索引越界异常
size与我们add的数量不符

为了知道这三种情况是怎么发生的，ArrayList，add 增加元素的代码如下：

ensureCapacityInternal()这个方法的详细代码我们可以暂时不看，它的作用就是判断如果将当前的新元素加到列表后面，列表的elementData数组的大小是否满足，如果size + 1的这个需求长度大于了elementData这个数组的长度，那么就要对这个数组进行扩容。

大体可以分为三步：

判断数组需不需要扩容，如果需要的话，调用grow方法进行扩容；
将数组的size位置设置值（因为数组的下标是从0开始的）；
将当前集合的大小加1

下面我们来分析三种情况都是如何产生的：

部分值为null：当线程1走到了扩容那里发现当前size是9，而数组容量是10，所以不用扩容，这时候cpu让出执行权，线程2也进来了，发现size是9，而数组容量是10，所以不用扩容，这时候线程1继续执行，将数组下标索引为9的位置set值了，还没有来得及执行size++，这时候线程2也来执行了，又把数组下标索引为9的位置set了一遍，这时候两个先后进行size+++，导致下标索引10的地方就为null了。
索引越界异常：线程1走到扩容那里发现当前size是9，数组容量是10不用扩容，cpu让出执行权，线程2也发现不用扩容，这时候数组的容量就是10，而线程1 set完之后size++，这时候线程2再进来size就是10，数组的大小只有10，而你要设置下标索引为10的就会越界（数组的下标索引从0开始）；
size与我们add的数量不符：这个基本上每次都会发生，这个理解起来也很简单，因为size++本身就不是原子操作，可以分为三步：获取size的值，将size的值加1，将新的size值覆盖掉原来的，线程1和线程2拿到一样的size值加完了同时覆盖，就会导致一次没有加上，所以肯定不会与我们add的数量保持一致的；

2.5.ArrayList的扩容机制说一下

ArrayList在添加元素时，如果当前元素个数已经达到了内部数组的容量上限，就会触发扩容操作。ArrayList的扩容操作主要包括以下几个步骤：

计算新的容量：一般情况下，新的容量会扩大为原容量的1.5倍在JDK 10之后，扩容策略做了调整），然后检查是否超过了最大容量限制。
创建新的数组：根据计算得到的新容量，创建一个新的更大的数组。
将元素复制：将原来数组中的元素逐个复制到新数组中。
更新引用：将ArrayList内部指向原数组的引用指向新数组。
完成扩容：扩容完成后，可以继续添加新元素。

2.6.线程安全的 List， CopyonWriteArraylist是如何实现线程安全的？

CopyOnWriteArrayList底层也是通过一个数组保存数据，使用volatile关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。

在写入操作时，加了一把互斥锁ReentrantLock以保证线程安全。

看到源码可以知道写入新元素时，首先会先将原来的数组拷贝一份并且让原来数组的长度+1后就得到了一个新数组，新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度，然后将新加入的元素放置都在新数组最后一个位置后，用新数组的地址替换掉老数组的地址就能得到最新的数据了。在我们执行替换地址操作之前，读取的是老数组的数据，数据是有效数据；执行替换地址操作之后，读取的是新数组的数据，同样也是有效数据，而且使用该方式能比读写都加锁要更加的效率。现在我们来看读操作，读是没有加锁的，所以读是一直都能读

3.Map

常见的Map集合（非线程安全）：

HashMap是基于哈希表实现的Map，它根据键的哈希值来存储和获取键值对，JDK 1.8中是用数组+链表+红黑树来实现的。HashMap是非线程安全的，在多线程环境下，当多个线程同时对HashMap进行操作时，可能会导致数据不一致或出现死循环等问题。

LinkedHashMap继承自HashMap，它在HashMap的基础上，使用双向链表维护了键值对的插入顺序或访问顺序，使得迭代顺序与插入顺序或访问顺序一致。。由于它继承自HashMap，在多线程并发访问时，同样会出现与HashMap类似的线程安全问题。

TreeMap是基于红黑树实现的Map，它可以对键进行排序，默认按照自然顺序排序，也可以通过指定的比较器进行排序。TreeMap是非线程安全的，在多线程环境下，如果多个线程同时对TreeMap进行插入、删除等操作，可能会破坏红黑树的结构，导致数据不一致或程序出现异常。

常见的Map集合（线程安全）：

Hashtable是早期 Java 提供的线程安全的Map实现，它的实现方式与HashMap类似，但在方法上使用了synchronized关键字来保证线程安全。通过在每个可能修改Hashtable状态的方法上加上synchronized关键字，使得在同一时刻，只能有一个线程能够访问Hashtable的这些方法，从而保证了线程安全。
ConcurrentHashMap在 JDK 1.8 以前采用了分段锁等技术来提高并发性能。在ConcurrentHashMap中，将数据分成多个段（Segment），每个段都有自己的锁。在进行插入、删除等操作时，只需要获取相应段的锁，而不是整个Map的锁，这样可以允许多个线程同时访问不同的段，提高了并发访问的效率。在 JDK 1.8 以后是通过 volatile + CAS 或者 synchronized 来保证线程安全的。

3.1.volatile关键字

volatile 是 Java 中的一个关键字，用于修饰变量。它的主要作用是确保一个变量在多个线程之间的可见性，并禁止对该变量的指令重排优化。volatile 关键字是 Java 内存模型（JMM）中的一部分，它在多线程编程中起到了重要作用，尤其是在保证变量的共享数据在不同线程之间的一致性时。

volatile 的作用：

可见性（Visibility）：当一个线程修改了 volatile 变量的值，其他线程能够立即看到这个修改。
禁止指令重排（Prevention of Instruction Reordering）：volatile 变量会禁止 JVM 和硬件对其进行指令重排，确保在多线程环境中操作的顺序性。

2. volatile 变量的可见性

在没有 volatile 修饰符的情况下，每个线程都有可能在自己的工作内存中缓存变量的值。当一个线程修改了共享变量的值，其他线程未必能立即看到这个变化。而使用 volatile 关键字时，Java 保证每次访问 volatile 变量时，都会从主内存中读取该变量，而不是从线程的本地缓存中读取。因此，当一个线程修改了 volatile 变量的值，其他线程可以立即看到更新后的值。

public class VolatileExample {
    private static volatile boolean flag = false;

    public static void main(String[] args) throws InterruptedException {
        // 线程1
        new Thread(() -> {
            while (!flag) {
                // 等待flag变为true
            }
            System.out.println("Thread 1 finished waiting.");
        }).start();

        // 线程2
        new Thread(() -> {
            try {
                Thread.sleep(1000);  // 睡眠1秒
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            flag = true;  // 修改flag的值
            System.out.println("Thread 2 updated flag to true.");
        }).start();
    }
}

在这个例子中，flag 变量被 volatile 修饰，因此当线程2将 flag 设置为 true 时，线程1能够立即看到这个变化，停止等待。

3. volatile 的禁止指令重排

指令重排是编译器和处理器为了提高程序执行效率，可能会对程序中的指令进行优化和调整执行顺序。这样可能会导致多线程中看似顺序执行的代码出现问题，特别是在操作共享变量时。使用 volatile 可以禁止对该变量的指令重排。它确保所有对 volatile 变量的写操作，都在前面所有的操作完成之后才执行；同时，所有对 volatile 变量的读操作，都在后面所有的操作之前执行。

4. volatile 不保证原子性

尽管 volatile 可以确保变量的可见性，但它并不保证对该变量操作的原子性。例如，对于 volatile 变量的复合操作（如 x++），它仍然不是原子性的，因为 x++ 是读取、修改、写回的组合操作。如果多个线程并发地执行类似操作，可能会出现竞争条件。

private static volatile int counter = 0;

public static void main(String[] args) throws InterruptedException {
    // 创建多个线程进行并发操作
    for (int i = 0; i < 1000; i++) {
        new Thread(() -> counter++).start();
    }

    // 给线程执行一定时间
    Thread.sleep(2000);

    // 期望值是 1000，但是可能会输出其他结果
    System.out.println("Counter: " + counter);
}

在上面的例子中，尽管 counter 是 volatile 变量，多个线程对它的 ++ 操作仍然可能导致竞争条件，最终的输出可能不是预期的 1000。如果需要保证原子性操作，应该使用 synchronized 或者其他并发工具（如 AtomicInteger）。

5. 适用场景

volatile 最适合用于以下场景：

标志位：例如，多个线程需要检查一个共享变量的值，决定是否退出循环或者进行某些操作（如终止任务）。
单例模式：在实现单例模式时，volatile 可用于保证实例对象的正确初始化。

3.2.乐观锁

乐观锁（Optimistic Locking）是一种并发控制策略，在多线程环境中常用于保证数据的一致性和完整性。与悲观锁（Pessimistic Locking）不同，乐观锁假设数据在大多数情况下不会发生冲突，因此在进行操作时并不加锁，而是在操作完成后通过某种机制来检查是否发生了并发冲突。只有在发现冲突时，才会进行相应的处理。

1. 乐观锁的基本概念

乐观锁的核心思想是：假设在进行更新操作时，其他线程不会修改相同的数据。因此，在操作过程中，乐观锁并不直接加锁，而是允许多个线程同时读取和操作数据。当一个线程准备提交更改时，它会检查在此期间是否有其他线程修改了数据，如果有修改，则会回滚或重试操作；如果没有修改，线程就会成功提交更新。

这种策略的优点是避免了过多的锁竞争，提高了性能，特别是在并发读取多而更新少的场景下。

2. 乐观锁的实现方式

乐观锁的常见实现方式是使用 版本号（version number） 或 时间戳（timestamp） 来检测数据是否发生了修改。常见的两种方式如下：

2.1. 版本号控制

每个数据行（记录）都有一个版本号，每次修改数据时，都会更新这个版本号。操作步骤如下：

读取数据：线程从数据库或共享资源中读取数据，并获取版本号。
修改数据：线程对数据进行修改，但不加锁。
提交数据：线程在提交修改时，检查数据的版本号是否发生变化。如果版本号没有变化，说明没有其他线程修改数据，当前线程可以提交更新；如果版本号发生变化，说明数据已被其他线程修改，当前线程需要回滚或重试。

2.2. 时间戳控制

时间戳控制与版本号控制类似，每次数据修改时都会更新一个时间戳。时间戳用于检查数据是否发生了变化。

3. 乐观锁的优缺点

优点：

提高并发性：乐观锁适合于读多写少的场景，因为它不会在读取过程中加锁，减少了线程之间的锁竞争。
避免死锁：由于不需要显式地加锁，乐观锁避免了由于锁资源竞争而导致的死锁问题。
效率较高：在没有冲突的情况下，乐观锁能避免频繁加锁带来的性能损失，尤其是在高并发环境中。

缺点：

冲突处理复杂：如果多个线程频繁地更新相同数据，乐观锁会频繁地检测到冲突，需要重试操作，这可能导致效率下降。
不适合写多的场景：在写操作频繁的情况下，乐观锁的重试机制可能会导致性能瓶颈，因为每次写操作后都需要检查版本号或时间戳。

4. 乐观锁的应用场景

乐观锁适用于以下场景：

高并发读操作：当应用中读操作远多于写操作时，乐观锁能够提供较好的性能。
少量冲突：如果并发冲突的概率较低，使用乐观锁可以避免锁的开销，提高并发性能。
分布式系统：在分布式数据库中，乐观锁常用于处理并发更新问题，例如通过版本号或时间戳来实现。

5. 乐观锁与悲观锁的对比

6. 示例代码：乐观锁的版本号控制

以下是一个基于版本号控制的乐观锁示例：

public class OptimisticLockExample {
    static class Product {
        int id;
        String name;
        double price;
        int version; // 版本号

        public Product(int id, String name, double price, int version) {
            this.id = id;
            this.name = name;
            this.price = price;
            this.version = version;
        }
    }

    public static boolean updateProduct(Product product, double newPrice) {
        // 假设数据库中的产品数据已经被读取，并且版本号为 product.version
        int currentVersion = product.version;

        // 模拟修改操作
        product.price = newPrice;

        // 检查版本号是否一致，假设数据库中的版本号是 currentVersion
        if (product.version == currentVersion) {
            // 更新版本号并提交修改
            product.version++;  // 更新版本号
            System.out.println("Product updated successfully!");
            return true;  // 操作成功
        } else {
            System.out.println("Product has been modified by another thread. Retry.");
            return false;  // 操作失败，版本号冲突
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Product product = new Product(1, "Laptop", 1000.0, 1);

        // 线程1更新产品
        Thread thread1 = new Thread(() -> {
            try {
                // 等待模拟一下，让线程2有机会修改数据
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean success = updateProduct(product, 1200.0);
            if (success) {
                System.out.println("Thread 1 updated product.");
            }
        });

        // 线程2尝试更新产品
        Thread thread2 = new Thread(() -> {
            boolean success = updateProduct(product, 1300.0);
            if (success) {
                System.out.println("Thread 2 updated product.");
            }
        });

        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();
    }
}

解释：

线程1（thread1） 在尝试更新 Product 的价格时，稍微延迟了100ms，以便给线程2的操作留出时间。
线程2（thread2） 尝试修改 Product 的价格，并且检查版本号。
由于线程1在线程2之前更新了价格并提交了更新，线程2在其尝试提交更新时发现版本号已经改变，因此会检测到版本冲突，并返回更新失败。

这样，我们就能够看到乐观锁在多个线程并发修改数据时的更新失败情况。

3.3.如何对map进行快速遍历？

用for-each循环和entrySet()方法：这是一种较为常见和简洁的遍历方式，它可以同时获取Map中的键和值

使用for-each循环和keySet()方法：如果只需要遍历Map中的键，可以使用keySet()方法，这种方式相对简单，性能也较好。

使用 Lambda 表达式和forEach()方法：在 Java 8 及以上版本中，可以使用 Lambda 表达式和forEach()方法来遍历Map，这种方式更加简洁和函数式。

使用Stream API：Java 8 引入的Stream API也可以用于遍历Map，可以将Map转换为流，然后进行各种操作。

import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;

public class MapTraversalExample {
     public static void main(String[] args) {
          Map<String, Integer> map = new HashMap<>();
          map.put("key1", 1);
          map.put("key2", 2);
          map.put("key3", 3);

         // 使用Stream API遍历Map
         map.entrySet().stream()
           .forEach(entry -> System.out.println("Key: " + entry.getKey() + ", Value: "+ entry.getValue()));


       // 还可以进行其他操作，如过滤、映射等
       Map<String, Integer> filteredMap = map.entrySet().stream()
                                           .filter(entry -> entry.getValue() > 1)
                                           .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

       System.out.println(filteredMap);
 }
}

3.4.HashMap实现原理介绍一下？

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。

所以在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过8的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度O（log n），可以提高查询性能，但是在数量较少时，即数量小于6时，会将红黑树转换回链表。

3.5.了解的哈希冲突解决方法有哪些？

链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

3.6.HashMap是线程安全的吗？

hashmap不是线程安全的，hashmap在多线程会存在下面的问题：

JDK 1.7 HashMap 采用数组 + 链表的数据结构，多线程背景下，在数组扩容的时候，存在 Entry 链死循环和数据丢失问题。
JDK 1.8 HashMap 采用数组 + 链表 + 红黑二叉树的数据结构，优化了 1.7 中数组扩容的方案，解决了Entry 链死循环和数据丢失问题。但是多线程背景下，put 方法存在数据覆盖的问题。

如果要保证线程安全，可以通过这些方法来保证：

多线程环境可以使用Collections.synchronizedMap同步加锁的方式，还可以使用HashTable，但是同步的方式显然性能不达标，而ConurrentHashMap更适合高并发场景使用。
ConcurrentHashmap在JDK1.7和1.8的版本改动比较大，1.7使用Segment+HashEntry分段锁的方式实现，1.8则抛弃了Segment，改为使用CAS+synchronized+Node实现，同样也加入了红黑树，避免链表过长导致性能的问题。

3.7.hashmap的put过程介绍一下

HashMap HashMap的put()方法用于向HashMap中添加键值对，当调用HashMap的put()方法时，会按照以下详细流程执行（JDK8 1.8版本）：

第一步：根据要添加的键的哈希码计算在数组中的位置（索引）。

第二步：检查该位置是否为空（即没有键值对存在）

如果为空，则直接在该位置创建一个新的Entry对象来存储键值对。将要添加的键值对作为该Entry的键和值，并保存在数组的对应位置。将HashMap的修改次数（modCount）加1，以便在进行迭代时发现并发修改。

第三步：如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同？

如果相同，则表示找到了相同的键，直接将新的值替换旧的值，完成更新操作。

第四步：如果第一个键值对的哈希码和键不相同，则需要遍历链表或红黑树来查找是否有相同的键：

如果键值对集合是链表结构，从链表的头部开始逐个比较键的哈希码和equals()方法，直到找到相同的键或达到链表末尾。

如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
如果没有找到相同的键，则将新的键值对添加到链表的头部。

如果键值对集合是红黑树结构，在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。

如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
果没有找到相同的键，则将新的键值对添加到红黑树中。

第五步：检查链表长度是否达到阈值（默认为8）：

如果链表长度超过阈值，且HashMap的数组长度大于等于64，则会将链表转换为红黑树，以提高查询效率。

第六步：检查负载因子是否超过阈值（默认为0.75）：

如果键值对的数量（size）与数组的长度的比值大于阈值，则需要进行扩容操作。

第七步：扩容操作：

创建一个新的两倍大小的数组。
将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。
更新HashMap的数组引用和阈值参数。

第八步：完成添加操作。

此外，HashMap是非线程安全的，如果在多线程环境下使用，需要采取额外的同步措施或使用线程安全的ConcurrentHashMap。

3.8.hashmap 调用get方法一定安全吗？

不是，调用 get 方法有几点需要注意的地方：

空指针异常（NullPointerException）：如果你尝试用 null 作为键调用 get 方法，而 HashMap 没有被初始化（即为 null），那么会抛出空指针异常。不过，如果 HashMap 已经初始化，使用null 作为键是允许的，因为 HashMap 支持 null 键。
线程安全：HashMap 本身不是线程安全的。如果在多线程环境中，没有适当的同步措施，同时对HashMap 进行读写操作可能会导致不可预测的行为。例如，在一个线程中调用 get 方法读取数据，而另一个线程同时修改了结构（如增加或删除元素），可能会导致读取操作得到错误的结果或抛出ConcurrentModificationException。如果需要在多线程环境中使用似 HashMap 的数据结构考虑使用 ConcurrentHashMap

3.9.HashMap一般用什么做Key？为啥String适合做Key呢？

用 string 做 key，因为 String对象是不可变的，一旦创建就不能被修改，，这确保了Key的稳定性。如果Key是可变的，可能会导致hashCode和equals方法的不一致，进而影响HashMap的正确性。

3.10.为什么HashMap要用红黑树而不是平衡二叉树？

平衡二叉树追求的是一种 “完全平衡” 状态：任何结点的左右子树的高度差不会超过 1，优势是树的结点是很平均分配的。这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
红黑树不追求这种完全平衡状态，而是追求一种 “弱平衡” 状态：整个树最长路径不会超过最短路径的2 倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。

3.11.hashmap key可以为null吗？

可以为 null。

hashMap中使用hash()方法来计算key的哈希值,当key为空时，直接令key的哈希值为0，不走key.hashCode()方法；

hashMap虽然支持key和value为null，但是null作为key只能有一个，null作为value可以有多个；
因为hashMap中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个。

3.12.重写HashMap的equal和hashcode方法需要注意什么？

HashMap使用Key对象的hashCode()和equals方法去决定key-value对的索引。当我们试着从HashMap中获取值的时候，这些方法也会被用到。如果这些方法没有被正确地实现，这种情况下，两个不同Key也许会产生相同的hashCode()和equals()输出，HashMap将会认为它们是相同的然后覆盖它们，而非把它们存储到不同的地方。

同样的，所有不允许存储重复数据的集合类都使用hashCode()和equals()去查找重复，所以正确实现它们非常重要。equals()和hashCode()的实现应该遵循以下规则：

如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。
如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。

3.13.重写HashMap的equal方法不当会出现什么问题？

hashMap在比较元素时，会先通过hashCode进行比较，相同的情况下再通过equals进行比较。所以 equals相等的两个对象，hashCode一定相等。hashCode相等的两个对象，equals不一定相等（比如散列冲突的情况）

重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，，而hashCode方法却返回false，这样的一个后果会导致在hashmap等类中存储多个一模一样的对象，导致出现覆盖存储的数据的问题，这与hashmap只能有唯一的key的规范不符合。

3.14.列举HashMap在多线程下可能会出现的问题？

JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。

3.15.HashMap的扩容机制介绍一下

hashMap默认的负载因子是0.75，即如果hashmap中的元素个数超过了总容量75%，则会触发扩容，扩容分为两个步骤：

第1步是对哈希表长度的扩展（2倍）
第2步是将旧哈希表中的数据放到新的哈希表中。

因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。如我们从16扩展为32时，具体的变化如下所示：

因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

3.16.HashMap的大小为什么是2的n次方大小呢？

在 JDK1.7 中，HashMap 整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的 hash 值计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。而在 JDK 1.8 中，HashMap 对扩容操作做了优化。由于扩容数组的长度是 2 倍关系，所以对于假设初始tableSize = 4 要扩容到 8 来说就是 0100 到 1000 的变化（左移一位就是 2 倍），在扩容中只用判断原来的 hash 值和左移动的一位（newtable 的值）按位与操作是 0 或 1 就行，0 的话索引不变，1 的话索引变成原索引加上扩容前数组。

之所以能通过这种“与运算“来重新分配索引，是因为 hash 值本来就是随机的，而 hash 按位与上newTable 得到的 0（扩容前的索引位置）和 1扩容前索引位置加上扩容前数组长度的数值索引处）就是随机的，所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。

3.17.往hashmap存20个元素，会扩容几次？

当插入 20 个元素时，HashMap 的扩容过程如下：

初始容量：16

插入第 1 到第 12 个元素时，不需要扩容。
插入第 13 个元素时，达到负载因子限制，需要扩容。此时，HashMap 的容量从 16 扩容到 32。

扩容后的容量：32

插入第 14 到第 24 个元素时，不需要扩容。

因此，总共会进行一次扩容。

3.18.说说hashmap的负载因子

HashMap 负载因子 loadFactor 的默认值是 0.75，当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。默认负载因子为 0.75，是因为它提供了空间和时间复杂度之间的良好平衡。

负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。

在哈希表中，负载因子（Load Factor）是衡量哈希表当前存储的元素数量与哈希表容量之间的比例。负载因子的计算公式为：

负载因子是一个重要的性能指标，它影响哈希表的查找效率。如果负载因子过高，意味着哈希表中的元素较多，可能导致哈希冲突频繁，进而影响查找和插入操作的效率。通常，当负载因子超过某个阈值时，哈希表会进行扩容。

3.19.Hashmap和Hashtable有什么不一样的？Hashmap一般怎么用？

HashTable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。
HashMap线程不安全，效率高一点，可以存储null的key和value，null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为8）先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。

3.20.ConcurrentHashMap怎么实现的？

在 JDK 1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组HashEntry。 Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。

JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap 虽然是线程安全的，但因为它的底层实现是数组 + 链表的形式，所以在数据比较多的情况下访问是很慢的，因为要遍历整个链表，而 JDK 1.8 则使用了数组 + 链表/红黑树的方式优化了 ConcurrentHashMap 的实现，具体实现结构如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：

如果为空则使用 volatile 加 CAS 来初始化
如果容器不为空，则根据存储的元素计算该位置是否为空。

如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

如果把上面的执行用一句话归纳的话，就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。

而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度。

3.21.分段锁怎么加锁的？

在 ConcurrentHashMap 中，将整个数据结构分为多个 Segment，每个 Segment 都类似于一个小的HashMap，每个 Segment 都有自己的锁，不同 Segment 之间的操作互不影响，从而提高并发性能。

在 ConcurrentHashMap 中，对于插入、更新、删除等操作，需要先定位到具体的 Segment然后再在该Segment 上加锁，而不是像传统的 HashMap 一样对整个数据结构加锁。这样可以使得不同 Segment 之间的操作并行进行，提高了并发性能。

3.22.分段锁是可重入的吗？

JDK 1.7 ConcurrentHashMap中的分段锁是用了 ReentrantLock，是一个可重入的锁（是指一个线程可以多次获得同一把锁，而不会造成死锁的锁。换句话说，如果一个线程已经持有了某个锁，那么它可以再次请求并成功获取这个锁，而不需要等待自己释放锁。这种特性使得同一线程在多次调用一个已经获得的锁时，可以顺利进行，而不必因为自己已经持有锁而被阻塞。）。

3.23.已经用了synchronized，为什么还要用CAS呢？

ConcurrentHashMap使用这两种手段来保证线程安全主要是一种权衡的考虑，在某些操作中使用synchronized，还是使用CAS，主要是根据锁竞争程度来判断的。

比如：在putVal中，如果计算出来的hash槽没有存放元素，那么就可以直接使用CAS来进行设置值，这是因为在设置元素的时候，因为hash值经过了各种扰动后，造成hash碰撞的几率较低，那么我们可以预测使用较少的自旋来完成具体的hash落槽操作。

当发生了hash碰撞的时候说明容量不够用了或者已经有大量线程访问了，因此这时候使用synchronized来处理hash碰撞比CAS效率要高，因为发生了hash碰撞大概率来说是线程竞争比较强烈。

3.24.ConcurrentHashMap用了悲观锁还是乐观锁?

悲观锁和乐观锁都有用到。

添加元素时首先会判断容器是否为空：

如果为空则使用 volatile 加 CAS （乐观锁） 来初始化。
如果容器不为空，则根据存储的元素计算该位置是否为空。
如果根据存储的元素计算结果为空，则利用 CAS（乐观锁） 设置该节点；
如果根据存储的元素计算结果不为空，则使用 synchronized（悲观锁） ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

3.25.说一下HashMap和Hashtable、ConcurrentMap的区别

HashMap线程不安全，效率高一点，可以存储null的key和value，null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为8），先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
HashTable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。
ConcurrentHashMap是Java中的一个线程安全的哈希表实现，它可以在多线程环境下并发地进行读写操作，而不需要像传统的HashTable那样在读写时加锁。ConcurrentHashMap的实现原理主要基于分段锁和CAS操作。它将整个哈希表分成了多Segment（段），每个Segment都类似于一个小的HashMap，它拥有自己的数组和一个独立的锁。在ConcurrentHashMap中，读操作不需要锁，可以直接对Segment进行读取，而写操作则只需要锁定对应的而不是整个哈希表，这样可以大大提高并发性能。

4.Set

4.1.Set集合有什么特点？如何实现key无重复的？

set集合特点：Set集合中的元素是唯一的，不会出现重复的元素。
set实现原理：Set集合通过内部的数据结构（如哈希表、红黑树等）来实现key的无重复,当向Set集合中插入元素时，会先根据元素的hashCode值来确定元素的存储位置，然后再通过equals方法来判断是否已经存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性。

4.2.有序的Set是什么？记录插入顺序的集合是什么？

有序的 Set 是TreeSet和LinkedHashSet。TreeSet是基于红黑树实现，保证元素的自然顺序。LinkedHashSet是基于双重链表和哈希表的结合来实现元素的有序存储保证元素添加的自然顺序
记录插入顺序的集合通常指的是LinkedHashSet，它不仅保证元素的唯一性，还可以保持元素的插入顺序。当需要在Set集合中记录元素的插入顺序时，可以选择使用LinkedHashSet来实现。

Java集合面试篇

1.概念

1.1.数组与集合的区别，用过哪些？

1.2.说说Java中的集合？