rhb_blog

rao的博客

0%

java-容器

发表于 更新于 分类于 ，

一、集合介绍

Java的集合类

　　集合类主要负责保存、盛装和管理对象，因此集合类也被称为容器类。

　　集合类分为Set、List、Map和Queue四大体系。

  • Set 代表无序、不可重复集合；
  • List 代表有序、可重复集合；
  • Map 代表具有映射关系元素的集合；
  • Queue 代表队列，实现元素的先进先出管理。

　　数组也是一种集合类，它是能随机存储和访问引用序列的诸多方法中最高效的一种，当追求高效的数据访问时，数组是很不错的选择。

所有集合类都位于java.util包中，集合中只能保存对象的引用。集合类把它所含有的元素看成是Object的实例，这样方便但是也有隐患，即多个类型不同的元素被放入一个集合中，会增加集合访问时类型转换的困难，甚至会产生错误。

　　泛型的引入改善了这种情况，使用泛型来限制集合里元素的类型，并让集合记住元素的类型。这样可以允许编译器检查加入集合的元素类型，避免值类型不一致的错误。

二、集合概述

Java的集合类主要由两个接口派生而出——Collection和Map，它们是Java集合框架的根接口。


Collection接口存储一组不唯一（可以重复），无序的对象

img


　标准集合类实现了Collection接口，其中一些是抽象类，实现部分接口，其它是具体类，可以直接在代码中使用。

2.1 Set

  • TreeSet：（有序，唯一）： 红黑树(自平衡的排序二叉树)。HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。

  • HashSet：无序，唯一）: 基于 HashMap 实现的，底层采用HashMap 来保存元素。

  • LinkedHashSet：具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。

2.2 List

  • ArrayList：基于动态数组实现，支持随机访问。

  • Vector：和 ArrayList 类似，但它是线程安全的。

    • 1.Stack栈是继承了Vector类，所以底层还是数组。

      2.Stack栈是将底层的数组的最后一个元素当做栈顶。第一个元素当做栈底。

  • LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

2.3 Queue

  • LinkedList：可以用它来实现双向队列。
  • PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

2.4 Map

  • TreeMap：基于红黑树实现。
  • HashMap：DK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
  • key不可重复
  • HashTable： 数组+链表组成的，数组是HashTable的主体，链表则是主要为了解决哈希冲突而存在的。
    线程安全，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
  • LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》

2.5 如何选用集合

需要根据键值获取到元素值时就选用 Map 接口下的集合：

  • 需要排序时选择 TreeMap
  • 不需要排序时就选择 HashMap
  • 需要保证线程安全就选用 ConcurrentHashMap。

只需要存放元素值时，就选择实现Collection 接口的集合：

  • 需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet
  • 不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList

2.6 为什么需要使用集合？

数组存储的数据是有序的、可重复的，特点单一。 但是集合提高了数据存储的灵活性，Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据。

三、Collection的子接口——List

3.1 ArrayList和Vector的区别

  • ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；
  • Vector 是 List 的古老实现类，底层使用 Object[ ] 存储，线程安全的。

3.2 ArrayList和LinkedList的区别

  1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
  2. 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
  3. 插入和删除是否受元素位置的影响：
    1. ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。
    2. LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
  4. 是否支持快速随机访问：
    1. LinkedList 不支持高效的随机元素访问
    2. ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  5. 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

3.3 ArrayList的扩容机制（重点）

  1. 初始化的默认容量是10；
  2. 当添加元素的时候，add（）方法会调用ensureCapacityInternal（size+1）方法，用来进行容量检查，决定扩容的想要的最小容量。
  3. 当需要扩容的时候，会调用grow（）方法。
    int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！
  4. 真正的实现扩容其实是Arrays.copy方法，就是复制数组实现扩容

四、Collection的子接口Set

4.1 comparable 和 Comparator 的区别

  • comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
  • comparator接口实际上是出自 java.util包它有一个compare(Object obj1, Object obj2)方法用来排序

4.2 比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

HashSet 是 Set 接口的主要实现类 ，HashSet 的底层是 HashMap，线程不安全的，可以存储 null 值；

LinkedHashSet 是 HashSet 的子类，能够按照添加的顺序遍历；

TreeSet 底层使用红黑树，能够按照添加元素的顺序进行遍历，排序的方式有自然排序和定制排序。

五、Map接口

5.1 HashMap 和 Hashtable 的区别

  1. 线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
  2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
  3. 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
  4. 初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
  5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

5.2 HashMap 和 HashSet 区别

HashSet 底层就是基于 HashMap 实现的。

HashMap HashSet
实现了 Map 接口 实现 Set 接口
存储键值对 仅存储对象
调用 put()向 map 中添加元素 调用 add()方法向 Set 中添加元素
HashMap 使用键（Key）计算 hashcode HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以 equals()方法用来判断对象的相等性

5.3 HashMap 和 TreeMap 区别

相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

5.4 HashSet 如何检查重复

先看hashcode；再用equals（）

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

hashCode()与 equals() 的相关规定：

  1. 如果两个对象相等，则 hashcode 一定也是相同的
  2. 两个对象相等,对两个 equals() 方法返回 true
  3. 两个对象有相同的 hashcode 值，它们也不一定是相等的
  4. 综上，equals() 方法被覆盖过，则 hashCode() 方法也必须被覆盖
  5. hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

5.5 HashMap 多线程操作导致死循环问题

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

5.6 HashMap 有哪几种常见的遍历方式?

HashMap 的 7 种遍历方式与性能分析！

HashMap 遍历从大的方向来说，可分为以下 4 类：

  1. 迭代器（Iterator）方式遍历；
  2. For Each 方式遍历；
  3. Lambda 表达式遍历（JDK 1.8+）;
  4. Streams API 遍历（JDK 1.8+）。

5.7 ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

  • 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
  • 实现线程安全的方式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者的对比图：

HashTable:

HashTable全表锁

http://www.cnblogs.com/chengxiao/p/6842045.html>

JDK1.7 的 ConcurrentHashMap：

JDK1.7的ConcurrentHashMap

http://www.cnblogs.com/chengxiao/p/6842045.html>

JDK1.8 的 ConcurrentHashMap：

Java8 ConcurrentHashMap 存储结构（图片来自 javadoop）

JDK1.8 的 ConcurrentHashMap 不在是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 **TreeNode**。当冲突链表达到一定长度时，链表会转换成红黑树。

5.8 ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.7

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

1
2
static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

JDK1.8 （上面有示意图）

ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

六、Collections 工具类

Collections 工具类常用方法:

  1. 排序
  2. 查找,替换操作
  3. 同步控制(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

6.1 排序

1
2
3
4
5
6
void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

6.2 查找,替换操作

1
2
3
4
5
6
7
int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素。
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target).
boolean replaceAll(List list, Object oldVal, Object newVal), 用新元素替换旧元素

6.3 同步控制

Collections 提供了多个synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。

我们知道 HashSet，TreeSet，ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

方法如下：

1
2
3
4
synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。

七、容器中的设计模式

7.1 迭代器模式


Collection 继承了 Iterable 接口，其中的 iterator() 方法能够产生一个 Iterator 对象，通过这个对象就可以迭代遍历 Collection 中的元素。

从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。

1
2
3
4
5
6
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
    System.out.println(item);
}

7.2 适配器模式

java.util.Arrays#asList() 可以把数组类型转换为 List 类型。

1
2
@SafeVarargs
public static <T> List<T> asList(T... a)

应该注意的是 asList() 的参数为泛型的变长参数，不能使用基本类型数组作为参数，只能使用相应的包装类型数组。

1
2
Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr);

也可以使用以下方式调用 asList()：

1
List list = Arrays.asList(1, 2, 3);