【Java集合】List，Map，Set-详细讲解_map,hasmap,list

文章目录

• Java 集合框架核心知识点总结
• • 概念
  • • 数组和集合的区别
    • Collection 和 Collections 有什么区别
  • List
  • • List 中的几种实现，以及他们的不同
    • List 可以一边遍历一边修改元素吗
    • ArrayList 线程不安全体现在哪里？
    • ArrayList 的扩容机制
  • Map
  • • Map 的遍历方式
    • HashMap 的实现原理
    • 解决哈希冲突的方法有哪些
    • HashMap 是线程安全的吗，可能会出现哪些问题？
    • HashMap 的 put 方法的过程
    • HashMap 一般使用什么作为 key？为什么
    • 为什么 HashMap 使用红黑树而不是直接使用平衡二叉树
    • HashMap 的扩容机制
    • 说一说 HashMap 的负载因子
    • ConcurrentHashMap 是怎么实现的
    • HashTable 的实现原理
    • HashMap, HashTable, ConcurrentHashMap 的区别
  • Set
  • • Set 集合有什么特点，怎么实现的
    • 有序的 set 集合是什么？

Java 集合框架核心知识点总结

概念

数组和集合的区别

• 数组的长度是不可变的，一旦被创建，不能被修改。而集合的长度是可变的。
• 数组中存储的元素可以是基本数据类型，也可以是对象。而集合中存储的元素只能是对象。
• 数组可以通过下标直接访问到元素，而集合需要通过迭代器等方式来获取元素。

Collection 和 Collections 有什么区别

• Collection 是集合类的总接口，其中定义了一些通用的方法比如增加删除元素，List，Set 都是它的实现类。
• Collections 是 Java 提供的用来处理集合的工具包，位于 java.util 包中。

---

List

List 中的几种实现，以及他们的不同

• ArrayList：它是由可变数组实现的，是线程不安全的。它的元素访问速度比较快，但是对元素的增加和删除速度比较慢。
• LinkedList：基于双向链表实现的，也是线程不安全的。它的元素访问速度比较慢但是元素的增加和删除速度比较快。
• Vector：类似与 ArrayList 也是可变数组，它是线程安全的。
• CopyOnWriteArrayList：它也是线程安全的，它通过对写操作进行加锁，保证了线程安全。对读操作没有加锁，这使得读写分离，可以在修改的同时不影响读操作。

实现类 底层结构 线程安全 访问速度 增删速度 ArrayList 可变数组 否 快 慢 LinkedList 双向链表 否 慢 快 Vector 可变数组 是 快 慢 CopyOnWriteArrayList 可变数组 是 快 慢

List 可以一边遍历一边修改元素吗

这与遍历的方式有关：

• 使用普通 for 循环遍历：可以直接修改。

  for (int i = 0; i < list.size(); i++) { list.set(i, \"newValue\"); // 可以直接修改}

• 使用增强型 for 循环 (foreach)：不可以直接修改，因为它的底层是基于迭代器实现的，强行修改可能会导致 ConcurrentModificationException。

  for (String item : list) { list.remove(item); // 可能抛出 ConcurrentModificationException}

• 使用迭代器遍历：可以使用迭代器的 remove(), set() 方法来进行删除和修改操作。

  Iterator<String> iterator = list.iterator();while (iterator.hasNext()) { String item = iterator.next(); iterator.remove(); // 安全删除 // iterator.set(\"newValue\"); // 安全修改}

ArrayList 线程不安全体现在哪里？

• 可能会出现 null 值。ArrayList 底层实现 add 方法是先判断当前位置是否超过容量大小，如果没有将值放入进去，然后将当前位置对应的变量 size++。如果此时两个线程，线程1先判断当前 size 为9，未超过容量，则执行 set 操作，还没进行 size++ 时就转换到线程二进行操作，同样判断当前位置为9，进行 set 操作。这时候两个线程再分别进行 size++ 操作，这时候 size=11，导致 size=10 这个位置为 null。
• 可能越界：同样在执行 add 操作时，线程一执行完 set 操作后还没有进行 size++，线程二就去判断是否超过容量，结果发现没有超过容量，但是还没有执行 set 操作就进入线程1进行 size++，这时候线程二执行 set 操作就会发生越界。
• size 与 add 的数量不一致：这是由于 size++ 这个操作本身就不是原子性的，它分为获取 size 值，将其进行 +1，将新值赋值给 size。可能线程1和线程2拿到一样的 size 然后互相覆盖掉了。

ArrayList 的扩容机制

当内部数组容量不够时，会触发扩容机制。

1. 计算扩容后数组的大小：新容量一般为旧容量的 1.5 倍。
2. 创建新数组：根据计算得到的大小创建新数组。
3. 数据复制：将原数组当中的数据复制到新数组当中。
4. 更新引用：将指向原数组的引用改为指向新数组。

---

Map

Map 的遍历方式

• 通过 for-each 和 entrySet 来进行遍历

  for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + \": \" + entry.getValue());}

• 通过 for-each 和 keySet 来进行遍历

  for (String key : map.keySet()) { System.out.println(key + \": \" + map.get(key));}

• 通过 entrySet 和迭代器来进行遍历

  Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();while (iterator.hasNext()) { Map.Entry<String, Integer> entry = iterator.next(); System.out.println(entry.getKey() + \": \" + entry.getValue());}

• 通过 forEach 方法和 Lambda 表达式进行遍历

  map.forEach((k, v) -> System.out.println(k + \": \" + v));

• 通过 Stream API 进行遍历

  map.entrySet().stream().forEach(entry -> { System.out.println(entry.getKey() + \": \" + entry.getValue());});

HashMap 的实现原理

HashMap 在 jdk1.7 以前是由数组+链表实现的，通过计算 key 的 hashcode 来将其映射到数组当中的插槽位置。如果多个 key 计算得到的插槽位置相同，那么使用链表将其连接起来存放在插槽中。
在 jdk1.8 以后是由数组+链表+红黑树实现的。当链表长度大于 8，数组长度大于 64 时，会将链表转化为红黑树，提高查询速率。

解决哈希冲突的方法有哪些

• 再哈希法：当发生哈希冲突时，我们可以使用其他 hash 函数来再次计算。
• 连接法：通过使用链表等数据结构将其连接在一起，放在同一个哈希桶中（HashMap 采用的方法）。
• 开放定址法：通过使用线性探测等算法重新找到位置存放。
• 哈希桶扩容。

HashMap 是线程安全的吗，可能会出现哪些问题？

不是，在 jdk1.7 以前，多线程环境下可能在增加元素时产生循环链表，导致 entrykey 死循环，还可能发生数据丢失的问题。在 jdk1.8 以后，使用数组+链表+红黑树的结构，解决了 entrykey 链死循环的问题。但是还是有 put 方法的覆盖问题。

HashMap 的 put 方法的过程

1. 根据要存放元素的 key 计算 hashcode 找到插槽位置。
2. 判断该位置是否存在元素，如果不存在，直接创建一个 entry 对象来存储该键值对，并将修改次数 +1。
3. 如果存在元素，进一步通过 equals 方法判断是否相同。如果相同直接将其 value 进行更新。如果不相同则遍历红黑树或者链表，查看是否有相同的元素，从而进行更新或者插入操作。
4. 检查链表长度是否大于阈值（是否为 8）。
5. 检查负载因子是否大于 0.75，如果大于进行扩容。

HashMap 一般使用什么作为 key？为什么

String，因为 String 是不可变的，一旦被创建不能被修改，它的 hashcode 和 equals 方法都是固定的，较为稳定。

为什么 HashMap 使用红黑树而不是直接使用平衡二叉树

• 平衡二叉树它要求每个子树的高度差不能超过 1，这个要求太严格了。会频繁修改树的结构。
• 红黑树要求最长结点长度不能超过最短节点的 2 倍，虽然牺牲了一部分查询效率，但是不会频繁触发修改树的结构。

特性 红黑树 平衡二叉树 (AVL) 平衡标准 非严格平衡（最长路径不超过最短路径的2倍） 严格平衡（左右子树高度差绝对值不超过1） 查询效率 O(log n)，稍弱于 AVL O(log n)，查询性能极致 插入/删除 效率更高，旋转次数少，调整操作更少 效率较低，需要更频繁的旋转操作以维持绝对平衡 适用场景 增删操作频繁的场景（如 HashMap） 查询非常多，增删很少的场景（如数据库索引）

HashMap 的扩容机制

当负载因子大于 0.75，即元素数量与数组大小的比值为 0.75 时会触发扩容。扩容一般分为两步：

1. 计算扩容后的长度并创建数组：新容量为旧容量的 2 倍。
2. 将旧数组中的数据转移到新数组：
   • 在 jdk1.7 以前，转移操作是直接将数组重新进行一个一个的哈希运算，重新分配位置。
   • 在 jdk1.8 以后，通过将该元素当前位置 & 扩容后数组大小得到 0 或者 1，如果为 0 则还在原位置，如果为 1 则在该位置 + 原数组大小的位置。这样可以不用通过哈希运算快速找到新位置。极大提高效率。

说一说 HashMap 的负载因子

负载因子是指元素的数量与数组大小的比值。当大于 0.75 时会触发扩容。设置为 0.75 的原因是平衡了时间和空间复杂度。负载因子过大，会导致大量碰撞，导致性能降低。过小会导致内存利用率不高。

ConcurrentHashMap 是怎么实现的

• 在 jdk1.7 以前，是由数组+链表实现的。并且通过 Segment（可重入锁）将数据分为一段一段的，并且为每一段数据分配一把锁。当一个线程访问一段数据时，其他段的数据也能被其他线程所访问。
• 在 jdk1.8 以后采用数组+链表+红黑树实现。并且通过 volatile + synchronized 或 CAS 实现的。当向其中添加一个元素时，会先判断容器是否被创建，如果没有，就使用 volatile 和 CAS（乐观锁）来初始化容器。然后判断容器内该位置是否有元素，如果没有，直接使用 CAS 创建元素（乐观锁），如果有，使用 synchronized 关键字，然后遍历链表或者红黑树，进行修改或者创建元素。

HashTable 的实现原理

• HashTable 底层是通过数组+链表实现的，数组是本体，链表是为了解决哈希冲突的。
• HashTable 通过将内部方法都用 synchronized 关键字进行修饰，来实现线程安全的。

HashMap, HashTable, ConcurrentHashMap 的区别

特性 HashMap HashTable ConcurrentHashMap (JDK 1.8) 线程安全 否 是 ( synchronized 方法) 是 ( synchronized + CAS) Key/Value 允许为 null 不允许为 null 不允许为 null 性能 高 低 (全局锁) 高 (锁粒度小) 底层结构 数组+链表+红黑树 (JDK8+) 数组+链表 数组+链表+红黑树 (JDK8+) 扩容 2倍 2n+1 2倍 初始容量 16 11 16

• HashMap 是非线程安全的，它的 key 和 value 允许为 null。默认初始容量为 16，扩容时一般扩容为原来的 2 倍。如果设置了初始值，扩容为 2 的幂次倍。它的底层是由链表+数组+红黑树实现的。
• HashTable 是线程安全的，它的 key 和 value 不允许为 null。默认初始容量为 11，扩容时一般扩容为原来的 2n+1。如果设置了初始值，直接使用初始值。它的底层是数组+链表实现的。
• ConcurrentHashMap 是线程安全的，它的 key 和 value 不允许为 null。它可以在多线程环境下进行并发读写。它的底层是由数组+链表+红黑树实现的。

---

Set

Set 集合有什么特点，怎么实现的

特点：无重复。
通过内部的数据结构来实现 key 的无重复，首先它会根据 hash 值来判断该元素在 set 中是否存在，如果存在，进一步使用 equals 方法进行判断。

有序的 set 集合是什么？

• TreeSet：通过比较器中的比较规则来进行有序排序。
• LinkedHashSet：通过链表来记录插入的顺序。