Java基础的数据结构类梳理和总结

   虽然用了Java多年,但一直没有对其基础的数据结构类做过系统的总结。最近有个契机,我对其进行了全面总结,以便后续在使用时能够快速索引和参考。
    Java 中的基础数据结构主要包括集合框架(Collection Framework)和映射(Map)。它们提供了多种接口和实现类,便于开发者高效地管理和操作数据。这些数据结构的继承关系错综复杂,但可以通过几个核心接口和类来理解其主要结构。如下图:

 

图中可以看出主要分为Collection和Map体系,这里对其分别进行拆解。

Collection体系:

List(列表)

  • List是有序集合,允许重复元素。
  • 常见的实现类有ArrayList和LinkedList
    • ArrayList基于动态数组实现,支持随机访问。
    • LinkedList基于链表实现,支持高效的插入和删除操作。
Set(集)
  • Set是不允许重复元素的集合,不保证元素的顺序。
  • 常见的实现类有HashSet、TreeSet和LinkedHashSet。
    • HashSet基于哈希表实现,具有快速查找的特性。
    • TreeSet基于红黑树实现,提供了有序的集合。
    • LinkedHashSet继承自HashSet,但保留了元素的插入顺序。
Queue(队列)
  • Queue是一种先进先出(FIFO)的数据结构,常用于任务调度等场景。
  • 常见的实现类有LinkedList,PriorityQueue,PriorityBlockingQueue。
    • LinkedList 实现一个先进先出的队列。
    • PriorityQueue 实现了一个优先队列:从队首获取元素时,总是获取优先级最高的元素。非阻塞、非线程安全、无边界。
    • PriorityBlockingQueue:支持优先级排序的无边界阻塞队列实现类,阻塞、线程安全、无边界。
Deque(双端队列):
  • Deque是一种同时支持在两端进行插入和删除操作的队列,可以作为栈使用。
  • 常见的实现类有ArrayDeque,LinkedList,ConcurrentLinkedDeque。
    • ArrayDeque是基于动态数组实现的双端队列,适用于栈(LIFO)和队列(FIFO)两种场景。
    • LinkedList实现了Deque接口,基于双向链表,可用作队列、双端队列、栈,支持所有List接口。
    • ConcurrentLinkedDeque是一个基于链表的无界线程安全双端队列,并发操作高效,适用于多线程环境。基于CAS(Compare-And-Swap)算法实现。

Map 体系

Map接口表示键值对的集合,不允许重复的键,但允许重复的值。
  • 其主要实现类包含: HashMap,LinkedHashMap,HashTable,TreeMap。
  • HashMap基于哈希表的实现,允许null键和null值。提供常数时间复杂度的基本操作(如插入、删除和访问),但不保证顺序。非线程安全,适用于单线程环境。
  • LinkedHashMap继承自HashMap,并且通过双向链表维护插入顺序。除了具有HashMap的所有特性,还维护了键值对的插入顺序或访问顺序。非线程安全,适用于单线程环境。
  • HashTable基于哈希表的实现,类似于HashMap,但不允许null键和null值。所有方法都是同步的,因此是线程安全的,但性能相对较低。线程安全,适用于多线程环境。
  • TreeMap基于红黑树实现的有序映射,键值对按键的自然顺序或通过提供的Comparator进行排序。提供O(log n)时间复杂度的基本操作,键值对是有序的,非线程安全,适用于单线程环境。
QA环节:
1、除了以上的类,还有其他的类吗?
答:有很多其他的类,如果一些复杂的功能以上类无法满足,除了自己实现之外,可参考官网文档寻找其他类:Java Platform, Standard Edition 8 API Specification—https://docs.oracle.com/javase/8/docs/api/
2、选择基础类时,是否需要关注线程安全?
答:对于无需考虑多线程的情况下,优先选择非线程安全,因为其性能较好。

原创文章,作者:guozi,如若转载,请注明出处:https://www.sudun.com/ask/90881.html

(0)
guozi的头像guozi
上一篇 2024年6月7日
下一篇 2024年6月7日

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注