Java 集合

集合框架可以分为两条大的支线：

1. Collection 接口, 主要由 List、Set、Queue 组成
   • List 接口
     • 代表有序、可重复的集合
       • 封装了动态数组的 ArrayList
       • 封装了链表的 LinkedList
   • Set 接口
     • 代表无序、不可重复的集合
       • HashSet
       • LinkedHashSet
       • TreeSet
   • Queue 接口
     • 代表队列
       • PriorityQueue
       • ArrayDeque
2. Map 接口
   • 代表键值对的集合
   • 键不能重复，每个键只能对应一个值
   • 典型代表就是 HashMap

Java 集合

获取长度的不同对应函数

• (集合类) Collection 和 Map：size()
• 数组：length（属性）
• String：length()（方法）

List

• Vector
• ArrayList
• LinkedList
• CopyOnWrtieArrayList

Java 集合

Map

常见的Map集合 (非线程安全)：

• HashMap: 是基于哈希表实现的Map，它根据键的哈希值来存储和获取键值对，JDK 1.8中是用数组+链表+红黑树来实现的
  • HashMap是非线程安全的，在多线程环境下，当多个线程同时对HashMap进行操作时，可能会导致数据不一致或出现死循环等问题。比如在扩容时，多个线程可能会同时修改哈希表的结构，从而破坏数据的完整性。
• LinkedHashMap: 继承自HashMap，它在HashMap的基础上，使用双向链表维护了键值对的插入顺序或访问顺序，使得迭代顺序与插入顺序或访问顺序一致。
  • 由于它继承自HashMap，在多线程并发访问时，同样会出现与HashMap类似的线程安全问题。
• TreeMap: 是基于红黑树实现的Map，它可以对键进行排序，默认按照自然顺序排序，也可以通过指定的比较器进行排序
  • TreeMap是非线程安全的，在多线程环境下，如果多个线程同时对TreeMap进行插入、删除等操作，可能会破坏红黑树的结构，导致数据不一致或程序出现异常

Java 集合

HashMap

底层数据结构

JDK 8 中 HashMap 的数据结构是数组+链表+红黑树

数组用来存储键值对，每个键值对可以通过索引直接拿到，索引是通过对键的哈希值进行进一步的 hash() 处理得到的

当多个键经过哈希处理后得到相同的索引时，需要通过链表来解决哈希冲突——将具有相同索引的键值对通过链表存储起来

Java 集合

HashMap

红黑树

红黑树是一种自平衡的二叉查找树

特点：节点设置颜色(红/黑) | 根+叶子节点是黑色 | 叶子节点是 null 节点 |

| 红色节点不能连着 | 最长路径不会超过最短路径两倍

关键：所有节点到其每个叶子的所有简单路径都包含相同数目的黑色节点 (最长路径不会超过最短路径两倍)

• 每个节点要么是红色，要么是黑色；
• 根节点永远是黑色；
• 所有的叶子节点都是黑色的（下图中的 NULL 节点）；
• 红色节点的子节点一定是黑色的 (红色节点不能连着)；
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

Java 集合

HashMap

怎么解决 HashMap 线程不安全

在早期的 JDK 版本中，可以用 Hashtable 来保证线程安全。Hashtable 在方法上加了 synchronized 关键字

另外，可以通过 Collections.synchronizedMap 方法返回一个线程安全的 Map，内部是通过 synchronized 对象锁来保证线程安全的，比在方法上直接加 synchronized 关键字更轻量级

更好的解决方案是

使用并发工具包下的 ConcurrentHashMap，使用了CAS+ synchronized 关键字来保证线程安全

Java 集合

Set

HashSet 的底层实现

HashSet 是由 HashMap 实现的，只不过值由一个固定的 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;
  // Dummy value to associate with an Object in the backing Map
  private static final Object PRESENT = new Object();
  // ……
}