Java的集合框架总结

Map接口和Collection接口是所有集合框架的父接口：

1. Collection接口的子接口包括：Set接口和List接口

1. Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等

1. Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等

1. List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

List接口及其实现

ArrayList

• 基于动态数组实现

• 允许快速随机访问元素

• 插入和删除操作可能需要移动其他元素，因此在中间位置插入和删除的时间复杂度为O(n)

• 非同步，不是线程安全的，可以使用使用Collections.synchronizedList(new ArrayList<>()) 创建一个同步的 ArrayList。

LinkedList

• 基于双向链表实现

• 允许快速插入删除元素

• 不能快速随机访问，访问元素的时间复杂度为O（n）

• 非同步，不是线程安全的。可以使用 Collections.synchronizedList(new LinkedList<>()) 创建一个同步的 LinkedList。

• 可以用做队列或双向队列

  依赖于两个节点（一个头节点一个尾节点）

  常用方法

  添加

  add(E e)：在链表后添加一个元素； 通用方法 addFirst(E e)：在链表头部插入一个元素； 特有方法 addLast(E e)：在链表尾部添加一个元素； 特有方法

  删除

  removeFirst(E e)：删除头，获取元素并删除； 特有方法 removeLast(E e)：删除尾； 特有方法

  查看

  getFirst()：获取第一个元素； 特有方法 getLast()：获取最后一个元素； 特有方法

Stack

• 基于Vector实现，代表了后进先出（）

• 是同步的，是线程安全的

• push入栈、peek查看栈顶元素、pop出栈、empty是否为空、size（）获取数目

Vector

• 基于动态数组实现，类似于ArrayList

• 同步的，是线程安全的

• 是需要线程安全的动态数组是使用，但是通常使用ArrayList和Collections.syschronizedList来代替

Set接口及其实现类

set其实一直在用map那一套

 public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable {
     private transient HashMap map;
     private static final Object PRESENT = new Object();
 ​
     public HashSet() {
         map = new HashMap<>();
     }
 ​
     public boolean add(E e) {
         return map.put(e, PRESENT) == null;
     }
 ​
     // Other methods delegate to the underlying map
 }
 ​

HashSet

• 元素存储HashSet 将元素添加到底层的 HashMap 中，键是元素的哈希码，值是一个占位符对象。HashSet的实现是基于HashMap的，他使用HashMap来存储元素，在HashSet中，元素被当作HashMap的键，而HashMap的值则是一个固定的占位符，通常是 PRESENT 对象（一个静态内部类对象）。这样做是为了节省空间，因为 HashSet 只关心元素的唯一性，不需要存储额外的值。

• 去重：HashSet 使用了 HashMap 键的唯一性来确保 HashSet 中不会有重复的元素。

• 不保证集合的迭代顺序，顺序可能会随时间变化。

• 方法委派：HashSet 的许多方法（如 add、remove、contains 等）都是通过调用底层 HashMap 的对应方法来实现的。

• 性能：由于 HashSet 是基于 HashMap 实现的，所以其性能与 HashMap 类似，添加、删除和查找操作的平均时间复杂度为 O(1)。

• 允许存储null值。

LinkedHashSet

LinkedHashSet 是 HashSet 的一个子类，它继承了 HashSet 的特性，并且保持了元素的插入顺序。下面是关于 LinkedHashSet 的一些关键点：

• 继承自HashSet并且使用链表维护元素的插入顺序

• 保证迭代顺序与插入顺序一致

• 允许存储null值。

• 插入、删除、和查找操作的时间复杂度为O(1)。

实现细节

• 当你向 LinkedHashSet 添加元素时，它会使用 LinkedHashMap 来存储元素。

• 每个元素被当作 LinkedHashMap 的键，值则是一个固定的占位符对象。

• LinkedHashSet 通过委派 LinkedHashMap 来实现其 add、remove 和 contains 等方法。

TreeSet

TreeSet 是 Java 中实现 SortedSet 接口的一个集合类，它基于 TreeMap 实现，并且元素是按照自然顺序（或通过提供的比较器）排序的。以下是 TreeSet 的一些关键点：

• 基于红黑树（自平衡二叉搜索树）实现

• 元素是有序的，元素按照自然顺序（或通过Comparator指定的顺序）排

• 不允许存储null值（会抛出NullPointerException）

• 插入、删除、和查找操作的时间复杂度为O(log n)。

Map接口及其实现类

HashMap：

• 基于哈希表实现，调用put方法值，首先将k，v封装到Node对象中，然后底层会调用k的hashCode（）方法得到hash值。根据这个值来决定到底该插入数组下标的哪个位置，如果有两个值的哈希值一样，就会调用equals方法进行比较，如果哈希值一样但是不相等，就会形成链表插入 ，如果相等那么相等的这个节点的value将会被覆盖。如果没有元素占用位置，就直接放入即可。（通过数组加链表形式）

• 在Java8对hashmap进行了优化，如果相同哈希值，链表的长度超过8，就从链表转换成红黑树。第一次添加元素的时候，默认初期长度为16，当往map中继续添加元素的时候，通过hash值跟数组长度取“与”来决定放在数组的哪个位置，如果出现放在同一个位置的时候，优先以链表的形式存放，在同一个位置的个数又达到了8个（代码是>=7,从0开始，及第8个开始判断是否转化成红黑树），如果数组的长度还小于64的时候，则会扩容数组。如果数组的长度大于等于64的话，才会将该节点的链表转换成树。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表（只有当数据量大于64才会有红黑树+链表）

• HashMap内部结构是数组（Node[] table）和链表结合组成的复合结构，数组被分成一个个桶（bucket）或槽，通过哈希值决定键值对在这个数组的寻址；哈希值相同的键值对，则以链表形式存储。当链表大小超过阈值（TREEIFY_THRESHOLD = 8）时，链表就会被改造成树形结构。（查询效率变高）

• Java8不再像Java7中那样需要满足两个条件，Java8中扩容只需要满足一个条件：当前存放新值（注意不是替换已有元素位置时）的时候已有元素的个数大于等于阈值（已有元素等于阈值，下一个存放后必然触发扩容机制）且扩容发生在存放后，即是数据存放后（先存放后扩容），判断当前存入对象的个数，如果大于阈值则进行扩容。

• 允许存储null键和null值。

• 插入、删除、和查找操作的时间复杂度为O(1)。

• 非同步，不是线程安全的。

LinkedHashMap

• 通过hashmap跟双向链表实现，可以确保按照插入顺序迭代链表

• 遍历性能： 与普通的HashMap相比，在迭代LinkedHashMap时，性能更加稳定。因为它不需要遍历整个桶，而是按照链表顺序遍历元素。

• 实现方式： 在内部实现上，LinkedHashMap在每个条目中保留了前一个和后一个条目的引用，以实现双向链表。这使得在插入、删除和遍历元素时的性能表现良好。

TreeMap：

• 基于红黑树实现

• 键按照自然顺序（或通过Comparator指定的顺序）排序。

• 不允许存储Null键

• 插入、删除、和查找操作的时间复杂度为O(log n)。

Hashtable

• 也是使用哈希表还有链表实现

• 同步的，是线程安全的。

• 不允许存储null键和null值。

• 插入、删除、和查找操作的时间复杂度为O(1)。

Properties

• 继承自Hashtable，表示一个持久化的属性集。

• 每个键及其对应值都是一个字符串。

• 常用于读取和写入配置文件。

ConcurrentHashMap

• 不允许存储null键和null值。

• 插入、删除、和查找操作的时间复杂度为O(1)。

• 在多线程环境下，使用HashMap进行put操作时存在丢失数据的情况，为了避免这种bug的隐患，强烈建议使用ConcurrentHashMap代替HashMap。

• HashTable是一个线程安全的类，它使用synchronized来锁住整张Hash表来实现线程安全，即每次锁住整张表让线程独占，相当于所有线程进行读写时都去竞争一把锁，导致效率非常低下。ConcurrentHashMap可以做到读取数据不加锁，并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小，允许多个修改操作并发进行，其关键在于使用了锁分段技术。它使用了多个锁来控制对hash表的不同部分进行的修改。

分段锁（Segment Locking）机制

早期版本的ConcurrentHashMap（Java 7及之前）使用分段锁机制，具体如下：

• ConcurrentHashMap内部将整个哈希表分为多个段（Segment），每个段都是一个独立的哈希表，并拥有自己的锁。

• 这种机制允许多个线程同时访问不同段的元素，从而提高并发度。

• ConcurrentHashMap 为了提高本身的并发能力，在内部采用了一个叫做 Segment 的结构，一个 Segment 其实就是一个类 Hash Table 的结构，Segment 内部维护了一个链表数组，我们用下面这一幅图来看下 ConcurrentHashMap 的内部结构,从下面的结构我们可以了解到，ConcurrentHashMap 定位一个元素的过程需要进行两次Hash操作，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部，因此，这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长，但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行操作即可，不会影响到其他的 Segment，这样，在最理想的情况下，ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment上），所以，通过这一种结构，ConcurrentHashMap 的并发能力可以大大的提高。

CAS操作和分段锁

在Java 8中，ConcurrentHashMap使用了一种新的机制，结合了CAS（Compare-And-Swap）操作和细粒度的分段锁。

• 使用CAS操作来保证对单个节点的原子性操作，减少锁的使用。

• 在插入、删除和更新操作中，如果CAS操作失败（即另一个线程同时修改了相同的位置），则退而使用锁进行操作。

• 在Java 8中，ConcurrentHashMap取消了分段锁的概念，直接在哈希桶（bucket）级别进行锁定，使用CAS操作和synchronized块来保证并发安全。这使得数据结构更加简单，且操作更加直观。

• 为了优化哈希冲突情况下的查找性能，Java 8引入了红黑树。当链表的长度超过一定阈值（默认是8）时，链表会转换为红黑树。这样，在高冲突情况下，查找操作的时间复杂度从O(n)降到了O(log n)，极大地提高了性能。

• CAS 操作通过比较当前值与预期值，如果两者相等则更新为新值，否则重试该操作。

数据结构

ConcurrentHashMap在Java 8中的内部数据结构有以下几个关键组成部分：

• 数组（Node[] table）：哈希表的核心数组，存储链表或红黑树的头节点。

• 链表和红黑树：数组中的每个桶（bucket）最初是一个链表。当链表长度超过阈值（8）时，链表会转换为红黑树，以提高查询效率。