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既可以是有容量限制也可以是无固定容量限制。

双端队列的三种用法：

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

#

BlockingDeque

#

非阻塞队列

#

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

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

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