常见集合类

作者: 彳亍口巴 | 来源:发表于2020-04-27 23:55 被阅读0次

一、常见集合类概述

集合继承关系图

在Java容器中一共定义了2种集合, 顶层接口分别是Collection和Map。但是这2个接口都不能直接被实现使用，分别代表两种不同类型的容器。
简单来看，Collection代表的是单个元素对象的序列，（可以有序/无序，可重复/不可重复等，具体依据具体的子接口Set，List，Queue等）；Map代表的是“键值对”对象的集合（同样可以有序/无序等依据具体实现）

（1）Collection 集合接口

Collection是最基本的集合接口，存储对象元素集合。一个Collection代表一组Object（元素）。有些容器允许重复元素有的不允许，有些有序有些无需。由Collection接口派生的两个接口是List和Set。这个接口的设计目的是希望能最大程度抽象出元素的操作。
定义

public interface Collection<E> extends Iterable<E> {
    ...
}

泛型即该Collection中元素对象的类型，继承的Iterable是定义的一个遍历操作接口，采用hasNext next的方式进行遍历。具体实现还是放在具体类中去实现。
主要方法

boolean add(Object o) 添加对象到集合
boolean remove(Object o) 删除指定的对象
int size() 返回当前集合中元素的数量
boolean contains(Object o) 查找集合中是否有指定的对象
boolean isEmpty() 判断集合是否为空
Iterator iterator() 返回一个迭代器
boolean containsAll(Collection c) 查找集合中是否有集合c中的元素
boolean addAll(Collection c) 将集合c中所有的元素添加给该集合
void clear() 删除集合中所有元素
void removeAll(Collection c) 从集合中删除c集合中也有的元素
void retainAll(Collection c) 从集合中删除集合c中不包含的元素

1、List子接口

List是一个允许重复元素的指定索引、有序集合。
从List接口的方法来看，List接口增加了面向位置的操作，允许在指定位置上操作元素。用户可以使用这个接口精准掌控元素插入，还能够使用索引index（元素在List中的位置，类似于数组下标）来访问List中的元素。List接口有两个重要的实现类：ArrayList和LinkedList。
Set里面和List最大的区别是Set里面的元素对象不可重复。

（1）ArrayList 数组

定义
1、ArrayList实现了List接口的可变大小的数组。（数组可动态创建，如果元素个数超过数组容量，那么就创建一个更大的新数组）
2、它允许所有元素，包括null
3、它的size, isEmpty, get, set, iterator,add这些方法的时间复杂度是O(1),如果add n个数据则时间复杂度是O(n)
4、ArrayList没有同步方法
常用方法

Boolean add(Object o)将指定元素添加到列表的末尾
Boolean add(int index,Object element)在列表中指定位置加入指定元素
Boolean addAll(Collection c)将指定集合添加到列表末尾
Boolean addAll(int index,Collection c)在列表中指定位置加入指定集合
Boolean clear()删除列表中所有元素
Boolean clone()返回该列表实例的一个拷贝
Boolean contains(Object o)判断列表中是否包含元素
Boolean ensureCapacity(int m)增加列表的容量,如果必须,该列表能够容纳m个元素
Object get(int index)返回列表中指定位置的元素
Int indexOf(Object elem)在列表中查找指定元素的下标
Int size()返回当前列表的元素个数

（2）LinkedList 链表

定义
1、LinkedList是一个实现了List接口的链表维护的序列容器
2、允许null元素。
3、LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
4、LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。

（2.1）ArrayList与LinkedList

链表LinkedList和数组ArrayList的最大区别在于它们对元素的存储方式的不同导致它们在对数据进行不同操作时的效率不同。实际使用时根据特定的需求选用合适的类。

查找方面。数组的效率更高，可以直接索引出查找，而链表必须从头查找。
插入删除方面。特别是在中间进行插入删除，这时候链表体现出了极大的便利性，只需要在插入或者删除的地方断掉链然后插入或者移除元素，然后再将前后链重新组装，但是数组必须重新复制一份将所有数据后移或者前移。
在内存申请方面，当数组达到初始的申请长度后，需要重新申请一个更大的数组然后把数据迁移过去才行。而链表只需要动态创建即可。
如果主要是查找元素则使用ArrayList。
如果主要是插入/删除元素则使用LinkedList。

（3）Vector 向量

Vector非常类似ArrayList。
Vector是同步的。当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。

（3.1）Stack 栈

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。

2、Set子接口

Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。

（1）HashSet 散列集

HashSet实现了Set接口，基于HashMap进行存储。遍历时不保证顺序，并且不保证下次遍历的顺序和之前一样。HashSet中允许null元素。

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

意思就是HashSet的集合其实就是HashMap的key的集合，然后HashMap的val默认都是PRESENT。HashMap的定义即是key不重复的集合。使用HashMap实现，这样HashSet就不需要再实现一遍。
所以所有的add，remove等操作其实都是HashMap的add、remove操作。遍历操作其实就是HashMap的keySet的遍历

（1.1）LinkedHashSet 链式散列集

LinkedHashSet的核心概念相对于HashSet来说就是一个可以保持顺序的Set集合。HashSet是无序的，LinkedHashSet会根据add，remove这些操作的顺序在遍历时返回固定的集合顺序。这个顺序不是元素的大小顺序，而是可以保证2次遍历的顺序是一样的。
类似HashSet基于HashMap的源码实现，LinkedHashSet的数据结构是基于LinkedHashMap。

（2）TreeSet 树形集

TreeSet即是一组有次序的集合，如果没有指定排序规则Comparator，则会按照自然排序。（自然排序即e1.compareTo(e2) == 0作为比较）
TreeSet源码的算法即基于TreeMap，扩展自AbstractSet，并实现了NavigableSet，AbstractSet扩展自AbstractCollection，树形集是一个有序的Set，其底层是一颗树，这样就能从Set里面提取一个有序序列了。在实例化TreeSet时，我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序。树形集中提供了很多便捷的方法。

注：TreeSet内的元素必须实现Comparable接口。

例

public class TestSet {

    public static void main(String[] args) {

        TreeSet<Integer> set = new TreeSet<>();

        set.add(1111);
        set.add(2222);
        set.add(3333);
        set.add(4444);
        set.add(5555);

        System.out.println(set.first()); // 输出第一个元素
        System.out.println(set.lower(3333)); //小于3333的最大元素
        System.out.println(set.higher(2222)); //大于2222的最大元素
        System.out.println(set.floor(3333)); //不大于3333的最大元素
        System.out.println(set.ceiling(3333)); //不小于3333的最大元素

        System.out.println(set.pollFirst()); //删除第一个元素
        System.out.println(set.pollLast()); //删除最后一个元素
        System.out.println(set);
    }
}

3、Queue 队列

队列是一种先进先出的数据结构，元素在队列末尾添加，在队列头部删除。Queue接口扩展自Collection，并提供插入、提取、检验等操作。

offer：向队列添加一个元素
poll：移除队列头部元素（队列为空返回null）
remove：移除队列头部元素（队列为空抛出异常）
element：获取头部元素
peek：获取头部元素

（1）Deque 双端队列

接口Deque，是一个扩展自Queue的双端队列，它支持在两端插入和删除元素，因为LinkedList类实现了Deque接口，所以通常我们可以使用LinkedList来创建一个队列。PriorityQueue类实现了一个优先队列，优先队列中元素被赋予优先级，拥有高优先级的先被删除。
Queue<String> queue = new LinkedList<>();
1
补：Iterator迭代器
如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：

Iterator it = collection.iterator(); // 获得一个迭代子  
while(it.hasNext()) {  
Object obj = it.next(); // 得到下一个元素  
}

（2）Map 图接口

Map是图接口，存储键值对映射的容器类。Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。
接口定义

public interface Map<K,V> {
    ...
    
    interface Entry<K,V> {
        K getKey();
        V getValue();
        ...
    } 
}

泛型<K,V>分别代表key和value的类型。这时候注意到还定义了一个内部接口Entry，其实每一个键值对都是一个Entry的实例关系对象，所以Map实际其实就是Entry的一个Collection，然后Entry里面包含key，value。再设定key不重复的规则，自然就演化成了Map。
遍历方法
Map集合提供3种遍历访问方法

1. Set keySet() 获得所有key的集合然后通过key访问value
会返回所有key的Set集合，因为key不可以重复，所以返回的是Set格式，而不是List格式。（之后会说明Set，List区别。这里先告诉一点Set集合内元素是不可以重复的，而List内是可以重复的）获取到所有key的Set集合后，由于Set是Collection类型的，所以可以通过Iterator去遍历所有的key，然后再通过get方法获取value。如下

Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");

Set<String> keySet = map.keySet();//先获取map集合的所有键的Set集合
Iterator<String> it = keySet.iterator();//有了Set集合，就可以获取其迭代器。

while(it.hasNext()) {
       String key = it.next();
       String value = map.get(key);//有了键可以通过map集合的get方法获取其对应的值。
       System.out.println("key: "+key+"-->value: "+value);//获得key和value值
}

2. Collection values() 获得value的集合
直接获取values的集合，无法再获取到key。所以如果只需要value的场景可以用这个方法。获取到后使用Iterator去遍历所有的value。如下

Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");

Collection<String> collection = map.values();//返回值是个值的Collection集合
System.out.println(collection);

3. Set< Map.Entry< K, V>> entrySet() 获得key-value键值对的集合
getValue获取key和value。如下

Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");

//通过entrySet()方法将map集合中的映射关系取出（这个关系就是Map.Entry类型）
Set<Map.Entry<String, String>> entrySet = map.entrySet();
//将关系集合entrySet进行迭代，存放到迭代器中                
Iterator<Map.Entry<String, String>> it = entrySet.iterator();

while(it.hasNext()) {
       Map.Entry<String, String> me = it.next();//获取Map.Entry关系对象me
       String key = me.getKey();//通过关系对象获取key
       String value = me.getValue();//通过关系对象获取value
}

通过以上3种遍历方式我们可以知道，如果你只想获取key，建议使用keySet。如果只想获取value，建议使用values。如果key value希望遍历，建议使用entrySet。
Map的访问顺序取决于Map的遍历访问方法的遍历顺序。有的Map，比如TreeMap可以保证访问顺序，但是有的比如HashMap，无法保证访问顺序。
主要方法

boolean equals(Object o)比较对象
boolean remove(Object o)删除一个对象
put(Object key,Object value)添加key和value

引用（本文章只供本人学习以及学习的记录，如有侵权，请联系我删除）

第六章 Java数据结构和算法之容器类（一）