Java集合1.0

1.什么是集合？

集合就是一个存放数据的容器，准确的说是放数据对象引用的容器。

集合和数组的区别

• 数组是固定长度，集合是可变长度。
• 数组可以存储基本数据类型，也可以存储引用数据类型，集合只能存储引用数据类型；
• 数组存储的元素必须是同一个数据类型，集合存储的对象可以是不同的数据类型。

使用集合框架的好处

• 容量自增长；
• 提供了高性能的数据结构和算法，使得编码更轻松，提高了程序速度和质量；
• 允许不同API之间相互操作，API之间可以来回传递集合；
• 可以方便的扩展或改写集合，提高了代码的复用性和可操作性；
• 通过使用JDK自带的集合类，可以降低代码维护和学习新API的成本；

2.常用的集合类有哪些？

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

1. Collection接口的子接口包括：Set接口和List接口，Queue接口；
2. Map接口的实现类主要有：HashMap,TreeMap,HashTable,ConcurrentHashMap；
3. Set接口的实现类主要有：HashSet，TreeSet，LinkedHashSet；
4. List接口的实现类主要有：ArrayList，LinkedList，Stack，Vector；

3.List，Set，Map三者的区别？

• List：

1. 可以允许重复对象
2. 可以插入多个null对象
3. 是一个有序的容器，保持了每个元素的插入顺序，它的输出顺序就是插入顺序；
4. 常用的实现类有ArrayList，LinkedList，Vector。

• Set：

1. 不允许重复对象
2. 无序容器，没法保证每个元素的存储顺序，TreeSet通过Comparator或者Comparable维护了一个排序顺序
3. 只允许一个null元素
4. 常用的实现类是HashSet，LinkedHashSet，TreeSet

• Map：

1. Map里你可以拥有随意个null值，但只能有一个null键
2. 常用的是实现类：HashMap，TreeMap，Hashtable，LinkedHashMap；

4.集合框架底层数据结构

List接口

1.ArrayList

• 底层数据结构：动态数组
• 特点：基于动态数组实现，数组在存储元素时是连续的内存空间；当数组容量不足时会自动扩容，通常为原容量的1.5倍；随机访问元素时O(1)的时间复杂度，但在插入或者删除元素时为O(n);

2.LinkedList

• 底层数据结构：双向链表
• 特点：基于双向链表实现，每个节点包含一个数据元素以及指向前后节点的两个指针；插入和删除操作O(1)；随机访问O(n)，因为需要从头或者尾部开始遍历链表；

3.Vector

• 底层数据结构：动态数组
• 特点：Vector时线程安全的，每个方法都被sychronized关键字修饰，因此在多线程环境下会出现数据不一致的问题；性能比ArrayList较差
• 适用场景：适合多线程环境中需要频繁访问的场景，但由于Vector的性能开销，一般推荐ArrayList和同步机制配合使用；

Set接口

1.HashSet

• 底层数据结构：哈希表
• 特点：基于HashMap实现，哈希表使用散列函数来计算每个元素的哈希值，并将元素存储在相应的哈希桶中；HashSet不保证集合的顺序，插入，删除，查找操作的时间复杂度为O(1)；允许一个null值；
• 适用场景：需要快速查找，插入，删除，并且不关心元素顺序的场景

2.LinkedHashSet

• 底层数据结构：链表和哈希表
• 特点：继承自HashSet，但维护者一个双向链表以保证插入顺序；

3.TreeSet

• 底层数据结构：红黑树(自平衡的二叉搜索树)
• 特点：基于TreeMap实现；元素的顺序是根据提供的比较器来排序的，插入删除查找操作为O(logn)；不允许null值，因为null无法比较

Map接口

1.HashMap

• 底层数据结构：哈希表和链表/红黑树
• 特点：基于哈希表实现，使用散列函数计算键的哈希值并将键值对存储在相应的哈希桶中；当哈希冲突发生时，HashMap使用链表来存储冲突的元素。从Java 8开始，当链表长度超过一定阈值（默认8）时，链表会转换为红黑树，以提高查找和删除效率。

2.LinkedHashMap

• 底层数据结构：链表和哈希表
• 特点：除了使用哈希表存储键值对外，还维护了一个双向链表来记录元素的插入顺序或访问顺序。

3.TreeMap

• 底层数据结构：红黑树
• 特点：底层基于红黑树实现，键值对按键的自然顺序或自定义比较器排序；不允许null键；
• 场景：适合需要键值对有序排列和范围查找的场景。

4.Hashtable

• 底层数据结构：哈希表
• 特点：和HashMap类似，但Hashtable是线程安全的，所有方法都被synchronized修饰。
• 场景：适合多线程环境下线程安全的键值对存储

5.哪些集合类是线程安全的？

1. Vector：Vector 是一个古老的动态数组实现，所有的方法都被 synchronized 关键字修饰，因此是线程安全的。然而，由于性能较差，不推荐在现代代码中使用。
2. Hashtable：Hashtable 是一个古老的哈希表实现，也是线程安全的，所有的方法都被 synchronized 关键字修饰。和 Vector 一样，由于性能原因，现在一般推荐使用 HashMap
3. ConcurrentHashMap：ConcurrentHashMap 是 Java 5 及以后版本引入的并发哈希表实现。它采用分段锁机制，支持高并发的读和写操作，是一个高性能的线程安全集合类