Java集合 - 简介
# 1 Collection
容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对 (两个对象) 的映射表。
有序性
有序性,遍历时可根据插入顺序遍历,无序则反之。
# 1.1 Set
# 1.1.1 TreeSet
数据结构:红黑树
查询时间复杂度:
说明:特殊的 TreeMap,查找效率不如哈希表实现的,支持有序性操作
# 1.1.2 HashSet
数据结构:哈希表
查询时间复杂度:
说明:特殊的 HashMap,支持快速查找,不支持有序性操作。
# 1.1.3 LinkedHashSet
数据结构:哈希表 + 双向链表
查询时间复杂度:
说明:支持快速查找,支持有序性操作。
# 1.2 List
# 1.2.1 ArrayList
数据结构:(动态) 数组
查询时间复杂度:
说明:支持随机访问
# 1.2.2 Vector
数据结构:(动态) 数组
查询时间复杂度:
说明:支持随机访问,线程安全的
# 1.2.3 LinkedList
数据结构:双向链表
查询时间复杂度:
说明:基于双向链表实现,只能顺序访问,但是可以快速地在链表中间插入和删除元素。不仅如此,LinkedList 还可以用作栈、队列、双向队列。
# 1.3 Queue
# 1.3.1 LinkedList
虽然是一个 List,但它可以实现 Queue 的功能。
# 1.3.2 PriorityQueue
数据结构:小顶堆 (完全二叉树,任意一个非叶子节点的权值,都不大于其左右子节点的权值)
查询时间复杂度:
说明:基于堆结构实现,可以用它来实现优先队列。
# 2 Map
# 2.1 TreeMap
数据结构:红黑树
查询时间复杂度:
说明:查找效率不如哈希表实现的,支持有序性操作
# 2.2 HashMap
数据结构:
- JDK7:数组 + 链表
- JDK8:数组 + 链表 (或红黑树)
查询时间复杂度:
说明:线程不安全,扩容时会出现问题
# 2.3 Hashtable
数据结构:数组 + 链表
查询时间复杂度:
说明:和 HashMap 类似,但它是线程安全的,这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类,不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全,并且 ConcurrentHashMap 的效率会更高,因为 ConcurrentHashMap 引入了分段锁。
# 2.4 LinkedHashMap
数据结构:HashMap (数组 + 链表 [+ 红黑树]) + LinkedList (双向链表)
查询时间复杂度:
说明:LinkedHashMap 是 HashMap 的一个子类,保存了记录的插入顺序 (有序性)。