四、Java集合

1. Java集合概述

Java集合主要由两个接口派生而出，Collection和Map
|---Collection(I)
|---|---Set(I)
|---|---|---EnumSet(C)
|---|---|---SortedSet(I)
|---|---|---|---TreeSet(C)
|---|---|---HashSet(C)
|---|---|---|---LinkedHashSet(C)
|---|---Queue(I)
|---|---|---PriorityQueue(C)
|---|---|---Deque(I) |
|-------------------|---LinkedList(C)
|---|---List(I)------|
|---|---|---ArrayList(C)
|---|---|---Vector(C)
|---|---|---|---Stack(C)

|---Map
|---|---EnumMap
|---|---IdentityHashMap
|---|---HashMap(C)
|---|---|---LinkedHashMap
|---|---HashTable(C)
|---|---|---Properites
|---|---SortedMap(I)
|---|---|---TreeMap(C)
|---|---WeakHashMap

Collection提供了如下接口：

• add,addAll,contains,containsAll,remove,removeAll,retainAll
• clear,isEmpty，size，toArray,iterator

遍历可以通过iterator迭代器来进行，也可以通过foreach来进行。
Iterator接口里面定义了以下三个方法：

• boolean hasNext()
• Object next()
• void remove()

2 Set接口

Set不允许两个equals方法返回True的对象同时插入

• 非同步，线程不安全
  可以用Collections.synchronizedSet来进行包装

2.1 HashSet类

• 具有更好的存储和查找性能
• 不保证元素的顺序
• 集合元素可以是null

HashSet判断相等的标准是：通过equals和hashCode方法，两个都相等

LinkedHashSet使用链表维护元素的次序，所以性能会略差一些。

2.2 TreeSet类

TreeSet是SortedSet接口的唯一实现。
与HashSet相比，还提供了以下额外的方法：

• comparator, first,last,lower,higher,headSet,tailSet,subSet

TreeSet采用红黑树来对数据结构进行排序

对于添加到TreeSet中的对象，有下面两个要求：
1.实现Comparable接口
2.必须是相同类

equals返回false或者compareTo不相等，都表示两个对象不相同

3 List接口

List接口代表一个有序集合，集合中的每个元素都有其对应的顺序索引。List允许重复元素，可以通过索引来访问指定位置的集合元素。

3.1 List接口和ListInterator接口

List除了可以使用Collection接口的全部方法之外，还有一些可以根据索引来操作集合元素的方法：

• void add(int index, Object element)
• boolean addAll(int index, Collection c)
• Object get(int index)
• int indexOf(Object o)
• int lastIndexOf(Object o)
• Object remove(int index)
• Object set(int index,Object element)
• List subList(int fromIndex,int toIndex)

List判断相等的标准，也是通过equals方法返回true即可

List还提供了一个listIterator()方法，该方法返回一个ListIterator对象,除了Iterator有的方法之外，还包含：

• boolean hasPrevious()
• Object previous()
• void add()

3.2 ArrayList和Vector实现类

二者都是基于数组实现的List类，封装了一个动态再分配的Object[]数组，每个对象有一个capacity属性，这个属性平时不用关注，但是如果要一次大量的插入元素，可以通过ensureCapacity(int)来一次性的增加capacity，从而减少重分配次数。
capacity属性默认为10，可以通过如下两个方法来操作：

• void ensureCapacity(int minCapacity)
• void trimToSize() //调整集合的capacity为当前列表大小

Vector是一个古老的集合，里面很多重复的方法，而且名字很长，所以一般不推荐使用。

Vector有一个Stack子类，有peek,pop和push方法，模拟栈这种数据结构。

有一点需要注意的是，Vector是线程安全的，但ArrayList是不安全的，但是也依旧可以通过Collections工具类来让其变得线程安全

4 Queue接口

Queue用于模拟队列这种数据结构，队列是一种FIFO容器。Queue实现了如下几个方法：

• void add(Object e) //添加到队列尾部
• boolean offer(Object e) //有些队列有大小限制，如果超出限制，该方法会返回false,而add则会抛出异常
• Object remove() //获取队列头部元素，并且删除
• Object poll()//当队列为空的时候，会返回null,而remove会抛出异常
• Object element()//获取队列头部元素，但是不删除
• Object peek()//当队列为空的时候，会返回null,而element会抛异常

4.1 LinkedList

LinkedList同时实现了List和Deque（双向队列）。
Deque接口里面定义了一些可以双向操作队列的方法：

• addFirst,addLast,offerFirst,offerLast,removeFirst,removeLast,pollFirst,pollLast,getFirst,getLast,peekFirst,peekLast
• Iterator descendingIterator()//返回以双向队列对应的迭代器
• Object removeFirstOccurrence(Object o)
• Object removeLastOccurrence(Object o)

从上面的方法可以看出，LinkedList不仅可以当双向队列使用，还可当栈使用。

4.2 PriorityQueue

保存队列的顺序并不是加入队列的顺序，而是排序之后的。
关于排序和TreeSet基本一致

5 Map接口

Map用于保存具有映射关系的数据。Map接口中定义了如下常用方法：

• void clear()
• boolean containsKey(Object key)
• boolean containsValue(Object value)
• Set entrySet()
• Object get(Object key)
• boolean isEmpty()
• Set keySet()
• Object push(Object key, Object value)
• void putAll(map m)
• Object remove(Object key)
• int size()
• Collection values()
  Map中包括一个内部类：Entry,包含getKey,getValue,setValue三个方法

5.1 HashMap和HashTable实现类

HashTable是一个古老的实现类，但是是线程安全的。

和HashSet类似的是，如果使用可变对象作为HashMap和HashTable的Key,且程序修改了key的话，那么，程序将再也无法准确访问到Map中被修改过Key

HashMap也有一个子类，叫LinkedHashMap,使用双向链表来维护key-value的次序。
Properites是HashTable的子类，该对象在处理属性文件的时候特别方便。包含如下接口：
String getProperty(String key)
String getProperty(String key, String defaultValue)
Object setProperty(String key,String value)
void load(InputStream inStream)//加载属性文件
void store(OutputStream,String comment)//写入属性文件

5.2 SortedMap接口和TreeMap实现类

和TreeSet一样，TreeMap也是使用红黑树对TreeMap的所有key进行排序，从而使所有的key-value属于有序状态。
也是提供了两种排序方式：

• 自然排序：key必须实现Comparable接口
• 定制排序：传入Comparator对象
  类似判断两个元素相等的标准，TreeSet中判断两个key相等的标准也是两个key通过equals返回true,通过compareTo返回0

实现的方法参考TreeSet的方法，有：firstEntry,firstKey,lastEntry,lastKey,higher,lower,subMap,headMap,tailMap

5.3 WeakHashMap, IdentityHashMap, EnumMap

WeakHashMap的key使用的是弱引用，在垃圾回收的时候
IdentityHashSet必须是使用==相同，才算是相同
EnumMap的key必须是单个枚举类的枚举值

6 操作集合的工具类：Collections

6.1排序操作

• static void reverse(List list)
• static void shuffle(List list)
• static void sort(List list)
• static void sort(List list, Comparator c)
• static void swaq(List list,int i,int j)
• static void rotate(List list,int distance)

6.2查找，替换操作

• static void binarySearch(List list,Object key)
• static Object max(Collection c,Comparator comp)
• static Object max(Collection c)
• static Object min(Collection c,Comparator comp)
• static Object min(Collection c)
• static void fill(List list, Object obj)
• static int frequency(Collection c, Object o)
• static int indexOfSubList(List source, List target)
• static int LastIndexOfSubList(List source, List target)
• static boolean replaceAll(List list, Object oldVal, Object newVal)

6.3 同步控制

synchronizedCollection/List/Set/Map

6.4 设置不可变集合

emptyxxx()
singletonxxx()
unmodifiablexxx()