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：基于哈希表和链表实现，按照插入顺序维护元素的次序。