Java

Java集合相关

摘要

集合相关要点汇总。

主干部分为：
Collection、Map、Iterator。

Collection

Collection包含了List和Set两大分支。

1.List

List是有序队列，List中的每一个元素都有一个索引，允许有重复的元素。

List的实现类有LinkedList, ArrayList, Vector, Stack等。

2.Set

Set不允许有重复元素。

Set的实现类有HastSet和TreeSet。HashSet依赖于HashMap，它实际上是通过HashMap实现的；TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。

Map

Map是一个映射接口，即key-value键值对。

AbstractMap是个抽象类，它实现了Map接口中的大部分API。而HashMap，TreeMap，WeakHashMap都是继承于AbstractMap。

Hashtable虽然继承于Dictionary，但它实现了Map接口。

Iterator

遍历集合的工具。

Collection依赖于Iterator，是因为Collection的实现类都要实现iterator()函数，返回一个Iterator对象。

ListIterator是专门为遍历List而存在的。

Enumeration作用和Iterator一样，也是遍历集合；但是Enumeration的功能要比Iterator少。在上面的框图中，Enumeration只能在Hashtable、Vector、Stack中使用。

List概况

List是一个继承于Collection的接口，即List是集合中的一种。List是有序的队列，List中的每一个元素都有一个索引；第一个元素的索引值是0，往后的元素的索引值依次+1。和Set不同，List中允许有重复的元素。

1.ArrayList

1.1 ArrayList是通过动态数组实现，大小可变的队列；允许包括 null 在内的所有元素，允许有重复的元素。此类大致上等同于Vector类，除了此类是不同步的。

1.2 每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。随着ArrayList中元素的增加，它的容量也会不断的自动增长。在每次添加新的元素时，ArrayList都会检查是否需要进行扩容操作，扩容操作带来数据向新数组的重新拷贝，所以如果我们知道具体业务数据量，在构造ArrayList时可以给ArrayList指定一个初始容量，这样就会减少扩容时数据的拷贝问题。

1.3 线程不安全，可使用List list = Collections.synchronizedList(new ArrayList(…)); 保证线程安全。

1.4 遍历ArrayList时，使用随机访问(即，通过索引序号访问 fori方式)效率最高，而使用迭代器的效率最低。

ArrayList的toArray()异常

当我们调用ArrayList中的 toArray()，可能遇到过抛出“java.lang.ClassCastException”异常的情况。

ArrayList提供了2个toArray()函数：

1
2
3
Object[] toArray()
<T> T[] toArray(T[] contents)

调用 toArray() 函数会抛出“java.lang.ClassCastException”异常，但是调用 toArray(T[] contents) 能正常返回 T[]。

toArray() 会抛出异常是因为 toArray() 返回的是 Object[] 数组，将 Object[] 转换为其它类型(如如，将Object[]转换为的Integer[])则会抛出“java.lang.ClassCastException”异常，因为有些情况下Java向下转型是不安全的。

解决该问题的办法是调用 T[] toArray(T[] contents) ， 而不是 Object[] toArray()。
调用 toArray(T[] contents) 返回T[]的可以通过以下几种方式实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// toArray(T[] contents)调用方式一
public static Integer[] vectorToArray1(ArrayList<Integer> v) {
    Integer[] newText = new Integer[v.size()];
    v.toArray(newText);
    return newText;
}
// toArray(T[] contents)调用方式二。最常用！
public static Integer[] vectorToArray2(ArrayList<Integer> v) {
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);
    return newText;
}
// toArray(T[] contents)调用方式三
public static Integer[] vectorToArray3(ArrayList<Integer> v) {
    Integer[] newText = new Integer[v.size()];
    Integer[] newStrings = (Integer[])v.toArray(newText);
    return newStrings;
}

2.ArrayList与CopyOnWriteArrayList比较

2.1 ArrayList线程不安全，CopyOnWriteArrayList线程安全。

2.2 和ArrayList继承于AbstractList不同，CopyOnWriteArrayList没有继承于AbstractList，它仅仅只是实现了List接口。

2.3 ArrayList的iterator()函数返回的Iterator是在AbstractList中实现的；而CopyOnWriteArrayList是自己实现Iterator。

2.4 ArrayList的Iterator实现类中调用next()时，会“调用checkForComodification()比较‘expectedModCount’和‘modCount’的大小”；但是，CopyOnWriteArrayList的Iterator实现类中，没有所谓的checkForComodification()，更不会抛出ConcurrentModificationException异常。

3.LinkedList

3.1 LinkedList是一个双向链表；LinkedList容量不限制；允许包括 null 在内的所有元素。

3.2 在插入和删除时，LinkedList更优于ArrayList；在查询时，ArrayList优于LinkedList。
LinkedList的顺序访问非常高效(使用迭代器或者foreach方式)，而随机访问效率比较低(fori方式)。

3.3 LinkedList可以作为FIFO(先进先出)的队列，也可以作为LIFO(后进先出)的栈。

4.Vector

4.1 Vector是通过动态数组实现，大小可变的队列；允许包括 null 在内的所有元素，允许有重复的元素，并且线程安全。

4.2 遍历Vector，使用随机访问(即，通过索引序号访问 fori方式)效率最高，而使用迭代器的效率最低。
Vector有一种额外的遍历方式：

1
2
3
4
5
Integer value = null;
Enumeration enu = vec.elements();
while (enu.hasMoreElements()) {
    value = (Integer)enu.nextElement();
}

5.Stack

5.1 Stack继承于Vector，也是通过数组实现；它的特性是：先进后出；线程安全。

6.List使用场景和性能分析

1.对于需要快速插入、删除元素，应该使用LinkedList。

因为ArrayList的add(int index, E element)函数，会引起index之后所有元素的改变。

而LinkedList双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找；否则，从后向前查找。

2.对于需要快速随机访问元素，应该使用ArrayList。

因为LinkedList需要在双向链表中找到要index位置的元素；找到之后再返回元素。

而ArrayList直接返回数组中index位置的元素，不需要查找。

3.对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。

Map概况

Map 是一个键值对(key-value)映射接口。Map映射中不能包含重复的键；每个键最多只能映射到一个值。

Map接口提供三种collection 视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。

  • entrySet()用于返回键-值集的Set集合；
  • keySet()用于返回键集的Set集合；
  • values()用户返回值集的Collection集合；

Map 映射顺序。有些实现类，可以明确保证其顺序，如 TreeMap；另一些映射实现则不保证顺序，如 HashMap。

SortedMap

SortedMap是继承于Map的接口。SortedMap中的内容是排序的键值对，排序的方法是通过比较器(Comparator)。

## NavigableMap

NavigableMap是继承于SortedMap的接口。相比于SortedMap，NavigableMap有一系列的导航方法；如”获取大于/等于某对象的键值对”、“获取小于/等于某对象的键值对”等等。

1.1 提供操作键-值对的方法。

1. lowerEntry、floorEntry、ceilingEntry 和 higherEntry 方法，它们分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象。

2. firstEntry、pollFirstEntry、lastEntry 和 pollLastEntry 方法，它们返回和/或移除最小和最大的映射关系（如果存在），否则返回 null。

1.2 提供操作键的方法。这个和1.1比较类似

1. lowerKey、floorKey、ceilingKey 和 higherKey 方法，它们分别返回与小于、小于等于、大于等于、大于给定键的键。

1.3 获取键集

1. navigableKeySet、descendingKeySet分别获取正序/反序的键集。

1.4 获取键-值对的子集

## 1.HashMap

HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

1.1 HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现，它是线程不安全的。如果需要满足线程安全，可以用Collections.synchronizedMap(new HashMap(…)); 使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

原理：

1. 通过Hash算法确定哈希桶数组索引位置；

2. 根据数组索引找到Entry(即，单向链表)，再遍历单向链表，将key和链表中的每一个节点的key进行对比。若key已经存在Entry链表中，则用该value值取代旧的value值；若key不存在Entry链表中，则新建一个key-value节点，并将该节点插入Entry链表的表头位置。

主要是addNewEntry()方法，获取指定 index 索引处的 Entry，将新创建的 Entry 放入 index 索引处，并让新的 Entry 指向原来的 Entry 。这样就将节点插入Entry链表的表头位置。


1
2
3
void addNewEntry(K key, V value, int hash, int index) {
        table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
    }


HashMap的put方法(JDK1.8)如图所示



1.2 它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。

1.3 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap中的映射不是有序的。

1.4 HashMap的遍历方式

  • entrySet()用于返回键-值集的Set集合；
1
2
3
4
5
6
7
8
9
10
11
// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    // 获取key
    key = (String)entry.getKey();
    // 获取value
    integ = (Integer)entry.getValue();
}
  • keySet()用于返回键集的Set集合；
1
2
3
4
5
6
7
8
9
10
11
// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
    // 获取key
    key = (String)iter.next();
    // 根据key，获取value
    integ = (Integer)map.get(key);
}
  • values()用于返回值集的Collection集合；
1
2
3
4
5
6
7
8
// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

2.Hashtable

2.1 Hashtable 虽然不是继承于AbstractMap，但它继承于Dictionary(Dictionary也是键值对的接口)，而且也实现Map接口；因此，Hashtable的内容也是“键值对，也不保证次序”。但和HashMap相比，Hashtable是线程安全的，而且它支持通过Enumeration去遍历。

2.2 HashMap是数组+链表实现的；是线程安全的。它的key、value都不可以为null。Hashtable中的映射不是有序的。

2.3 Hashtable的遍历方式

  • entrySet()用于返回键-值集的Set集合；
  • keySet()用于返回键集的Set集合；
  • values()用于返回值集的Collection集合；

以下两种方式遍历，不会抛出ConcurrentModificationException异常

  • keys()用于返回值集的枚举对象
1
2
3
4
Enumeration enu = table.keys();
while(enu.hasMoreElements()) {
    System.out.println(enu.nextElement());
}
  • elements()用于返回值集的枚举对象
1
2
3
4
Enumeration enu = table.elements();
while(enu.hasMoreElements()) {
    System.out.println(enu.nextElement());
}

3.TreeMap

3.1 TreeMap基于红黑树（Red-Black tree）实现。是一个有序的key-value集合。不是线程安全的。

TreeMap 继承于AbstractMap，且实现了NavigableMap接口；因此，TreeMap中的内容是“有序的键值对”。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

4.WeakHashMap

4.1 WeakHashMap 继承于AbstractMap。它的key、value都可以为null。它和HashMap的键类型不同，WeakHashMap的键是“弱键”。WeakHashMap是数组+链表实现的；WeakHashMap不是线程安全的。是一个无序的集合。

4.2 “弱键”的实现原理：WeakHashMap的key是“弱键”，即是WeakReference类型的；ReferenceQueue是一个队列，它会保存被GC回收的“弱键”。

实现步骤是：

1.新建WeakHashMap，将“键值对”添加到WeakHashMap中。

实际上，WeakHashMap是通过数组table保存Entry(键值对)；每一个Entry实际上是一个单向链表，即Entry是键值对链表。

2.当某“弱键”不再被其它对象引用，并被GC回收时。在GC回收该“弱键”时，这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中。

3.当下一次需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的键值对；同步它们，就是删除table中被GC回收的键值对。

答案是：

wmap:{three=w3, one=w1, two=w2}

contains key two : true

contains key five : false

contains value 0 : false

wmap: {one=w1, two=w2}

next : two - w2

after gc WeakHashMap size:1

5.LinkedHashMap

5.1 LinkedHashMap通过LinkedList(双向链表)+HashMap(数组+单向链表+红黑树(JDK1.8))实现；它的key、value都允许为空(key重复会覆盖、value允许重复)；允许有重复数据；它是有序的；它是线程不安全的。

5.2 LRUCache就是LinkedHashMap的一个应用。LRU即Least Recently Used，最近最少使用，也就是说，当缓存满了，会优先淘汰那些最近最不常访问的数据。

通过accessOrder字段，它表示：

  1. false，所有的Entry按照插入的顺序排列；

  2. true，所有的Entry按照访问的顺序排列。

访问包含两个意思：

  1. 根据Key拿到Value，也就是get方法；

  2. 修改Key对应的Value，也就是put方法。

每次调用LinkedHashMap#makeTail()方法会

  1. 把待移动的Entry的前后Entry相连；

  2. 把待移动的Entry移动到尾部。

答案是：

111=111 222=222 333=333 444=444

222=222 333=333 444=444 111=111

333=333 444=444 111=111 222=2222

6.HashMap和Hashtabe的不同点

  1. 继承和实现方式不同；
  2. 线程安全不同；Hashtable线程安全；HashMap线程不安全；
  3. 对null值的处理不同；HashMap的key、value都可以为null；Hashtable的key、value都不可以为null；
  4. 支持的遍历种类不同。HashMap只支持Iterator(迭代器)遍历；Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历。
  5. ……

Set概况

Set 是继承于Collection的接口。它是一个不允许有重复元素的集合。

  1. HashSet依赖于HashMap，它实际上是通过HashMap实现的。HashSet中的元素是无序的。
  2. TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。TreeSet中的元素是有序的。

1.HashSet

1.1 HashSet 是一个没有重复元素的集合。它是由HashMap实现的，不保证元素的顺序，而且HashSet允许使用 null 元素。它不是线程安全的。可以用Collections.synchronizedSet(new HashSet(…)); 使HashSet具有线程安全的能力。

2.TreeSet

2.1 TreeSet 是一个有序的集合。它不是线程安全的。允许使用 null 元素。

2.2 TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。

2.3 和NavigableSet一样，TreeSet的导航方法大致可以区分为两类，一类时提供元素项的导航方法，返回某个元素；另一类时提供集合的导航方法，返回某个集合。

lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素，如果不存在这样的元素，则返回 null。

Iterator和Enumeration区别

1.函数接口不同；

  1. Enumeration只有2个函数接口。通过Enumeration，我们只能读取集合的数据，而不能对数据进行修改。
  2. Iterator只有3个函数接口。Iterator除了能读取集合的数据之外，也能数据进行删除操作。

2.Iterator支持fail-fast机制，而Enumeration不支持；

参考

  1. Java 集合系列目录(Category)

  2. Java 8系列之重新认识HashMap

  3. 图解集合6：LinkedHashMap