媒体网站推进信息化建设,照明网站建设,wordpress系统付费,深圳外贸网站建设设计公司Java中List、Set、Map的区别和实现方式
List
List 是一个有序的集合#xff0c;即元素按照插入的顺序进行排序#xff0c;可以有重复的元素。因为是有序的#xff0c;所以可以根据下标来获取元素或者遍历整个集合内的元素。常用的实现类包括 ArrayList 和 LinkedList。
A…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基于哈希表和链表实现按照插入顺序维护元素的次序。
