java面试热点：集合框架（二）

• Set接口
  Set接口与List接口的重要区别就是它不支持重复的元素，至多可以包含一个null类型元素。Set接口定义的是数学意义上的“集合”概念。
  Set接口主要定义了以下方法：

boolean add(E e)
void clear()
boolean contains(Object o)
boolean isEmpty()
boolean equals(Object obj)
Iterator<E> iterator()
boolean remove(Object o)
boolean removeAll(Collection<?> c)
int size()
Object[] toArray()
<T> T[] toArray(T[] a)

关于set家族，有一下描述：

1. Set接口并没有显式要求其中的元素是有序或是无序的。
2. Set接口有一个叫做SortedSet的子接口，这个接口可以用来实现对Set元素的排序。
3. SortedSet有叫NavigableSet的子接口，这个接口定义的方法可以在有序Set中进行查找和遍历。
4. Jdk类库中实现了Set接口的类主要有：AbstractSet，HashSet，TreeSet，EnumSet，LinkedHashSet等等。其中HashSet与TreeSet都是AbstractSet的子类。
5. Java官方文档中提到，HashSet和TreeSet分别基于HashMap和TreeMap实现（我们在后面会简单介绍HashMap和TreeMap），他们的区别在于Set<E>接口是一个对象的集（数学意义上的”集合“），Map<K, V>是一个键值对的集合。

---

• Queue接口

1. Queue接口是对队列这种数据结构的抽象。
2. 一般的队列实现允许我们高效的在队尾添加元素，在队列头部删除元素（First in, First out)。
3. Queue<E>接口还有一个名为Deque的子接口，它允许我们高效的在队头或队尾添加/删除元素，实现了Deque<E>的接口的集合类即为双端队列的一种实现（比如LinkedList就实现了Deque接口）。
4. 实现Queue接口的类主要有：AbstractQueue， ArrayDeque， LinkedList，PriorityQueue，DelayQueue等等。
   Queue接口定义了以下方法：

boolean add(E e) //添加一个元素到队列中，若队列已满会抛出一个IllegalStateException异常
E element() //获取队头元素
boolean offer(E e) //添加一个元素到队列中，若队列已满返回false
E peek() //获取队头元素，若队列为空返回null
E poll() //返回并移除队头元素，若队列为空返回null
E remove() //返回并移除队头元素

add与offer，element与peek，remove与poll看似是三对儿功能相同的方法。它们之间的重要区别在于前者若操作失败会抛出一个异常，后者若操作失败会从返回值体现出来（比如返回false或null），我们可以根据具体需求调用它们中的前者或后者。

---

• Map接口
  java官方文档对它的定义如下：

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.The Map
interface provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map’s collection views return their elements. Some map implementations, like the TreeMap
class, make specific guarantees as to their order; others, like the HashMap
class, do not.

大概意思是：一个把键映射到值的对象被称作一个Map对象。映射表不能包含重复的键，每个键至多可以与一个值关联。
Map接口提供了三个集合视图（关于集合视图的概念我们下面会提到）：键的集合视图、值的集合视图以及键值对的集合视图。
一个映射表的顺序取决于它的集合视图的迭代器返回元素的顺序。一些Map接口的具体实现（比如TreeMap）,保证元素有一定的顺序，其它一些实现（比如HashMap）则不保证元素在其内部有序。
Map接口让我们能够根据键快速检索到它所关联的值。也就是利用这个特性，Struts2框架中用ContextMap作为容器封装一次请求所需的所有数据。 我们先来看看Map接口定义了哪些方法：

void clear()
boolean containsKey(Object key) //判断是否包含指定键
boolean containsValue(Object value) //判断是否包含指定值
boolean isEmpty()
V get(Object key) //返回指定键映射的值
V put(K key, V value) //放入指定的键值对
V remove(Object key)
int size()
Set<Map.Entry<K,V>> entrySet() 
Set<K> keySet()
Collection<V> values()

Map接口的具体实现类主要有：AbstractMap，EnumMap，HashMap，LinkedHashMap，TreeMap。HashTable。

• 我们看一下HashMap的官方定义：

HashMap<K, V>是基于哈希表这个数据结构的Map接口具体实现，允许null键和null值。这个类与HashTable近似等价，区别在于HashMap不是线程安全的并且允许null键和null值。由于基于哈希表实现，所以HashMap内部的元素是无序的。HashMap对与get与put操作的时间复杂度是常数级别的（在散列均匀的前提下）。对HashMap的集合视图进行迭代所需时间与HashMap的capacity（bucket的数量）加上HashMap的尺寸（键值对的数量）成正比。因此，若迭代操作的性能很重要，不要把初始capacity设的过高（不要把load factor设的过低）。

有两个因素会影响一个HashMap对象的性能：intial capacity（初始容量）和load factor（负载因子）。intial capacity就是HashMap对象刚创建时其内部的哈希表的“桶”的数量（请参考哈希表的定义）。load factor等于maxSize / capacity，也就是HashMap所允许的最大键值对数与桶数的比值。增大load factor可以节省空间但查找一个元素的时间会增加，减小load factor会占用更多的存储空间，但是get与put的操作会更快。当HashMap中的键值对数量超过了maxSize（即load factor与capacity的乘积），它会再散列，再散列会重建内部数据结构，桶数（capacity）大约会增加到原来的两倍。
HashMap的构造器如下：

HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
HashMap(Map<? extends K,? extends V> m) //创建一个新的HashMap，用m的数据填充

常用方法如下：

void clear()
boolean containsKey(Object key)
boolean containsValue(Object value)
V get(Object key)
V put(K key, V value)
boolean isEmpty()
V remove(Object key)
int size()
Collection<V> values()
Set<Map.Entry<K,V>> entrySet()
Set<K> keySet()

它们的功能都很直观，更多的使用细节可以参考Java官方文档，这里就不贴上来了。这里简单地提一下WeakHashMap，它与HashMap的区别在于，存储在其中的key是“弱引用”的，也就是说，当不再存在对WeakHashMap中的键的外部引用时，相应的键值对就会被回收。关于WeakHashMap和其他类的具体使用方法及注意事项，大家可以参考官方文档。

• 下面我们来简单地介绍下另一个Map接口的具体实现——TreeMap。
  它的官方定义是这样的：

TreeMap<K, V>一个基于红黑树的Map接口实现。TreeMap中的元素的有序的，排序的依据是存储在其中的键的natural ordering（自然序，也就是数字从小到大，字母的话按照字典序）或者根据在创建TreeMap时提供的Comparator对象，这取决于使用了哪个构造器。TreeMap的containsKey, get, put和remove操作的时间复杂度均为log(n)。

TreeMap有以下构造器：

TreeMap() //使用自然序对其元素进行排序
TreeMap(Comparator<? super K> comparator) //使用一个比较器对其元素进行排序
TreeMap(Map<? extends K,? extends V> m) //构造一个与映射表m含有相同元素的TreeMap，用自然序进行排列
TreeMap(SortedMap<K,? extends V> m) //构造一个与有序映射表m含有相同元素及元素顺序的TreeMap

它的常见方法如下：

K ceilingKey(K key)
void clear()
Comparator<? super K> comparator() //返回使用的比较器，若按自然序则返回null
boolean containsKey(Object key)
boolean containsValue(Object value)
NavigableSet<K> descendingKeySet() //返回一个包含在TreeMap中的键的逆序的NavigableSet视图
NavigableMap<K,V> descendingMap()
Set<Map.Entry<K,V>> entrySet()
Map.Entry<K,V> firstEntry() //返回键最小的键值对
Map.Entry<K,V> floorEntry(K key) //返回一个最接近指定key且小于等于它的键对应的键值对
K floorKey(K key)
V get(Object key)
Set<K> keySet()
Map.Entry<K,V> lastEntry() //返回与最大的键相关联的键值对
K lastKey()

建议读者先了解下红黑树这个数据结构的原理及实现（可参考算法（第4版） (豆瓣)），然后再去看官方文档中关于这个类的介绍，这样学起来会事半功倍。

• 再简单地介绍下NavigableMap<K, V>这个接口：

实现了这个接口的类支持一些navigation methods，比如lowerEntry（返回小于指定键的最大键所关联的键值对），floorEntry（返回小于等于指定键的最大键所关联的键值对），ceilingEntry（返回大于等于指定键的最小键所关联的键值对）和higerEntry（返回大于指定键的最小键所关联的键值对）。一个NavigableMap支持对其中存储的键按键的递增顺序或递减顺序的遍历或访问。NavigableMap<K, V>接口还定义了firstEntry、pollFirstEntry、lastEntry和pollLastEntry等方法，以准确获取指定位置的键值对。

总的来说，NavigableMap<K, V>接口正如它的名字所示，支持我们在映射表中”自由的航行“，正向或者反向迭代其中的元素并获取我们需要的指定位置的元素。TreeMap实现了这个接口。

---

• 视图（View）与包装器
  Java中的集合视图是用来查看集合中全部或部分数据的一个”窗口“，只不过通过视图我们不仅能查看相应集合中的元素，对视图的操作还可能会影响到相应的集合。比如TreeMap和HashMap的keySet()方法就会返回一个相应映射表对象的视图。通过使用视图可以获得其他的实现了Map接口或Collection接口的对象。
  也就是说，keySet方法返回的视图是一个实现了Set接口的对象，这个对象中又包含了一系列键对象。
• 轻量级包装器
  Arrays.asList方法包装了Java数组的集合视图（实现了List接口）。请看以下代码：

public static void main(String[] args) {
  String[] strings = {"first", "second", "third"};
  List<String> stringList = Arrays.asList(strings);
  String s1 = stringList.get(0);
  System.out.println(s1);
  stringList.add(0, "new first");
}

注意：以上代码会编译成功，但是在运行时会抛出一个UnsupportedOperationException异常，原因是调用了改变列表大小的add方法。Arrays.asList方法返回的封装了底层数组的集合视图不支持对改变数组大小的方法（如add方法和remove方法）的调用（但是可以改变数组中的元素）。

• 子范围
  很多集合类型建立一个称为子范围（subrange）的集合视图。例如以下代码抽出group中的第10到19个元素（从0开始计数）组成一个子范围：

List subgroup = group.subList(10, 20); //group为一个实现了List接口的集合

List接口所定义的操作都可以应用于子范围，包括那些会改变列表大小的方法，比如以下方法会把subgroup列表清空，同时group中相应的元素也会从列表中移除：

subgroup.clear();

对于实现了SortedSet<E>接口的有序集或是实现了SortedMap<K, V>接口的有序映射表，我们也可以为他们创建子范围。SortedSet接口定义了以下三个方法：

SortedSet<E> subSet(E from, E to); 
SortedSet<E> headSet(E to);
SortedSet<E> tailSet(E from);

SortedMap也定义了类似的方法：

SortedMap<K, V> subMap(K from, K to);
SortedMap<K, V> headMap(K to);
SortedMap<K, V> tailMap(K from);

• 不可修改的视图
  Collections类中的一些方法可以返回不可修改视图（unmodifiable views)：

Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifiableSet
Collections.unmodifiableSortedSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap

• 同步视图
  若集合可能被多个线程并发访问，那么我们就需要确保集合中的数据不会被破坏。Java类库的设计者使用视图机制来确保常规集合的线程安全。比如，我们可以调用以下方法将任意一个实现了Map接口的集合变为线程安全的：
  Map<String, Integer> map = Collections.synchronizedMap(new HashMap<String, Integer>());
• 集合视图的本质

集合视图本身不包含任何数据，它只是对相应接口的包装。集合视图所支持的所有操作都是通过访问它所关联的集合类实例来实现的。我们来看看HashMap的keySet方法的源码：

public Set<K> keySet() {
  Set<K> ks;
  return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
} 

final class KeySet extends AbstractSet<K> {
  public final int size() { 
    return size; 
  }
  public final void clear() { 
    HashMap.this.clear(); 
  }
  public final Iterator<K> iterator() { 
    return new KeyIterator(); 
  }
  public final boolean contains(Object o) { 
    return containsKey(o); 
  }
  public final boolean remove(Object key) {
    return removeNode(hash(key), key, null, false, true) != null;
  }
  public final Spliterator<K> spliterator() {
    return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
  }
  public final void forEach(Consumer<? super K> action) {
    Node<K,V>[] tab;
    if (action == null) throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
      int mc = modCount;
      for (int i = 0; i < tab.length; ++i) {
        for (Node<K,V> e = tab[i]; e != null; e = e.next)
          action.accept(e.key);
        }
        if (modCount != mc) throw new ConcurrentModificationException();
      }
  }
}

可以看到，实际上keySet()方法返回一个内部final类KeySet的实例。我们可以看到KeySet类本身没有任何实例变量。我们再看KeySet类定义的size()实例方法，它的实现就是通过直接返回HashMap的实例变量size。还有clear方法，实际上调用的就是HashMap对象的clear方法。

keySet方法能够让你直接访问到Map的键集，而不需要复制数据或者创建一个新的数据结构，这样做往往比复制数据到一个新的数据结构更加高效。

• Collections类
  Collections类与Collection接口的区别：Collection是一个接口，而Collections是一个类（可以看做一个静态方法库）。下面我们看一下官方文档对Collections的描述：

Collections类包含了大量用于操作或返回集合的静态方法。它包含操作集合的多态算法，还有包装集合的包装器方法等等。这个类中的所有方法在集合或类对象为空时均会抛出一个NullPointerException。

• 说下面试经常问的HsahMap和HashTable的区别：

1. 正如上文所说，HashMap<K,V>是基于哈希表这个数据结构的具体实现，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap允许null key和null value，而hashtable不允许。
2. HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率
   上可能高于Hashtable。
   HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。
   HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。
3. Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。
4. 最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。
5. Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异。

总结

关于Java集合框架，我们首先应该把握住几个核心的接口，请看下图:

集合大家庭.jpg