面经-集合

集合的分类

Java中的集合类主要分为两大类: Collection接口（单列集合）和Map接口（双列集合）；前者是存储对象的集合类，后者存储的是键值对(key-value)的集合类

Collection接口下又分为List、Set和Queue接口，每个接口有其具体实现类， Map接口下有很多接口，比如HashMap，LinkedHashMap， TreeMap， Hashtable， ConcurrentHashMap

• List下有ArrayList (基于动态数组，查询速度快，插入、删除慢) ， LinkedList (基于双向链表，插入、删除快，查询速度慢) 和vector;
• Set下有HashSet (基于哈希表，元素无序，不允许重复) ， LinkedHashSet (基于链表和哈希表，维护插入顺序，不允许重复) ，TreeSet (基于红黑树，元素有序，不允许重复) ;

Map 接口：存储的是键值对，也就是给对象（value）设置了一个 key，这样通过 key 可以找到那个 value。

• HashMap：基于哈希表，键值对无序，不允许键重复。LinkedHashMap：基于链表和哈希表，维护插入顺序，不允许键重复。
• TreeMap：基于红黑树，键值对有序，不允许键重复。

Collection（List）

ArrayList集合底层结构是什么

Object数组

在List集合中删除元素的注意事项

反向遍历

ArrayList、LinkedList、Vector的区别

ArrayList

A：底层结构是数组（查询快、增删慢）

B：线程不安全、效率高

LinkedList

A：底层结构是链表（查询慢、增删快）

B：线程不安全、效率高

Vector

A：底层结构是数组（查询慢、增删慢）

B：线程安全、效率低

ArrayList集合的扩容机制

如果第一次使用无参构造，那么第一次添加元素的时候会扩容成长度为10的数组，当添加的元素超过数组的长度时，按照1.5倍扩容

int newCapacity = oldCapacity + (oldCapacity >> 1);

List的应用场景

​ 批量查询全部部门数据时，需要使用List集合

/**
* 查询全部部门数据
* @return
*/
List<Dept> list();

Collection（Set）

HashSet、LinkedHashSet、TreeSet集合的底层结构

HashSet

底层结构：哈希表

数组+链表 （JDK7及以前）

数组+链表+红黑树 （JDK8及以后）

特点：存取无序、无索引、元素唯一

LinkedHashSet

底层结构：链表+哈希表

特点：存取有序、无索引、元素唯一

TreeSet

底层结构：二叉树

特点：按照给定的规则排序、无索引、元素唯一

HashSet集合是怎么保证元素唯一性的

依赖hashCode和equals两个方法

先通过hash计算在数组中的位置，然后用equals方法与链表或红黑树中的每个元素做对比，如果有相同元素就覆盖，如果没有相同元素则添加。

TreeSet集合是怎么保证元素唯一性的

比较接口中重写的比较方法，返回值为0表示元素重复

Map

HashMap集合的底层结构

JDK7及以前：数组+链表

JDK8及以后：数组+链表+红黑树

HashMap集合的无参构造，在第一次添加元素的时候数组的初始大小

16

HashMap集合加载因子为什么是0.75

泊松分布，泊松分布计算得到了在加载因子为0.75时，链表长度达到6为十万分之一，达到8为千万分之一。

加载因子较大，哈希冲突的概率变大，导致链表过长，查询效率变低

加载因子过小，数据过于稀疏，会导致空间浪费

HashMap集合中链表什么时候转红黑树

链表的长度达到阈值8，且数组的长度大于64

HashMap集合中红黑树什么时候转链表

链表的长度达到6

HashMap数组扩容的两种情况

1. 数组长度<64，链表长度达到阈值8
2. 添加元素超过承重

HashMap集合中数组的扩容为什么都是2的n次幂

因为在添加元素计算数组的下标时，使用的是key的哈希值和数组的长度减一做&运算

HashMap集合添加元素的时候，计算数组下标为什么不使用取余，而使用按位与

• 按位与的效率较高

• 取余可能出现负数

HashMap和Hashtable的区别

	HashMap	Hashtable
是否允许null值	允许null键和null值	不允许null键和null值
线程是否安全	线程不安全，效率高	线程安全的，效率低

concurrentHashMap 如何保证线程安全

​ ConcurrentHashMap 在HashMap的基础上，通过 CAS (compare and swap, 比较并交换） 或者 synchronized 来保证线程安全的，并且缩小了锁的粒度，查询性能也更高。

HashMap应用场景

​ 在登录校验中，使用JwtUtils.generateJwt(Map<String, Object> claims)方法生成JWT（Json Web Token）令牌返回前端时，需要传入一个Map集合。

@PostMapping("/login")
    public Result login(@RequestBody Emp emp){
        log.info("员工登录: {}", emp);
        Emp e = empService.login(emp);

        //登录成功,生成令牌,下发令牌
        if (e != null){
            Map<String, Object> claims = new HashMap<>();
            claims.put("id", e.getId());
            claims.put("username", e.getUsername());

            String jwt = JwtUtils.generateJwt(claims); //jwt包含了当前登录的员工信息
            return Result.success(jwt);
        }

        //登录失败, 返回错误信息
        return Result.error("用户名或密码错误");
    }

额外补充

线程安全

以上描述的集合类都是线程不安全的。

HashMap

在jdk1.8中

1. HashMap底层是数组+链表或红黑树的结构，加载因子为0.75

2. 向HashMap中用put()方法添加一个元素时，通过元素key的哈希值运算得到一个table表的索引

3. 查着索引处是否有元素

   1. 没有，则直接添加
   2. 有，则判断该位置的元素和要加入的元素的key的内容是否相同
      1. 相同：替换value
      2. 不同：需要判断是树结构还是链表结构，做出相应处理
         1. key值不同，红黑树进行添加元素操作
         2. key值不同，链表进行尾添加，判断当前链表个数是否超过8，再判断table大小是否>=64。是，则转变为红黑树，否则扩容table表。

4. 第一次添加table容量为16，临界值为12（16*0.75）

5. 再扩容，table容量为32，临界值为24

ArrayList 和 Array 有什么区别？ArrayList 和 LinkedList 的区别是什么？

• ArrayList vs Array：

1. ArrayList是动态数组的实现，而Array 是固定长度的数组。在随机访问时，Array由于其连续内存存储，性能通常优于ArrayList。
2. ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer） 。Array 可以直接存储基本类型数据，也可以存储对象。
3. ArrayList 提供了更多的功能，比如自动扩容、增加和删除元素等，Array则没有这些功能。

• ArrayList vs LinkedList：

1. ArrayList基于动态数组，LinkedList 基于双向链表。在ArrayList末尾添加元素通常很快，但在ArrayList中间或开始插入或删除元素时，可能需要移动后续元素，时间复杂度为 O(n)。而LinkedList添加和删除元素时性能更佳, 只需改变节点的引用。
2. 随机访问：ArrayList在随机访问时性能更好，而LinkedList访问元素时效率较低，因为需要从头开始或从尾开始通过链接遍历，时间复杂度为 O(n)。
3. 容量：当容量不足以容纳更多元素时，ArrayList 会扩容，这个过程涉及创建新数组和复制旧数组的内容，有一定的开销。
4. 使用场景：选择 ArrayList 或者 LinkedList 通常取决于你的 Java 应用是否需要频繁的随机访问操作，还是更多的插入和删除操作。

​ 总结来说，ArrayList和Array的主要区别在于动态大小和功能，而ArrayList和LinkedList的主要区别在于底层数据结构和它们对元素操作的性能特点。选择使用哪一个取决于具体的应用场景和性能需求。

ArrayList的扩容机制

​ ArrayList扩容的本质就是计算出新的扩容数组的size 后实例化，并将原有数组内容复制到新数组中去。

1. 当创建一个ArrayList集合时，它会分配一定的初始容量，通常为10。这是为了节省内存，因为并不是所有的ArrayList都需要大量的空间。
2. 需要扩容时，会调用grow()方法， 该方法先尝试将数组扩大为原数组的1.5倍。（默认新容量=旧容量右移一位（相当于除于2）在加上旧容量）
3. 若新的容量满足需求，会调用一个Arrays.copyof 方法, 将所有的元素从旧数组复制到新数组中。如果扩容后的新容量还是不满足需求，那新容量大小为当前所需的容量加 1。

红黑树

红黑树的特点

解决Hash冲突的方法有哪些？HashMap 是如何解决 hash 冲突的

哈希冲突

​ 当两个不同的数经过哈希函数计算后得到了同一个结果，即他们会被映射到哈希表的同一个位置时，该现象称为发生了哈希冲突。

解决方法

解决哈希冲突的方法主要有以下两种：

1. 链地址法：在数组的每个位置维护一个链表。当发生冲突时，新的元素会被添加到链表的尾部。
2. 开放寻址法：当发生冲突时，根据某种探测算法在哈希表中寻找下一个空闲位置来存储元素。

Java中的 HashMap使用链地址法解决hash冲突。

HashMap 为什么是线程不安全的? 如何实现线程安全

为什么是线程不安全的

​ HashMap是线程不安全的。因为HashMap的内部实现并没有加锁，多个线程同时访问和修改时可能会引发数据竞争，造成数据不一致或陷入死循环等问题。

如何实现线程安全

为了实现线程安全的 HashMap，有以下两种方式：

• 使用Collections.synchronizedMap()方法：这种方法通过在 HashMap的方法上加synchronized锁实现线程安全。不过，这种方式对整个Map加锁，会导致较高的锁竞争和性能开销，尤其是在高并发情况下。

Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

• 使用ConcurrentHashMap：ConcurrentHashMap 是专门设计用于多线程环境的哈希表实现。它使用分段锁机制，允许多个线程同时进行读操作，提高并发性能。

concurrentHashMap 如何保证线程安全

​ ConcurrentHashMap 在HashMap的基础上，通过 CAS 或者 synchronized 来保证线程安全的，并且缩小了锁的粒度，查询性能也更高。

HashMap和ConcurrentHashMap的区别

线程安全性：

• HashMap 是线程不安全的。在多线程环境中，如果同时进行读写操作，可能会导致数据不一致或抛出异常。如果要实现线程安全，可以通过使用 Collections.synchronizedMap() 方法对整个map上锁。
• ConcurrentHashMap 是线程安全的，它使用了分段锁（Segment Locking）的机制，将整个数据结构分成多个段（Segment），每个段都有自己的锁。这样，不同的线程可以同时访问不同的段，提高并发性能。

初始化容量和负载因子：

• HashMap 可以通过构造方法设置初始容量和负载因子。
• ConcurrentHashMap 在Java 8及之后版本中引入了ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)构造方法，允许设置初始容量、负载因子和并发级别。

性能：

• 在低并发情况下，HashMap 的性能可能会比 ConcurrentHashMap 稍好，因为 ConcurrentHashMap 需要维护额外的并发控制。
• 在高并发情况下，ConcurrentHashMap 的性能通常更好，因为它能够更有效地支持并发访问。

​ 总的来说，如果需要在多线程环境中使用哈希表，而且需要高性能的并发访问，通常会选择使用 ConcurrentHashMap。如果在单线程环境中使用，或者能够手动进行外部同步管理，那么 HashMap 可能是更简单的选择。

HashMap 和 HashSet 的区别

不同点：

​ HashMap 适用于需要存储键值对的情况，而 HashSet 适用于只关心元素唯一性的情况。在某些情况下，可以使用 HashMap 来模拟 HashSet 的行为，只使用键而将值设为固定的常量。

相同点：

​ 两者都允许所存对象为null，并且使用迭代器或增强型 for 循环遍历。

HashMap 和 HashTable 的区别

重点为前四点

空值

• HashMap 允许键和值都为 null。
• Hashtable 不允许键或值为 null。

线程安全

• HashMap 不保证在多线程环境中的线程安全性。如果需要同步，可以使用 Collections.synchronizedMap() 方法来创建一个同步的 HashMap。
• Hashtable 它的方法是线程安全的。这是通过在每个方法上添加同步关键字来实现的，但这也可能导致性能下降。

初始容量和加载因子

• HashMap 允许通过构造方法设置初始容量和加载因子，以便更好地调整性能。
• Hashtable 的初始容量和加载因子是固定的。

性能

• HashMap 在多线程环境中可能比 Hashtable 更快，因为它没有同步开销。
• 由于 Hashtable 是同步的，它在多线程环境中的性能可能较差。

继承关系

Hashtable 是 Dictionary 类的子类，而 HashMap 是 AbstractMap 类的子类，实现了 Map 接口。

迭代器

• HashMap 的迭代器是通过 Iterator 实现的。
• Hashtable 的迭代器是通过 Enumerator 实现的。