一、Collection和Map的继承体系

 

2、Map接口继承图

二、Collection详解

1、接口方法

- int size();// 获取集合元素数量
- boolean isEmpty();// 集合是否为空
- boolean contains(Object o);// 集合是否包含某元素
- Iterator iterator();// 返回iterator对象,用于遍历
- Object[] toArray();// 把集合数据转成数组存储(可能会导致向下转型后错误)
- T[] toArray(T[] a);// 构造的数组对象类型和参数的类型一致
- boolean add(E e);// 添加元素
- boolean remove(Object o);// 移除元素
- boolean containsAll(Collection c);// 集合中是否包含某集合
- boolean addAll(Collection c);// 添加集合
- boolean removeAll(Collection c);// 移除集合c
- boolean retainAll(Collection c);// 与集合c是否有交集
- void clear();// 清空集合
- boolean equals(Object o);// 比较相等
- int hashCode();// 获取集合hashCode值

2、Set子接口

Set集合不允许包含相同的元素,而判断两个对象是否相同则是根据equals方法。
(1)HashSet
HashSet是Set接口的典型实现类。特点:
1. 不能保证元素的排列顺序,加入的元素要特别注意hashCode()方法的实现。
2. HashSet不是同步的,多线程访问同一步HashSet对象时,需要手工同步。
3. 集合元素值可以是null。

(2)LinkedHashSet
LinkedHashSet类也是根据元素的hashCode值来决定元素的存储位置,但它同时使用链表维护元素的次序。与HashSet相比,特点:
1. 对集合迭代时,按增加顺序返回元素。
2. 性能略低于HashSet,因为需要维护元素的插入顺序。但迭代访问元素时会有好性能,因为它采用链表维护内部顺序。

(3)SortedSet、TreeSet

TreeSet类是SortedSet接口的实现类。因为需要排序,所以性能肯定差于HashSet。与HashSet相比,额外增加的方法有:
1. first():返回第一个元素
2. last():返回最后一个元素
3. lower(Object o):返回指定元素之前的元素
4. higher(Obect o):返回指定元素之后的元素
5. subSet(fromElement, toElement):返回子集合

可以定义比较器(Comparator)来实现自定义的排序。默认自然升序排序。
(4)EnumSet
EnumSet类是专为枚举类设计的集合类,EnumSet中的所有元素都必须是指定枚举类型的枚举值。《Effective Java》第32条,用EnumSet代替位域,示范:
import java.util.*;
public class Text {
public enum Style { BOLD, ITALIC, UNDERLINE, STRIKETHROUGH }
// 任何集合都可以传入,但EnumSet显然是最好的
public void applyStyles(Set‹Style› styles) {
// ...
}
// 简单调用
public static void main(String[] args) {
Text text = new Text();
text.applyStyles(EnumSet.of(Style.BOLD, Style.ITALIC));
}
}

3、List子接口

List子接口是有序集合,所以与Set相比,增加了与索引位置相关的操作:
- add(int index, Object o):在指定位置插入元素
- addAll(int index, Collection c):...
- get(int index):取得指定位置元素
- indexOf(Obejct o):返回对象o在集合中第一次出现的位置
- lastIndexOf(Object o):...
- remove(int index):删除并返回指定位置的元素
- set(int index, Object o):替换指定位置元素
- subList(int fromIndex, int endIndex):返回子集合

(1)ArrayList、Vector
这两个类都是基于数组实现的List类。
ArrayList是线程不安全的,而Vector是线程安全的。但Vector的性能会比ArrayList低,且考虑到兼容性的原因,有很多重复方法。
Vector提供一个子类Stack,可以挺方便的模拟“栈”这种数据结构(LIFO,后进先出)。
结论:不推荐使用Vector类,即使需要考虑同步,即也可以通过其它方法实现。同样我们也可以通过ArrayDeque类或LinkedList类实现“栈”的相关功能。所以Vector与子类Stack,建议放进历史吧。

(2)LinkedList
不像ArrayList是基于数组实现的线性表,LinkedList类是基于链表实现的。
另外还有固定长度的List:Arrays工具类的方法asList(Object… a)可以将数组转换为List集合,它是Arrays内部类ArrayList的实例,特点是不可以增加元素,也不可以删除元素。

4、Queue子接口

Queue用于模拟队列这种数据结构,实现“FIFO(先入先出队列)”等数据结构。通常,队列不允许随机访问队列中的元素。

Queue 接口并未定义阻塞队列的方法,而这在并发编程中是很常见的。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法,这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素,尽管某些实现(如 LinkedList)并不禁止插入 null。即使在允许 null 的实现中,也不应该将 null 插入到 Queue 中,因为 null 也用作 poll 方法的一个特殊返回值,表明队列不包含元素。

基本操作:
boolean add(E e) : 将元素加入到队尾,不建议使用
boolean offer(E e): 将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。推荐使用此方法取代add
E remove(): 获取头部元素并且删除元素,不建议使用
E poll(): 获取头部元素并且删除元素,队列为空返回null;推荐使用此方法取代remove
E element(): 获取但是不移除此队列的头
E peek(): 获取队列头部元素却不删除元素,队列为空返回null

(1)PriorityQueue

PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序,而是按队列元素的大小重新排序。当调用peek()或者是poll()方法时,返回的是队列中最小的元素。当然你可以与TreeSet一样,可以自定义排序。自定义排序的一个示范:
@Test
public void testPriorityQueue() {
PriorityQueue‹Integer› pq = new PriorityQueue‹Integer›(20, new Comparator‹Integer›() {
public int compare(Integer i, Integer j) {
// 对数字进行奇偶分类,然后比较返回;偶数有较低的返回值(对2取余数然后相减),奇数直接相减。
int result = i % 2 - j % 2;
if (result == 0)
result = i - j;
return result;
}
});
// 倒序插入测试数据
for (int i = 0; i ‹ 20; i++) {
pq.offer(20 - i);
}
// 打印结果,偶数因为有较低的值,所以排在前面
for (int i = 0; i ‹ 20; i++) {
System.out.println(pq.poll());
}
}

(2)Deque、ArrayDeque

Deque代表一个双端队列,可以当作一个双端队列使用,也可以当作“栈”来使用,因为它包含出栈pop()与入栈push()方法。

ArrayDeque类为Deque的实现类,数组方式实现。方法有:
addFirst(Object o):元素增加至队列开头
addLast(Object o):元素增加至队列末尾
poolFirst():获取并删除队列第一个元素,队列为空返回null
poolLast():获取并删除队列最后一个元素,队列为空返回null
pop():“栈”方法,出栈,相当于removeFirst()
push(Object o):“栈”方法,入栈,相当于addFirst()
removeFirst():获取并删除队列第一个元素
removeLast():获取并删除队列最后一个元素

(3)LinkedList

LinkedList类是List接口的实现类,同时它也实现了Deque接口。因此它也可以当做一个双端队列来用,也可以当作“栈”来使用。并且,它是以链表的形式来实现的,这样的结果是它的随机访问集合中的元素时性能较差,但插入与删除操作性能非常出色。

5.各种线性表选择策略

  1. 数组:是以一段连续内存保存数据的;随机访问是最快的,但不支持插入、删除、迭代等操作。
  2. ArrayList与ArrayDeque:以数组实现;随机访问速度还行,插入、删除、迭代操作速度一般;线程不安全。
  3. Vector:以数组实现;随机访问速度一般,插入、删除、迭代速度不太好;线程安全的。
  4. LinkedList:以链表实现;随机访问速度不太好,插入、删除、迭代速度非常快。

三、Map详解

1、Map接口的基本操作:

  • V put(K key, V value): 将指定的值与此映射中的指定键相关联(可选操作)。如果此映射中以前包含一个该键的映射关系,则用指定值替换旧值。
  • boolean containsKey(Object key): 如果此映射包含指定键的映射关系,则返回 true。
  • boolean containsValue(Object value): 如果此映射为指定值映射一个或多个键,则返回 true。
  • Set<Map.Entry<K,V>> entrySet(): 返回此映射中包含的映射关系的 set 视图。
  • V get(Object key): 返回指定key对应的value
  • V remove(Object key): 删除指定key对应的key-value对

2. Map的遍历可以使用Iterator接口或者是foreach循环来实现

3. HashMap类和Hashtable类

  • Hashtable是线程安全的,而HashMap不是线程安全的。
  • Hashtable不允许null作为key和value,而HashMap则可以使用null作为key和value。
    不建议使用Hashtable类,它是一个很古老的类,从JDK1.0开始。如果要考虑线程安全,建议使用Collections工具类将HashMap转换为线程安全的。

(1)Properties
Properties类从Hashtable类继承而来。额外方法主要有:

  • void load(InputStream inStream): 从属性文件加载key-value对
  • void store(OutputStream out, String comments): 将当前的所有key-value对输出到指定属性文件
  • String getProperty(String key): 获取指定key对应的value值
  • String getProperty(String key, String defaultValue): 用指定的键在属性列表中搜索属性。如果在属性列表中未找到该键,则接着递归检查默认属性列表及其默认值。如果未找到属性,则此方法返回默认值变量。
  • Object setProperty(String key, String value): 调用 Hashtable 的方法 put。使用 getProperty 方法提供并行性。

Properties还可以把key-value对以XML文件的格式保存,也可以从XML文件中加载。loadFromXML(InputStream in)及storeToXML(OutputStream os, String comment)。

(2)LinkedHashMap

LinkedHashMap从HashMap类继承而来。以链表来维护内部顺序。很多方面跟LinkedHashSet类似。LinkedHashMap它可以记住key-value对的添加时的顺序, 同时避免使用TreeMap时性能受到的影响。

4. SortedMap接口及其TreeMap实现类

类似于SortedSet及TreeSet,TreeMap也可以自定义比较器(Comparable)实现定制排序。它的额外提供的方法也与TreeSet类似,增加了访问第一个、前一个、后一个、最后一个key-value对的方法,并提供了从TreeMap中提取子集的方法。TreeMap不允许null作为key,要不然怎么比较呢?

firstEntry()
firstKey()
lastEntry()
lastKey()
higerEntry()
higerKey()
……
subMap(Object fromKey, Object toKey)

5. IdentityHashMap

与HashMap的不同在于,只有两个key严格相等(key1 == key2)时,IdentityHashMap才认为两个key相等;而对于普通HashMap而言,只要key1.equals(key2)且hashCode相同即可。同样允许null值,不能保证顺序。

6. EnumMap类

EnumMap是一个与枚举类一起使用的Map实现。它的key必须是单个枚举类的枚举值。EnumMap不允许使用null作为key,但可作为value。

7. 各种Map实现类选择策略

  • 正常情况使用HashMap,而不是Hashtable。
  • 如果考虑排序,那么考虑使用TreeMap。通常TreeMap比HashMap等在插入、删除操作时要慢不少,因为它需要在底层采用红黑树来管理key-value对。
  • 如果考虑插入时的顺序,那么使用LinkedHashMap是个不错的选择。
  • 如果想优化垃圾回收,建议使用WeakHashMap实现类(本文未提及);要求key完全匹配(同一对象),则使用IdentityHashMap;还有枚举类不多说了。
  • 关于null值:Hashtable不允许key为null,也不允许value为null;TreeMap与EnumMap不允许key为null;HashMap及其子类LinkedHashMap,IdentityHashMap允许key为null。