2、集合

继承树

Collection接口

Map接口

Collection 接口

• Collection接口（继承于java.lang.Iterable）：单列集合，用来存储一个一个的对象

  • List接口：extends Collection，存储有序的、可重复的数据。“动态”数组

    • ArrayList、LinkedList、Vector

  • Set接口：extends Collection，存储无序的、不可重复的数据。高中讲的“集合”

    • HashSet、LinkedHashSet、TreeSet

Collection 接口方法

• 增加：add(Object obj)，addAll(Collection coll)
• 获取有效元素个数：int size()
• 清空集合：void clear()
• 是否为空集合：boolean isEmpty()
• 是否包含指定元素：boolean contains(Object obj)，boolean containsAll(Collection c)
• 删除：boolean remove(Object obj)，boolean removeAll(Collection c)
• 取两个集合的交集（只保留集合c中有的元素）：boolean retainAll(Collection c)
• 集合是否相等：boolean equals(Object obj)
• 转数组：Object[] toArray()
• 获取迭代器：iterator()

遍历Collection的两种方式

• 使用迭代器Iterator

• foreach循环（或增强for循环）：内部仍然调用的是迭代器

迭代器Iterator接口

Iterable：接口，规定实现类或子接口必须要有提供迭代器的能力

Iterator：迭代器的类型，迭代器使用Iterable接口中iterator方法返回的，通过Iterator<T> iterator();方法获取

java.util包下定义的迭代器接口：Iterator

• Iterator对象称为迭代器(设计模式的一种)，主要用于遍历Collection集合中的元素。

• GOF给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。

不支持删除行为：Iterator迭代时，删除当前遍历到的元素可以使用迭代器对象.remove()，但是，切记！！！迭代器在迭代的时候不支持集合本身的修改行为add|remove，否则，会引发java.util.ConcurrentModificationException并发修改异常。

遍历代码实现

Iterator iterator = coll.iterator();
//hasNext():判断是否还下一个元素
while(iterator.hasNext()){
    //next():指针下移并将下移以后指向的元素返回
    System.out.println(iterator.next());
    //remove():删除指针当前指向的元素
    iterator.remove();
}

符合迭代器的设计模式

• 抽象集合接口（Iterable（抽象接口））
• 集合的具体实现类实现Iterable，必须拥有给外界提供迭代器（Iterator）的能力
• 抽象迭代器接口（Iterator）
• 具体的迭代器实现类（实现Iterator，体现为不同集合中的内部类）

List接口

存储的数据特点：存储有序的、可重复的数据。

List接口常用方法

• 增：add(Object obj)
• 删：remove(int index) / remove(Object obj)
• 改：set(int index, Object ele)
• 查：get(int index)
• 插：add(int index, Object ele)
• 长度：size()
• 遍历：
  • Iterator迭代器方式
  • 增强for循环
  • 普通的循环

实现类1：ArrayList

底层：底层是一个Object类型的数组，初始的默认长度0（jdk1.6之前是10），在第一次add时，容量变为10，也可以指定长度，初始长度如果满了，底层进行自动扩容，扩容为原来的1.5倍oldCapacity + (oldCapacity >> 1)。如果对集合中的元素个数可以预估，那么建议预先指定一个合适的初始容量new ArrayList(20);

优点：查找效率高，向末尾添加元素也可以

缺点：增加 、删除牵扯到数组的扩容和移动，效率低；线程不安全

实现类2：LinkedList

底层：是一个链表（双向）结构，不是线性存储。

优点：增加、删除效率高

缺点：查找效率低；线程不安全

实现类3：Vector

底层：是一个Object类型的数组，初始的默认长度为10，扩容的时候扩容为原来的2倍，如果自己指定扩容的长度，那么就是旧容量加指定的，如果没有指定，就是旧容量的2倍。

优点：线程安全，通过synchronized同步锁实现

缺点：效率低

// 初始容量1，每次扩容增加2
Vector v = new Vector(1,2);

存储的元素的要求

添加的对象，所在的类要重写equals()方法

三个实现类的异同

Set接口

存储的数据特点：无序的、不可重复的元素（如果hashCode返回值一样和equals为true，则认为是重复元素）

具体说明

以HashSet为例说明：

1. 无序性：不等于随机性。存储的数据在底层数组中并非照数组索引的顺序添加，而是根据数据的哈希值决定的。

2. 不可重复性：保证添加的元素照equals()判断时，不能返回true，hashCode不可以一样，即：相同的元素只能添加一个。

Set接口中没额外定义新的方法，使用的都是Collection中声明过的方法。

实现类1：HashSet

底层：HashSet的底层是一个HashMap，只是将HashMap中的值设置为一个常量，用所有的键组成了一个HashSet

优点**：可以存储null值**

缺点：线程不安全

实现类2：LinkedHashSet

LinkedHashSet 是 HashSet 的子类

底层：是一个LinkedHashMap，底层维护了一个数组 + 双向链表

• 遍历其内部数据时，可以按照添加的顺序遍历（存储了插入顺序）
• 在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。（双向链表）
• 对于频繁的遍历操作，LinkedHashSet效率高于HashSet，但是由于维护链表，所以插入效率不如HashSet
• 可以存放null值

存储对象所在类的要求：

向Set(主要指：HashSet、LinkedHashSet)中添加的数据，其所在的类一定要重写hashCode()和equals()

实现类3：TreeSet

TreeSet 是 SortedSet（继承于Set）接口的实现类，TreeSet 可以确保集合元素处于排序状态。

不可以放null对象

存储对象所在类的要求：

1. 向TreeSet中添加的数据，要求是相同类的对象而且对象必须是可比较的。

2. 两种排序方式：自然排序（实现Comparable接口） 和 定制排序（Comparator，创建TreeSet的时候可以作为构造方法参数传入！）

TreeSet<Integer> s2 = new TreeSet<Integer>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        // 升序排序
        if (o1 > o2){
            return 1;
        }else {
            return -1;
        }
    }
});

Map接口

• Map：存储双列数据，存储key-value对的数据，类似于高中的函数：y = f(x)
  • HashMap
    • LinkedHashMap
  • TreeMap
  • Hashtable
    • Properties:常用来处理配置文件。key和value都是String类型

Map接口常用方法

• 新增：Object put(Object key,Object value)，void putAll(Map m)
• 删除：Object remove(Object key)
• 清空：void clear()
• 获取value：Object get(Object key)
• 是否包含key：boolean containsKey(Object key)
• 是否包含value：boolean containsValue(Object value)
• 键值对个数：int size()
• 是否为空map：boolean isEmpty()
• 获取所有key：Set keySet()
• 获取所有value：Collection values()
• 获取所有键值对：Set entrySet()

存储结构的理解

• Map中的key : 无序的、不可重复的，使用Set存储所有的key，key所在的类要重写equals()和hashCode()（以HashMap为例)
• Map中的value : 无序的、可重复的，使用Collection存储所的value，value所在的类要重写equals()，一个键值对：key-value构成了一个Entry对象。
• Map中的entry : 无序的、不可重复的，使用Set存储所的entry

实现类1：HashMap

底层：所有的键构成了一个HashSet，整体是数组+链表/红黑树

优点：效率高，可以存储null值、null键

缺点：线程不安全

• 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true， hashCode 值也相等。
• 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true。

初始长度16，每次扩容为原来的2倍，扩容因子（即当前元素个数 / 当前容量 > 扩容因子时就会进行扩容）0.75

HashMap的put过程

1. 根据键的hash码（调用键的hashCode方法）进行哈希运算，得到一个整数哈希值
2. 判断哈希表是否为空或者长度是否为0，如果是，要对数组进行初始化，如果否，进入3
3. 根据1得到的哈希值计算数组索引（与运算），得到一个和数组存储位置匹配的索引i
4. 判断i号位置是否为null，如果null，就将键和值封装为一个Entry类型的对象进行插入,如果不为null，进入5
5. 判断key是否存在（使用equals进行判断），如果存在，覆盖原有的值，如果不存在，进入6
6. 判断i号位置是否为一个树结构，如果是一个树结构，在树中进行插入，如果不是树结构，进入7
7. 为链表结构，对链表进行遍历，判断key是否存在，存在就覆盖，不存在就在链表中插入新的节点
8. 链表中插入新节点后，如果i号位置的元素个数大于等于8，i号位置的所有元素转换为树结构，如果不大于等于8，新节点正常插入结束
9. size++
10. 判断是否要进行扩容，如果需要扩容，就执行Resize()进行扩容
11. 结束

实现类2：LinkedHashMap

底层**：HashMap的子类**；在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。

优点：保证在遍历map元素时，可以照添加的顺序实现遍历。对于频繁的遍历操作，此类执行效率高HashMap。可以存储null值、null键

缺点：线程不安全

实现类3：TreeMap

底层**：红黑树**

优点：保证照添加的key-value对进行排序，实现按照键排序遍历，两种排序方式：自然排序（实现Comparable接口） 和 定制排序（Comparator）

缺点**：键不可以为null，值可以为null**

实现类4：Hashtable

底层**：数组+链表/红黑树**

优点：线程安全（使用synchronized实现）

缺点：效率低；不能存储null的key和value

不可以放入null值、null键

初始长度11，每次扩容为原来的2倍加1，扩容因子（即当前元素个数 / 当前容量 > 扩容因子时就会进行扩容）0.75

实现类5：Properties

底层**：Hashtable的子类，数组+链表/红黑树**

优点：一般用来存储配置文件

缺点：key和value都是String类型

面试题

• 为什么HashMap的长度为什么要设计成2的n次方？

  • 为了方便将去余运算转换为位运算

• 为什么设计扩容因子

  • 为了减少一个桶里元素碰撞的概率，本质就是不要让一个桶中的元素个数太多

• 根据key怎么找到值的get(key)？

  • 根据key的哈希码先找到桶的位置，然后再在一个桶中用equals方法进行比对，找到对应的元素，获取其值。

• 为什么使用hash码相关的集合的时候，重写equals方法的时候建议也重写hashCode方法

  • 如果equals返回true.但是哈希码不一样，有可能会放到不同的桶中，不同的桶中就存在了键重复的元素了，有漏洞，最终目的是为了让equals返回true的两个对象能放到一个桶中，保证键不重复

• HashMap和Hashtable的区别：

  1. 继承的类不一样，HashMap继承自AbstractMap，Hashtable继承自Dictionary类
  2. 根据hash码计算存储位置的过程和算法是不同的（hashMap最后进行位运算，hashtable最后进行取余的运算）。
  3. Hashtable不能放入null键、null值，但是hastMap可以放入null键、null值
  4. Hashtable初始的默认长度是11，HashMap是16.
  5. Hashtable线程安全，效率低，HashMap线程不安全，效率高
  6. 扩容方式不同，HashMap扩容为原来的2倍，Hashtable扩容为原来的二倍加1（int newCapacity = (oldCapacity << 1) + 1）
  7. Hashtable支持Enumeration遍历 ，HashMap不支持

• HashMap在jdk8中相较于jdk7在底层实现方面的不同：

  1. jdk7：底层初始创建一个长度为16的数组，jdk8：初始化没有指定HashMap数组大小，而是在添加第一个元素时，进行扩容操作

  2. jdk8底层的数组是：Node[]，而非Entry[]（jdk7）

  3. 首次调用put()方法时，底层创建长度为16的数组

  4. jdk7底层结构只：数组+链表。jdk8中底层结构：数组+链表+红黑树。

  5. 形成链表时，七上八下（jdk7：新的元素指向旧的元素。jdk8：旧的元素指向新的元素）

  6. 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所有数据改为使用红黑树存储。

Collections工具类

作用：操作Collection和Map的工具类

Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作， 还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

Collections常用方法

集合的线程安全

List的线程安全

如果使用ArrayList多个线程同时添加和读取，可能会出现并发修改异常ConcurrentModificationException

Vector

使用synchronized关键字，对修改、添加、删除等方法进行修饰，实际开发中，我们很少使用，强同步性能低

Collections

可以使用Collections中的静态方法synchronizedXXX将XXX类型的集合转为线程安全版本

CopyOnWriteArrayList（推荐）

List list = new CopyOnWriteArrayList();

使用写时复制技术，也就是读的时候可以并发进行读，但是写，只允许一个线程写，复制一份和当前集合相同的集合，然后在写完以后，进行合并

使用Lock可重入锁进行实现

Set的线程安全

Collections

和List的使用方法一样

CopyOnWriteArraySet

和List的使用方法一样

Map的线程安全

HashTable

使用synchronizd强同步，效率低，不推荐

Collections

和List的使用方法一样

ConcurrentHashMap

Map map = new ConcurrentHashMap()

队列Queue

任何无限容量的队列ho栈都是有容量的，这个容量就是Integer.MAX_VALUE

Queue常用方法

• 入队
  • void add(Object e)：将指定元素加入此队列的尾部，当超过容量，抛出异常
  • boolean offer(Object e)：将指定元素加入该队列的尾部，当超过容量，返回false
• 出队
  • Object poll()：获取队列头部的元素，并删除该元素，队列为空则返回null
  • Object remove()：获取队列头部的元素，并删除该元素，队列为空时抛出异常NoSuchElementException
• 查看队首元素
  • Object element()：获取列队头部的元素，但是不删除该元素，队列为空抛出异常
  • Object peek()：获取队列头部的元素，但是不删除该元素，队列为空，则返回null

双端队列

deque是double ended queue的缩写。双端队列顾名思义就是队列的两个端口都能进出。

Deque的实现类中，LinkedList是最常用的。值得注意的是，LinkedList也实现了List接口。

大多数Deque既可以是有容量限制也可以是无固定容量限制。

	头部	头部	尾部	尾部
失败响应	抛出异常	返回值	抛出异常	返回值
入队	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
出队	removeFirst()	pollFirst()	removeLast()	pollLast()
查看	getFirst()	peekFirst()	getLast()	peekLast()

双端队列的三种用法：

1、作为队列，先进先出

Queue<String> queue = new LinkedList();
// 队尾入队
queue.offer("El");
// 队首出队
String el = queue.poll();

Deque<String> deque = new LinkedList();
// 队尾入队
deque.offerLast("El");
// 队首出队
String el = deque.pollFirst();

2、作为堆栈，先进后出

注意：Java的堆栈类Stack已经过时，官方推荐Deque代替

Deque<String> deque = new LinkedList();
// 队尾入队
deque.offerLast("el");
// 队尾出队
String el = deque.pollLast();

3、作为双端队列，两端都可进出

Deque<String> deque = new LinkedList();
// 队尾入队
deque.offerLast("el");
// 队首入队
deque.offerFirst("el");
// 队尾出队
String el1 = deque.pollLast();
// 队首出队
String el2 = deque.pollFirst();

阻塞队列

阻塞队列是一个支持两个附加操作的队列，即在队列为满时，存储元素的线程会等待队列可用；当队列为空时，获取元素的线程会等待队列为非空。

• ArrayBlockingQueue ：一个由数组结构组成的有界阻塞队列。
• LinkedBlockingQueue ：一个由链表结构组成的有界阻塞队列。
• PriorityBlockingQueue ：一个支持优先级排序的无界阻塞队列。
• DelayQueue：一个使用优先级队列实现的无界阻塞队列。
• SynchronousQueue：一个不存储元素的阻塞队列。
• LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
• LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

阻塞队列所实现接口有BlockingQueue和BlockingDeque，增加方法如下：

BlockingQueue

方法描述	一直阻塞	超时退出
入队	put(e)	offer(e,time,unit)
出队	take()	poll(time,unit)

BlockingDeque

	头部	头部	尾部	尾部
方法描述	一直阻塞	超时退出	一直阻塞	超时退出
入队	putFirst(e)	offerFirst(e,time,unit)	putLast(e)	offerLast(e,time,unit)
出队	takeFirst()	pollFirst(time,unit)	takeLast()	pollLast(time,unit)

非阻塞队列

非阻塞队列不能阻塞，个人理解为普通队列，在多线程中，当队列满或空时，只能使用wait()和notify()进行队列消息传送。

AbstractQueue是非阻塞队列所实现的接口，常见的非阻塞实现类有：

• LinkedList
  • 既实现了AbstractQueue接口也实现了Deque接口，也可作为双端队列使用。
• PriorityQueue
  • 维护了一个有序队列，默认队头是规则排序中最小的元素（从小到大）。
  • 排序的规则是通过构造函数comparator来实现，因此，该队列不允许插入null值或不可比较的对象。
• ConcurrentLinkedQueue
  • 该类是基于链接点的线程安全队列，并发访问不需要同步。
  • 此队列不允许使用null元素。