Java中List、Set、Map的区别和实现方式
Java中List、Set、Map的区别和实现方式
List
- List 是一个有序的集合，即元素按照插入的顺序进行排序，可以有重复的元素。
- 因为是有序的，所以可以根据下标来获取元素或者遍历整个集合内的元素。
- 常用的实现类包括 ArrayList 和 LinkedList。
ArrayList
- 底层是基于数组实现的，在内部维护了一个 Object[] 数组。
- 当需要添加元素时，首先检查数组是否已满，如果未满，就直接在后面添加元素，否则需要通过扩容数组的方式来增加容量。
- 由于数组长度固定且数组内的元素是连续的，因此查询某个元素的时间复杂度为 O(1)，而添加或删除元素的时间复杂度为 O(n)（需要移动后面的元素）。
LinkedList
- 底层是基于链表实现的，每个节点包含一个元素和指向下一个节点的引用。
- 当需要添加(尾部添加O(1))或删除(删除头结点或者使用 iterator 的 remove 方法 O(1))元素时，只需要修改相邻节点之间的引用，不需要对其他元素进行移动。这使得 LinkedList 在添加或删除元素方面比 ArrayList 更快。
- 由于没有连续的内存，并且需要遍历整个链表才能找到指定元素，因此查询某个元素的时间复杂度为 O(n)，而添加或删除元素的时间复杂度为 O(1)。
Set
- Set 是一个不允许有重复元素的集合，元素没有特定的顺序。
- 可以用来判断某个元素是否在集合￥￥现过。
- 常用的实现类包括 HashSet 和 TreeSet。
HashSet
- 底层是基于 HashMap 来实现的，内部维护了一个 HashMap 实例作为其成员变量。
- 添加元素时，将元素作为 key 存储在 HashMap 中，value 为一个固定的常量对象。
- 由于 HashMap 底层使用了哈希表，因此可以快速查找某个元素是否已存在集合中，时间复杂度为 O(1)。
- 不保证遍历顺序，也不保证插入顺序。
TreeSet
- 底层是基于红黑树实现的，每个元素都必须实现 Comparable 接口或向构造函数传递一个 Comparator 对象。
- 每个节点对应一个元素，且每个节点具有以下性质：
- 如果一个节点有左子节点，则左子节点上的所有元素都比该节点上的元素小；
- 如果一个节点有右子节点，则右子节点上的所有元素都比该节点上的元素大；
- 左右子树自身都是一棵二叉搜索树。
- 由于 TreeSet 底层采用了红黑树，因此平均情况下添加元素、删除元素、查找元素的时间复杂度都为 O(logn)。
- 确保元素按升序排列，或者在创建时通过传递 Comparator 实例来自定义排序方式。
Map
- Map 是一个键值对映射的集合，允许键和值都可以为 null，但键不能重复，值可以重复。
- 可以用于存储一些关联性比较强的数据对象，例如电话簿、字典等。
- 常用的实现类包括 HashMap 和 TreeMap。
HashMap
- 底层也是基于哈希表来实现的，内部维护了一个数组，每个元素都是一个链表或树的首节点，用于解决哈希冲突。
- 添加元素时，会根据 key 的 hash 值进行散列，然后找到对应的数组位置，如果该位置上已经存在元素，则以链表或树结构的形式将其插入。
- HashMap 可以快速查找某个 key 对应的 value 是否存在集合中，时间复杂度为 O(1)（如果哈希函数设计得好）。
- 遍历顺序和插入顺序都不保证。
TreeMap
- 底层是基于红黑树实现的，每个键值对都被封装成一个 Entry 对象，按照键的自然顺序或指定 Comparator 排序。
- TreeMap 中的所有元素都保证按照排序规则排列，在遍历 TreeMap 时可以获得有序的键值对列表。
- 添加、删除、查找元素的时间复杂度都为 O(logn)，其中 n 表示元素个数。
- TreeMap 可以自定义排序方式，并且支持限制只允许包含实现了 Comparable 接口的键类型。
总结
List
List是Java集合框架中最基本和最常用的一种数据结构，它是有序集合，可以允许重复的元素。List提供了按照索引来插入、删除和获取指定位置上的元素等操作。
Java中List有很多实现类，比较常用的有：
- ArrayList：基于数组实现，以及动态扩容。
- LinkedList：基于链表实现，适合于频繁添加、删除元素操作。
Set
Set也是Java集合框架中的一种数据结构，它是由不同元素组合而成的无序集合，不允许有重复元素。Set的主要目的是为了消除重复元素。
Java中Set的实现类有：
- HashSet：基于哈希表实现，可快速判断对象的唯一性。
- TreeSet：基于红黑树实现，可以对元素排序并保证元素唯一性。
- LinkedHashSet：基于哈希表和链表实现，保留插入时顺序并保证元素唯一性。
Map
Map也是Java集合框架中最常用的一种数据结构，它是由键值对组成的集合，每个键只能出现一次，而且每个键只能映射到一个值。
Java中Map有很多实现类，比较常用的有：
- HashMap：基于哈希表实现，以键值对的形式进行存储和访问。
- TreeMap：基于红黑树实现，可以对键进行排序并保证键的唯一性。
- LinkedHashMap：基于哈希表和链表实现，按照插入顺序维护元素的次序。