本章是整理知识内容,为强化知识长期更新。
Java集合
集合是Java提供的工具包、包含常用的数据结构:集合、链表、队列、栈、数组、映射等。Collection的包是java.util.*。
Collection
Map
实际上还有Cloneable、Serializable接口是都集合类需要实现的,通用所以不不画上去了。
Java集合主要划分4个部分:
- List(列队)
- Set(集合)
- Map(映射)
- 工具类(Iterator迭代器、Enumeration枚举类、Arrays、Collections)
划重点
- Conllection
- List
ArrayList
Vector
- Stack
LinkedList
- Set
HashSet
TreeSet
LinkedHashSet
- Queue
- List
- Map
HashMap
HashTable
TreeMap
- 工具
- Arrays
- Collections
- Enumeration
Java类库中具体集合
集合类型 | 概括 |
---|---|
ArrayList |
一种可以动态增长和缩减的索引序列,访问速度很快但是插入和删除比ArrayList慢。 |
LinkedList |
一种可以在任何位置进行高效地插入和删除操作的有序序列,但是访问比较ArrayList慢。 |
ArrayDeque |
一种循环数组实现的双端序列。 |
HashSet |
一种没有重复元素的无序集合。 |
TreeSet |
一种有序集合。 |
EnumSet<E extends Enum |
一种包含枚举类型的集合。 |
LinkedHashSet |
一种可以记住元素插入顺序的集合。 |
PriorityQueue |
一种允许高效删除最小元素的集合。 |
HashMap<K , V> | 一个存储 键 / 值 关联的数据结构。 |
TreeMap<K , V> | 一种键值有序排列的映射表。 |
EnumMap<K extends Enum |
一种键属于枚举类型的映射表。 |
LinkedHashMap<K ,V > | 一种可以记住键 / 值 项添加顺序的映射表。 |
WeakHashMap<K , V > | 一种其值无用武之地后可以被垃圾回收回收的映射表。 |
IdentityHashMap<K , V> | 一种用 == 而不是用用 equals 比较的映射表。 |
介绍下Java Collection Interface
1. Set
- TreeSet:基于红黑树实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如 HashSet,HashSet 查找的时间复杂度为 O(1),TreeSet 则为 O(logN)。
- HashSet:基于哈希表实现,支持快速查找,但不支持有序性操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
- LinkedHashSet:具有 HashSet 的查找效率,并且内部使用双向链表维护元素的插入顺序。
2. List
- ArrayList:基于动态数组实现,支持随机访问。
- Vector:和 ArrayList 类似,但它是线程安全的。
- LinkedList:基于双向链表实现,只能顺序访问,但是可以快速地在链表中间插入和删除元素。不仅如此,LinkedList 还可以用作栈、队列和双向队列。
3. Queue
- LinkedList:可以用它来实现双向队列。
- PriorityQueue:基于堆结构实现,可以用它来实现优先队列。
4. Map
- TreeMap:基于红黑树实现。
- HashMap:基于哈希表实现。
- HashTable:和 HashMap 类似,但它是线程安全的,这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类,不应该去使用它,而是使用 ConcurrentHashMap 来支持线程安全,ConcurrentHashMap 的效率会更高,因为 ConcurrentHashMap 引入了分段锁。
- LinkedHashMap:使用双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用(LRU)顺序。
泛型E
该接口封装了不同类型的结合,使得开发人员操作集合的时候不必关心他们具体的实现,核心的集合接口是Java集合框架的基础。证如上图看到的核心集合接口的层次关系。
Interface
首先简单的介绍下接口以及接口的方法,便于后面的深入学习。
Iterator
Iterable
Collection
Queue
- LinkedList 双向列队结构。
- PriorityQueue 基于堆机构实现,可以用来做优先级列队。
Set
- HashSet 基于哈希实现,支持快速查找,但不支持有序性操作,例如根据一个范围查找元素的操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
- TreeSet 基于红黑树实现,支持有序性操作,但是查找效率不如 HashSet,HashSet 查找时间复杂度为 O(1),TreeSet 则为 O(logN);
LinkedHashSet 具有 HashSet 的查找效率,且内部使用链表维护元素的插入顺序。
List
- ArrayList 基于动态数组实现,支持随机访问元素。
- Vector 和ArrayList类似,但是它是线程安全的。
- Stack 是Vector的子类,它实现了一个标准的后进先出的栈。
- LinkedList 基于双向循环列表,只能顺序访问;可以快速的插入和删除元素。而且,LinkedList还可以用作栈、列队和双端列队。
Map<K , V >
需要特别说明下Irertor<E> 和Iterable<T>这两个接口,Iterator模式是用于遍历集合类的标准方法。它主要用于将 访问逻辑从不同的类型集合类中抽象出来、所以在很多实现了Iterble集合类中实现这个多个Iterator接口。这样避免向客用户包撸集合内部的结构,这就是为什么我们用的这么爽的原因之一。
实现类一览表
Collction | 排序 | 随机访问 | Key-Value | 可重复元素 | 空元素 | 线程安全 |
---|---|---|---|---|---|---|
ArrayList | Y | Y | N | Y | Y | N |
LinkedList | Y | N | N | Y | Y | N |
HashSet | N | N | N | N | Y | N |
TreeSet | Y | N | N | N | N | N |
HashMap | N | Y | Y | N | Y | N |
TreeMap | Y | Y | Y | N | N | N |
Vector | Y | Y | N | Y | Y | Y |
Stack | Y | N | N | Y | Y | Y |
Hashtable | N | Y | Y | N | N | Y |
Properties | Y | N | N | Y | Y | Y |
CopyOnWriteArrayList | Y | Y | Y | N | N | Y |
ConcurrentHashMap | N | Y | Y | N | N | Y |
CopyOnWriteArrayList | N | N | N | N | Y | Y |
Iterator 接口
- 迭代器必须从属容器、其作用就是迭代所属容器中的元素。源代码看出这是一个泛型接口。就是迭代泛型类元素。
1 | public interface Iterator<E> { |
Iterable 接口
- 这个接口被Collection继承。
1 | public interface Iterable<T> { |
Collection 接口
- 这个接口集合接口。
1 | public interface Collection<E> extends Iterable<E> { |
Map 接口
翻译成中文就是地图,x y 坐标代表地图上的一个位置。Map就是一种 键\值的存在。键好比地图中的x y ,值好比地图中的位置。
1 | public interface Map<K,V> { |