当前位置: 首页>后端>正文

【java容器的刻意练习】【一】容器的介绍

容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。

【java容器的刻意练习】【一】容器的介绍,第1张
Collection (图片来源网络,侵删)

Collection

List:有先后顺序,数值不唯一

ArrayList
  • 基于数组实现List接口。
  • 由于基于数组实现,连续内存,所以擅长于顺序访问和随机下标访问,速度最快,时间复杂度是O(1)
  • 用会自动扩增容量的Array([],最高效,但是容量固定但不可动态改变)。
  • 数组扩容是对ArrayList效率影响比较大的一个因素。每当执行Add、AddRange、Insert、InsertRange等添加元素的方法,都会检查内部数组的容量是否不够了,如果不够,它就会以当前容量的两倍来重新构建一个数组,将旧元素Copy到新数组中,然后丢弃旧数组,在这个临界点的扩容操作,应该来说是比较影响效率的。
  • 按内容查找逐个遍历,速度较慢,时间复杂度是,时间复杂度是O(N)。
  • 增、删操作导致元素大量移动,非常耗时,时间复杂度是O(N)。
LinkedList
  • 基于头尾相连的双向链表实现,只能顺序或逆序访问,但是可以快速地在链表中间插入和删除元素,时间复杂度是O(1)
  • 随机访问速度较慢,时间复杂度是O(N)。
  • 用作栈、队列和双向队列。

Set:无先后顺序,数值唯一

HashSet
  • 底层使用HashTable实现。
  • 添加快、内容查询快、删除快,都是O(1)。
  • 无先后顺序,无大小顺序,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
LinkedHashSet
  • 具备HashSet优点,但是添加、删除会比HashSet慢一点
  • 内部使用双向链表维护元素的插入先后顺序。
TreeSet
  • 红黑树(有序的自平衡二叉树)
  • 有大小顺序
  • 查询内容O(logN)比List的O(N)快,比HashSet的O(1)慢
EnumSet
  • 以位向量的形式存储,对象占用内存很小,而且运行效率很好。尤其是进行批量操作(如调用containsAll()和retainAll()方法)时,如果其参数也是EnumSet集合,则该批量操作的执行速度也非常快。

Set整理思路

  1. HashSet的性能总是比TreeSet好(特别是最常用的添加、查询元素等操作),因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时,才应该使用TreeSet,否则都应该使用HashSet
  2. 对于普通的插入、删除操作,LinkedHashSet比HashSet要略慢一点,这是由维护链表所带来的开销造成的。不过,因为有了链表的存在,遍历LinkedHashSet会更快
  3. EnumSet是所有Set实现类中性能最好的,但它只能保存同一个枚举类的枚举值作为集合元素
  4. HashSet、TreeSet、EnumSet都是"线程不安全"的,通常可以通过Collections工具类的synchronizedSortedSet方法来"包装"该Set集合。
    SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

Queue

LinkedList
  • 实现双向列表队列
PriorityQueue
  • 基于堆结构实现,实现了优先级队列
  • 队首元素优先级最高
  • 默认按照元素比较多顺序排序,此时要实现comparable接口
  • 也可以传入Compartor自定义排序对象,此时不实现comparable接口
  • 可以实现

Map

HashTable

  • 与HashMap类似,但是是线程安全的
  • 现在可以使用 ConcurrentHashMap 来支持线程安全,并且 ConcurrentHashMap 的效率会更高,因为 ConcurrentHashMap 引入了分段锁。

LinkedHashTable

  • 使用双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用(LRU)顺序。

HashMap

  • 基于哈希表实现

TreeMap

  • 基于红黑树实现(有序的自平衡二叉树)

Map整理思路

  1. HashMap和Hashtable的效率大致相同,因为它们的实现机制几乎完全一样。但HashMap通常比Hashtable要快一点,因为Hashtable需要额外的线程同步控制
  2. TreeMap通常比HashMap、Hashtable要慢(尤其是在插入、删除key-value对时更慢),因为TreeMap底层采用红黑树来管理key-value对
  3. 使用TreeMap的一个好处就是: TreeMap中的key-value对总是处于有序状态,无须专门进行排序操作

如何记录每一个容器的结构和所属体系呢?

看名字!后缀名就是该集合所属的体系。前缀名就是该集合的数据结构。

看到array:就要想到数组,就要想到查询块,有下标。

看到link:就要想到链表,就要想到增删快,就要想到add,get,remove+first last的方法。

看到hash:就要想到哈希表,就要想到唯一性,就要想到元素需要覆盖hashCode方法和equals方法。

看到tree:就要想到二叉树,就要想到排序,就要想到两个接口Comparator,Comparable。

而且通常这些常用的集合容器都是不同步的。


https://www.xamrdz.com/backend/3z51920732.html

相关文章: