Java集合概述
# Java 集合概述
# 集合与容器
- 容器（Container）是一个更广泛的术语，用于表示可以容纳、组织和管理其他对象的对象。它是一个更高层次的概念，包括集合（Collection）在内。
- 集合（Collection）是一种特定类型的容器，用于存储和操作一组对象。集合提供了对元素的添加、删除、查找和遍历等操作。List、Set、Queue 和 Map 都是集合的具体实现。
总结
- 容器是一个广泛的概念，用于表示可以容纳和管理其他对象的对象。
- 集合是容器的一种特定类型，用于存储和操作一组对象。
# Java 集合框架如下图所示
# 说说 List, Set, Queue, Map 四者的区别？
List(对付顺序的好帮手): 存储的元素是有序的、可重复的。（可以通过索引访问和修改元素）Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。（无索引）Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，"x" 代表 key，"y" 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
# 无序性和不可重复性的含义是什么
- 无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
- 不可重复性是指添加的元素按照
equals()判断时 ，返回 false，需要同时重写equals()方法和hashCode()方法。
# 集合框架底层数据结构常见实现类
# 1. List
ArrayList：Object[]数组Vector：Object[]数组LinkedList： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)
# 2. Set
HashSet(无序，唯一): 基于HashMap实现的，底层采用HashMap来保存元素LinkedHashSet(有序，唯一):LinkedHashSet是HashSet的子类，并且其内部是通过LinkedHashMap来实现的。有点类似于我们之前说的LinkedHashMap其内部是基于HashMap实现一样，不过还是有一点点区别的TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)红黑树（Red-Black Tree）是一种自平衡的二叉查找树。它的特点是：每个节点要么是红色，要么是黑色；树的根节点是黑色的；所有叶子节点都是黑色的空节点（NIL节点）；如果一个节点是红色的，则其子节点必须是黑色的；从根节点到叶子节点的所有路径上，不能有两个连续的红色节点；从任意一个节点到其子树中每个叶子节点的路径都包含相同数目的黑色节点。
# 3. Queue
PriorityQueue:Object[]数组来实现二叉堆ArrayQueue:Object[]数组 + 双指针
再来看看 Map 接口下面的集合。
# 4. Map
HashMap： JDK1.8 之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间LinkedHashMap（有序的）：LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。Hashtable： 数组+链表组成的，数组是Hashtable的主体，链表则是主要为了解决哈希冲突而存在的HashTable是线程安全的，而HashMap不是。在多线程环境下，使用HashTable可以避免数据竞争和并发访问的问题，但是对于单线程环境，使用HashMap可以提高性能TreeMap： 红黑树（自平衡的排序二叉树）
# 哈希冲突
哈希冲突是指在哈希表中，不同的关键字（Key）通过哈希函数被映射到了同一个槽位（Bucket）中，导致同一个槽位中存储了多个关键字的情况。
当 HashMap 发生哈希冲突时，链表存储的是键值对（key-value pairs）。具体来说，链表中的每个元素包含一个键（key）和一个值（value）。所以，链表不仅存储元素本身，还包含键。
# 为什么链表可以解决哈希冲突（拉链法：数组+链表）
当一个桶中存储多个键值对时，可以将它们存储在一个链表中，每个节点存储一个键值对。当需要查找或删除某个键值对时，可以按照哈希函数的规则找到对应的桶，然后遍历链表中的节点，查找或删除目标键值对
# 哈希表是什么
在 Java 中，"哈希表" 通常泛指基于哈希结构实现的集合类，即指以哈希算法为核心，通过哈希函数将键值对映射到表中位置的数据结构。具体到
HashMap和Hashtable，二者均可称为哈希表的实现方式，尽管它们在具体应用中有所不同。
哈希表（Hash Table），也称为散列表，是一种数据结构，用于实现关联数组（Associative Array）或映射（Map）等抽象数据类型。
- 它通过将关键字映射到表中一个位置来访问记录，以加快查找的速度。
- 哈希表实际上是一个数组，其中每个元素都是一个链表的头节点，每个链表中包含了哈希值相同的所有元素。
哈希表的基本思想是：将关键字通过哈希函数计算出一个哈希值，然后将该值作为数组的下标，将元素存储在对应的数组位置中。
- 在查找元素时，通过哈希函数计算出关键字的哈希值，然后在对应的数组位置中查找元素。
- 哈希表的优点是查找速度快，时间复杂度为 O(1)，而不像线性表的查找时间复杂度为 O(n)。
- 但是，哈希表的缺点是空间利用率相对较低，因为需要预留足够的空间来存储哈希冲突的元素。
- 此外，哈希表的性能还受到哈希函数的影响，如果哈希函数设计不好，可能会导致哈希冲突率过高，降低哈希表的性能。
# 线程不安全的接口
ArrayList，LinkedList，HashSet，LinkedHashSet，TreeSet，PriorityQueue，ArrayQueue，HashMap，LinkedHashMap，TreeMap
都是线程不安全的
# 线程安全的接口
Vector，Hashtable，ConcurrentHashMap
# 为什么要使用集合
- 是因为数组一旦声明之后，长度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可重复的，特点单一。
- 而集合提高了数据存储的灵活性，Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据。