集合/容器
Java集合由Collection
Map
两个接口派生而出,Collection
代表序列式容器,Map
代表关联式容器.
Collection
Collection
作为List
Queue
Set
等序列式容器的父接口, 提供了一些公共基础方法:
update相关方法:
boolean add(E e)
boolean addAll(Collection<? extends E> c)
void clear()
boolean remove(Object o)
boolean removeAll(Collection<?> c)
boolean retainAll(Collection<?> c)
(取交集)select相关方法
boolean contains(Object o)
boolean containsAll(Collection<?> c)
Iterator<E> iterator()
Object[] toArray()
<T> T[] toArray(T[] a)
boolean isEmpty()
int size()
详细可参考JDK文档
Iterator
iterator()
方法返回一个迭代器Iterator
.与其他容器主要用于存储数据不同,Iterator
主要用于遍历容器. Iterator
隐藏了各类容器的底层实现细节,向应用程序提供了一个遍历容器的统一接口:
方法 | 释义 |
---|---|
boolean hasNext() |
Returns true if the iteration has more elements. |
E next() |
Returns the next element in the iteration. |
void remove() |
Removes from the underlying collection the last element returned by this iterator (optional operation). |
注意: 当遍历
Collection
时不要使用Collection
自带的remove
方法删除数据,确实需要删除时,需要使用Iterator
提供的remove
.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
Java 1.5提供foreach
循环使得代码更加简洁,但实际foreach
迭代容器元素底层也是用的Iterator
,这一点可以在调试时看得很清楚.
List
List
代表有序/可重复集合,因此List
在Collection
的基础上添加了根据索引来操作元素的方法:
方法 | 描述 |
---|---|
void add(int index, E element) |
Inserts the specified element at the specified position in this list (optional operation). |
E get(int index) |
Returns the element at the specified position in this list. |
int indexOf(Object o) |
Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. |
int lastIndexOf(Object o) |
Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element. |
E remove(int index) |
Removes the element at the specified position in this list (optional operation). |
E set(int index, E element) |
Replaces the element at the specified position in this list with the specified element (optional operation). |
List<E> subList(int fromIndex, int toIndex) |
Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. |
List
判断两个元素是否相等是通过equals()
方法.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
ListIterator
List
增加了返回ListIterator
的方法:
方法 | 描述 |
---|---|
ListIterator<E> listIterator() |
Returns a list iterator over the elements in this list (in proper sequence). |
ListIterator<E> listIterator(int index) |
Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list. |
ListIterator
继承自Iterator
,专门用于操作List
, 在Iterator
的基础上增加了如下方法:
方法 | 描述 |
---|---|
void add(E e) |
Inserts the specified element into the list (optional operation). |
void set(E e) |
Replaces the last element returned by next() or previous() with the specified element (optional operation). |
boolean hasPrevious() |
Returns true if this list iterator has more elements when traversing the list in the reverse direction. |
E previous() |
Returns the previous element in the list and moves the cursor position backwards. |
int previousIndex() |
Returns the index of the element that would be returned by a subsequent call to previous(). |
int nextIndex() |
Returns the index of the element that would be returned by a subsequent call to next(). |
与Iterator
相比增加了前向迭代 获取迭代元素index 以及add set的功能.
ArrayList
ArrayList
是List
基于数组的实现,它封装了一个动态自增长/允许再分配的Object[]
数组:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 1
- 2
- 3
- 4
- 5
- 6
- 7
ArrayList
可以使用initialCapacity
参数来设置该数组的初始长度ArrayList(int initialCapacity)
,或者使用默认长度DEFAULT_CAPACITY = 10
; 当添加元素超过elementData
数组容量时,ArrayList
会重新分配数组, 以容纳新元素:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
如果在创建时就知道ArrayList
的容量,最好同时指定initialCapacity
的大小,以避免重新分配数组,耗费性能.
ArrayList
还提供如下方法来调整initialCapacity
大小:
方法 | 描述 |
---|---|
void ensureCapacity(int minCapacity) |
Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument. |
void trimToSize() |
Trims the capacity of this ArrayList instance to be the list’s current size. |
工具类Arrays
还提供了一个static
方法List<T> asList(T... a)
, 该方法可以把数组或N个对象转换成一个List
集合, 这个List
集合并不是普通的ArrayList
,而是Arrays
内部实现的一个Arrays.ArrayList
(一个固定长度的List
,不可对该集合做add/remove操作).
关于ArrayList
实现原理还可以参考ArrayList源码解析
LinkedList
LinkedList
是基于双向链表实现的List,虽然可以根据索引来访问集合中的元素,但性能不高(平均时间复杂度为O(N)
),但其插入/删除操作非常迅速(尤其是在头尾,平均时间复杂度为O(1)
);除此之外,LinkedList
还实现了Deque
接口,因此还可以当成[双端]队列/栈来使用.
关于LinkedList
的实现原理还可以参考 [1.LinkedList源码解析, 2. 双向循环链表的设计与实现]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
Queue
Queue
用于模拟队列,队列是一种先进先出/FIFO容器,新元素插到队尾(offer
), 访问操作会返回队首元素(poll
). 通常, 队列不允许随机访问队列中的元素:
方法 | 描述 |
---|---|
boolean add(E e) |
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available. |
boolean offer(E e) |
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. |
E element() |
Retrieves, but does not remove, the head of this queue. |
E peek() |
Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty. |
E poll() |
Retrieves and removes the head of this queue, or returns null if this queue is empty. |
E remove() |
Retrieves and removes the head of this queue. |
Queue
有一个PriorityQueue
实现类,另外Queue
还有一个Deque
子接口,代表可以从两端存取数据的队列(因此Deque
可以当成Stack
使用),Java为Deque
提供了ArrayDeque
和LinkedList
两个实现类.
PriorityQueue
PriorityQueue
并不是按照插入队列顺序进行排序,而是按照队列元素的大小(权重)进行排序, 因此element/peek/poll/remove
返回的并不是最早进入队列的元素,而是队列中[权重]最小的元素:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
可以看到遍历PriorityQueue
得到的并不是有序序列, 因为PriorityQueue
内部并不是一个按照顺序排序的数组, 而是一个二叉堆(详细可以参考[1.PriorityQueue源码解析, 2. 堆与堆排序 ]).
由于需要排序,
PriorityQueue
不允许插入null
;
PriorityQueue
的元素有两种排序方式
- 自然排序: 采用自然排序的元素必须实现了
Comparable
接口. - 定制排序: 创建
PriorityQueue
时,传入一个Comparator
实例,该对象负责对元素进行排序,采用定制排序时不要求队列元素实现Comparable
接口.
关于两种排序的详细内容可以参考下面关于TreeMap
的讨论.
Deque-ArrayDeque
Deque
接口代表一个双端队列,提供了如下方法从队列的两端存取数据:
Java为Deque
提供了两个实现类ArrayDeque
(基于数组)与LinkedList
(基于链表);由于ArrayDeque
底层基于数组E[] elements
实现,因此创建时可以指定一个numElements
参数设置elements
数组初始长度,如果不指定numElements
参数,默认数组长度为16
(关于ArrayDeque
的实现原理可参考ArrayDeque源码解析).
Deque
还可以作为栈stack
使用, 他提供了如下方法:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
此外,
LinkedList
也实现了Deque
接口,因此也可以作为Queue
/Deque
的实现类.
Map
Map
用于保存具有映射关系的key-value
数据,key
和value
之间存在单向一对一关系,通过指定的key
,总能找到唯一确定的value
.
update相关
V put(K key, V value)
void putAll(Map<? extends K,? extends V> m)
V remove(Object key)
void clear()
select相关
V get(Object key)
Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K,V>> entrySet()
boolean containsKey(Object key)
boolean containsValue(Object value)
boolean isEmpty()
int size()
Map
内部定义一个Map.Entry<K,V>
接口,封装key-value
对,Entry
提供如下方法:
方法 | 描述 |
---|---|
K getKey() |
Returns the key corresponding to this entry. |
V getValue() |
Returns the value corresponding to this entry. |
V setValue(V value) |
Replaces the value corresponding to this entry with the specified value (optional operation). |
HashMap
HashMap
是基于hash
算法的Map
实现(用它代替Hashtable
),针对key-value
的插入/检索,这种形式具有最稳定的性能(O(1)
),还可通过构造器对这一性能进行调整.
为了成功在HashMap
中存取数据,key
对象必须实现hashCode()
与equals()
方法,HashMap
先通过key
的hashCode()
定位到元素所在桶,如果两个元素在同一个桶,再用equals()
进行判断是否相等.如果两个对象的hashCode()
相同,但equals()
不同, 则将两个对象放在同一个桶的不同链表位置(这样会导致hash
效率下降).如果两个对象通过equals()
返回true
, 但这hashCode()
不同,则非常有可能导致HashMap
将这两个对象分配在不同桶中,从而使这两个对象都添加成功,这就与Map
规则冲突了.(关于HashMap
详细原理可以参考: [1. 哈希表的设计与实现, 2.HashMap源码解析]).
建议: 如果两个对象通过
equals()
方法比较返回true
, 则两个对象的hashCode()
值也相同.
hashCode()
重写规则:
- 运行过程中, 同一个对象多次调用
hashCode()
应具有相同返回值; - 当两个对象通过
equals()
比较返回true
时,hashCode()
应具有相同返回值; - 对象中用作
equals()
比较标准的实例变量, 都应该用于计算hashCode()
.
-
hashCode()
重写方法: -
将每个有意义的实例变量都计算出一个
int
的hashcode
值. -
类型 计算方式 boolean
hashCode = (true ? 1 : 0);
float
hashCode = Float.floatToIntBits(f);
double
long value = Double.doubleToLongBits(f);
hashCode = (int)(value^(value>>>32));
int
/short
/byte
hashCode = (int)i;
long
hashCode = (int)(l^(l>>>32));
引用类型 hashCode = object.hashCode();
-
用上面计算出来的多个
hashcode
组合计算成一个最终的hashcode
,为了避免直接相加产生偶然相等,可以为各个hashcode
乘以任意一个质数再相加:
-
String
实现
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
String
的hashCode()
方法做了一些优化, 叫闪存散列码, 详见数据结构与算法分析 : Java语言描述
- 自定义
Bean
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
-
HashMap
的主要实现逻辑:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
注意
- 当向
Map
类容器(如HashMap
TreeMap
或后面的HashSet
TreeSet
)中添加可变对象时,必须十分小心,如果修改Map
中的key
,有可能导致该key
与集合中的其他key
相等,从而导致无法准确访问该key-value
.因此尽量不要使用可变对象作为Map
的key
,或不要修改作为key
的对象(Set
的value
于此类同)Map
还支持containsValue()
方法来判断一个value
是否存在于Map
中, 但该方法会遍历所有的桶查找这个值, 因此性能较差, 不推荐使用
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
LinkedHashMap
LinkedHashMap
使用双向链表来维护key-value
插入顺序,因此性能略低于HashMap
,但在需要顺序迭代Map
的场景下会有非常好的效率.
LinkedHashMap
提供的addEntry()
方法与HashMap
有所不同,当使用LinkedHashMap
的put()
时, 会从HashMap
调回到LinkedHashMap
的addEntry()
方法,将新元素添加到链表尾:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 使用
LinkedHashMap
统计word出现次数
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
WeakHashMap
WeakHashMap
与HashMap
的区别在于:HashMap
的key
保留了对实际对象的强引用, 这意味着只要该HashMap
不被销毁,则Map
的所有key
所引用的对象不会被垃圾回收;但WeakHashMap
的key
只保留对实际对象的弱引用, 这意味着如果该key
所引用的对象没有被其他强引用变量引用,则该对象可能被垃圾回收,WeakHashMap
也会自动删除这些key
对应的key-value
对.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
如果使用
WeakHashMap
来保留对象的弱引用,则不要让该key
所引用的对象具有任何强引用, 否则将失去使用WeakHashMap
的意义.
IdentityHashMap
与HashMap
不同,IdentityHashMap
判断元素是否相等的标准是用==
而不是equals()
;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
SortedMap-TreeMap
Map
接口派生出SortedMap
接口代表根据key
排序的key-value
集合, TreeMap
作为SortedMap
的实现类是一个红黑树结构,每个key-value
作为红黑树的一个节点.TreeMap
存储key-value
时,根据key
值进行排序.因此TreeMap
可以保证所有元素都处于有序状态,因此SortedMap
在Map
的基础上又添加了如下方法:
方法 | 描述 |
---|---|
Comparator<? super K> comparator() |
Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys. |
K firstKey() |
Returns the first (lowest) key currently in this map. |
K lastKey() |
Returns the last (highest) key currently in this map. |
SortedMap<K,V> headMap(K toKey) |
Returns a view of the portion of this map whose keys are strictly less than toKey. |
SortedMap<K,V> tailMap(K fromKey) |
Returns a view of the portion of this map whose keys are greater than or equal to fromKey. |
SortedMap<K,V> subMap(K fromKey, K toKey) |
Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive. |
而TreeMap
又在SortedMap
的基础上扩展了如下方法:
方法 | 描述 |
---|---|
Map.Entry<K,V> ceilingEntry(K key) |
Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key. |
K ceilingKey(K key) |
Returns the least key greater than or equal to the given key, or null if there is no such key. |
Map.Entry<K,V> floorEntry(K key) |
Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key. |
K floorKey(K key) |
Returns the greatest key less than or equal to the given key, or null if there is no such key. |
Map.Entry<K,V> higherEntry(K key) |
Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key. |
K higherKey(K key) |
Returns the least key strictly greater than the given key, or null if there is no such key. |
Map.Entry<K,V> lowerEntry(K key) |
Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key. |
K lowerKey(K key) |
Returns the greatest key strictly less than the given key, or null if there is no such key. |
Map.Entry<K,V> pollFirstEntry() |
Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty. |
Map.Entry<K,V> pollLastEntry() |
Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty. |
Map.Entry<K,V> firstEntry() |
Returns a key-value mapping associated with the least key in this map, or null if the map is empty. |
Map.Entry<K,V> lastEntry() |
Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty. |
TreeMap
有两种排序方式:
自然排序
TreeMap
的所有key
必须实现Comparable
接口,TreeMap
会调用key
的int compareTo(T o);
方法来比较元素的大小,然后将集合元素升序排列.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 1
- 2
- 3
- 4
- 5
- 6
- 7
Java提供的java.lang.Comparable
接口仅包含一个int compareTo(T o);
方法.大部分常用类都实现了该接口(如String
, Integer
等).
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
与
HashMap
不同,TreeMap
判断两个key
是否相等的唯一标准是:通过compareTo
方法比较返回值是否为0.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 实现
Comparable
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
当执行了
remove
方法后,TreeMap
会对集合中的元素重新索引, 这一点可以在调试时看到.
自定义排序
TreeMap
默认的是使用升序排序,如果需要自定义排序规则,需要为其传入一个Comparator
实例, 采用定制排序时不要求key
实现Comparable
.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
由于
TreeMap
是基于红黑树实现,因此相比HashMap
性能要慢一点(Hash平均O(1)
,Tree平均O(lgN)
详细可参考[1. TreeMap源码解析, 2.红黑树的设计与实现(上)]),但其中的key-value
已是有序状态,无需再有专门的排序操作.因此适用于key
有序的场景.
EnumMap
EnumMap
是一个需要与枚举类一起使用的Map
,其所有key
都必须是单个枚举类的枚举值.EnumMap
具有以下特征:
-
EnumMap
内部以数组形式存储,紧凑/高效,是Map
所有实现中性能最好的. -
EnumMap
根据key
的自然顺序(枚举值在枚举类的定义顺序)来维护key-value
顺序. -
EnumMap
不允许key
为null
, 但允许使用null
作为value
.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 1
- 2
- 3
- 4
- 5
- 6
- 7
Set
Set
与Map
关系非常密切, 虽然Map
中存放的是key-value
, Set
中存放的是单个对象, 但从JDK源代码看, Java是先实现了Map
,然后包装一个空Object
来填充所有的value
来实现的Set
.
- 1
- 2
- 3
- 4
- 1
- 2
- 3
- 4
- 1
- 2
- 3
- 1
- 2
- 3
Set
继承自Collection
, 没有提供额外的方法;
HashSet
HashSet
是Set
接口的典型实现,是Set
中用的最多的实现.由于HashSet
是基于HashMap
实现的,因此具有如下特点:
- 不保证元素的排列顺序;
- 不能同步,如果有多个线程同步访问/修改
HashSet
, 需要开发人员自己保证同步; - 集合元素值可以为
null
;
LinkedHashSet
由于LinkedHashSet
底层是基于LinkedHashMap
实现,因此Set
可以记录元素的插入顺序,当遍历LinkedHashSet
时,将会按照元素的添加顺序来访问集合中的元素:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
LinkedHashSet
的优缺点与LinkedHashMap
类似.
SortedSet-TreeSet
SortedSet
接口继承自Set
,Java为SortedSet
提供了TreeSet
实现,由于SortedSet
可以确保集合元素可以处于已排序状态, 因此在Set
的基础上又提供了如下方法:
类型 | 计算方式 |
---|---|
Comparator<? super E> comparator() |
Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements. |
E first() |
Returns the first (lowest) element currently in this set. |
E last() |
Returns the last (highest) element currently in this set. |
SortedSet<E> tailSet(E fromElement) |
Returns a view of the portion of this set whose elements are greater than or equal to fromElement. |
SortedSet<E> headSet(E toElement) |
Returns a view of the portion of this set whose elements are strictly less than toElement. |
SortedSet<E> subSet(E fromElement, E toElement) |
Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive. |
TreeSet
相比于SortedSet
还提供了如下实用方法:
类型 | 计算方式 |
---|---|
E ceiling(E e) |
Returns the least element in this set greater than or equal to the given element, or null if there is no such element. |
E floor(E e) |
Returns the greatest element in this set less than or equal to the given element, or null if there is no such element. |
Iterator<E> descendingIterator() |
Returns an iterator over the elements in this set in descending order. |
NavigableSet<E> descendingSet() |
Returns a reverse order view of the elements contained in this set. |
E higher(E e) |
Returns the least element in this set strictly greater than the given element, or null if there is no such element. |
E lower(E e) |
Returns the greatest element in this set strictly less than the given element, or null if there is no such element. |
E pollFirst() |
Retrieves and removes the first (lowest) element, or returns null if this set is empty. |
E pollLast() |
Retrieves and removes the last (highest) element, or returns null if this set is empty. |
由于
TreeSet
底层采用TreeMap
实现, 因此其性能特点以及排序规则可以参考TreeMap
.
EnumSet
EnumSet
是专门为枚举设计的Set
,所有的元素必须是单一枚举类的枚举值.EnumSet
也是有序的,以枚举值在Enum
类内定义的顺序来排序;由于EnumSet
没有暴露任何构造器,因此需要通过他提供的如下static
方法来创建EnumSet
实例:
allOf(Class<E> elementType)
complementOf(EnumSet<E> s)
copyOf(Collection<E> c)
noneOf(Class<E> elementType)
of(E first, E... rest)
range(E from, E to)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
EnumSet
的内部以位向量的形式存储,紧凑/高效,因此EnumSet
占用内存小,运行效率高,是Set
实现类中性能最好的. 尤其是批量操作(containsAll()
,retainAll()
)时,如果参数也是EnumSet
, 则执行效率非常快(详细可参考Java EnumSet工作原理初窥).
Collections
Java提供了一个操作List
Map
Set
等集合的工具类Collections
, 其提供了大量的工具方法对集合元素进行排序 查找 更新等操作:
排序相关
sort(List<T> list)
sort(List<T> list, Comparator<? super T> c)
shuffle(List<?> list)
swap(List<?> list, int i, int j)
reverse(List<?> list)
reverseOrder(Comparator<T> cmp)
rotate(List<?> list, int distance)
查找相关
binarySearch(List<? extends Comparable<? super T>> list, T key)
binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
indexOfSubList(List<?> source, List<?> target)
lastIndexOfSubList(List<?> source, List<?> target)
max(Collection<? extends T> coll)
max(Collection<? extends T> coll, Comparator<? super T> comp)
min(Collection<? extends T> coll)
min(Collection<? extends T> coll, Comparator<? super T> comp)
更新相关
addAll(Collection<? super T> c, T... elements)
fill(List<? super T> list, T obj)
nCopies(int n, T o)
不可变集合视图
unmodifiableCollection(Collection<? extends T> c)
unmodifiableList(List<? extends T> list)
unmodifiableMap(Map<? extends K,? extends V> m)
unmodifiableSet(Set<? extends T> s)
unmodifiableSortedMap(SortedMap<K,? extends V> m)
unmodifiableSortedSet(SortedSet<T> s)
单元素集合
Set<T> singleton(T o)
singletonList(T o)
singletonMap(K key, V value)
空集合
emptyList()
emptyMap()
emptySet()
Collections
提供了三个静态变量来代表一个空集合static List EMPTY_LIST
static Map EMPTY_MAP
static Set EMPTY_SET
同步集合
详见Java 并发基础
遗留的集合
Java还提供了一些集合工具:Hashtable
Vactor
Stack
Enumeration
StringTokenizer
(Enumeration
的一个实现类,其功能类似于String
的split()
,但不支持正则,实现将字符串进行分割, 然后迭代取出), 这些集合工具都是从java 1.0开始就存在的, 但其实现要么性能较低(需要保持线程同步), 要么方法名繁琐(如hasMoreElements()
), 现在已经很少使用,而且其使用方法也与前面的集合类似, 因此在此就不做过多介绍了. 如果在实际开发中会遇到还在使用这些工具的代码(比如Dom4j),可以参考JDK文档.
Properties
Properties
是Hashtable
的子类,他可以把Map
和属性文件关联起来,从而可以把Map
对象中的key-value
写入属性文件, 也可以将属性文件中的”属性名=属性值”加载到Map
中,由于属性文件中的属性名/属性值都是String
,因此Properties
的key-value
都只能是String
.Properties
提供了如下方法来读写内存中的key-value
.
方法 | 描述 |
---|---|
String getProperty(String key) |
Searches for the property with the specified key in this property list. |
String getProperty(String key, String defaultValue) |
Searches for the property with the specified key in this property list. |
Object setProperty(String key, String value) |
Calls the Hashtable method put. |
Enumeration<?> propertyNames() |
Returns an enumeration of all the keys in this property list, including distinct keys in the default property list if a key of the same name has not already been found from the main properties list. |
Set<String> stringPropertyNames() |
Returns a set of keys in this property list where the key and its corresponding value are strings, including distinct keys in the default property list if a key of the same name has not already been found from the main properties list. |
Properties
还提供了读写属性文件的方法:
方法 | 描述 |
---|---|
void list(PrintStream/PrintWriter out) |
Prints this property list out to the specified output stream/writer. |
void load(InputStream/Reader in) |
Reads a property list (key and element pairs) from the input byte/character stream. |
void store(OutputStream/Write out, String comments) |
Writes this property list (key and element pairs) in this Properties table to the output stream/write in a format suitable for loading into a Properties table using the load(InputStream/Reader) method. |
- common.properties
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- client
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
Properties
还可以从XML中加载key-value
,也可以以XML形式保存,其用法与普通.properties
文件类似.