Java容器

发表于 2021-07-25 更新于 2023-08-30 分类于 Java全栈， JavaSE 阅读次数：

概览

容器除了数组，主要包括Collection和Map这两种接口，两者也常被统称为集合框架：

Collection存储对象的集合（单列）
Map存储键值对的映射表（双列）

数组和集合框架的区别：

数组长度固定；集合的长度可变
数组可以存储基本数据类型；集合只能存储对象，而且对象的类型可以不一致（泛型）

在开发中，一般当对象多的时候，使用集合框架进行存储。

Collection 接口

java.util.Collection是单列集合类的根接口。

常用方法：

boolean add(E e)：添加指定对象到当前集合
void clear()：清空集合中所有的元素
boolean remove(E e)：从当前集合中删除指定对象
boolean contains(E e)：判断当前集合中是否包含给定的对象
boolean isEmpty()：判断当前集合是否为空
int size()：返回集合中元素个数
Object[] toArray()：把集合中的元素存储到数组中

继承了Collection的接口：

List 接口
Set 接口
Queue 接口

Iterator 接口

java.util.Iterator接口也是Java集合中的一员，主要用于迭代访问（即遍历）Collection中的元素。

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

迭代：即Collection集合元素的通用获取方式。需要先判断集合中有没有元素，如果有，就取出来，直至全部取出。

常用方法：

public E next()：返回迭代的下一个元素
public boolean hasNext()：如果仍有元素可以迭代，则返回true

Collection<String> col = new ArrayList<>();
//往集合中添加元素
col.add("甲");
col.add("乙");
col.add("丙");
col.add("丁");

Iterator<String> it = col.iterator(); //迭代器的泛型由创建它的Collection的泛型决定
while(it.hasNext()) {
    System.out.println(it.next());
}

从JDK 1.5 之后，可以使用增强for循环——foreach方法来遍历实现了Iterable接口的聚合对象：

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

List 接口

java.util.List存储的元素有序且可重复。习惯性地会将实现了List接口的对象称为List集合，可以通过索引来访问集合中的指定元素。

常用方法

除了继承自Collection接口中的全部方法，还增加了一些根据元素索引来操作集合的方法：

void add(int index, E element)：将指定元素添加到指定位置，原index及之后位置的元素都向后移动
E get(int index)：返回指定位置的元素
E remove(int index)：移除指定位置的元素，返回被移除的元素
E set(int index, E element)：用指定元素替换集合中指定位置的元素，返回被替换的元素

list集合的三种遍历方式：

普通for循环
使用迭代器
增强for循环

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");

// 1. 普通for循环
for(int i = 0; i < list.size(); i++) {
    String str = list.get(i);
    System.out.println(str);
}

// 2. 使用迭代器
Iterator<String> it = list.iterator();
while(it.hasNext()) {
    String str = it.next();
    System.out.println(str);
}

// 3.增强for循环
for (String str : list) {
    System.out.println(str);
}

ArrayList

java.util.ArrayList集合的存储结构是动态数组。由于日常开发中使用最多的功能为查询和遍历数据，而不是增删操作，因此ArrayList是最常用的集合。

LinkedList

java.util.LinkedList集合的存储结构是双向链表，可以快速完成插入和删除元素的操作。LinkedList能用作栈、队列和双向队列。

LinkedList包含了大量操作首尾元素的方法，使用这些方法时，不能使用多态：

void addFirst(E e)

void push(E e)等效于该方法
void addLast(E e)

void add(E e)等效于该方法，可读性不如
E getFirst()
E getLast()
E removeFirst()

E pop()等效于该方法
E removeLast()

Vector

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

Set 接口

java.util.Set同样继承自Collection接口，它与Collection接口中的方法基本一致，没有进行功能上的扩充，只是更严格。Set接口中，元素无序且不可重复。

Set不允许重复元素的原理

Set集合在调用add方法的时候，add方法会调用元素的hashCode方法和equals方法，判断元素是否重复。存储的元素必须重写hashCode方法和equals方法，建立自己的比较方式。

HashSet

java.util.HashSet是Set接口的一个实现类，元素无序且不可重复，基于哈希表（实际上是一个HashMap实例）实现。

HashSet根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。

jdk 1.8之前，哈希表 = 数组 + 链表；jdk 1.8开始，哈希表 = 数组 + 链表/红黑树。数组的初始容量为16。

先计算元素的hash值，hash值即作为在数组中对应的下标；
存在不同的元素拥有相同的hash值（hash冲突），数组中存储的元素为链表/红黑树，链表/红黑树中存放最终的元素（相同hash值的元素超过了8个，就会改链表为红黑树存储元素）。

LinkedHashSet

java.util.LinkedHashSet继承了HashSet类，基于哈希表 + 双向链表（维护元素的插入顺序），保证元素有序。

TreeSet

基于红黑树实现，元素有序。

查找效率不如HashSet，HashSet查找的时间复杂度为O(1)，TreeSet则为O(logN)。

Queue 接口

Queue实现了一个FIFO的队列，常用方法如下：

	throw Exception	返回false或null
添加元素到队尾	add(E e)	boolean offer(E e)
取队首元素并删除	E remove()	E poll()
取队首元素但不删除	E element()	E peek()

PriorityQueue

PriorityQueue基于堆结构实现，可以用它来实现优先队列。
PriorityQueue在获取队首元素时，总是返回优先级最高的元素。
默认按元素比较的顺序（小顶堆）排序（必须实现Comparable接口）
可以通过Comparator自定义排序算法（不必实现Comparable接口）

Deque

Deque实现了一个双端队列（Double Ended Queue），实现类有：

ArrayDeque
LinkedList

总是使用xxxFirst/xxxLast，以便和Queue的方法区分开。

1 2	// 多态，让LinkedList这种具有多种功能的类的角色更明确 Deque<String> deque = new LinkedList<>();

Collections 类

java.utils.Colletcions是集合工具类，用来对集合进行操作。部分方法如下：

static <T> boolean addAll(Collection<T> c, T... elements)：往集合中添加多个元素
static void shuffle(List<?> list)：打乱集合顺序
static <T> void sort(List<T> list)：将集合中元素按照默认规则(升序)排序
static <T> void sort(List<T> list, Comparator<? super T>)：将集合中元素按照指定规则排序

ArrayList<String> list = new ArrayList<>();
Collections.addAll(list, "a", "b", "c", "d", "e");

Collections.shuffle(list);

sort(List<T> list) 方法的使用

参与排序的集合中存储的元素，必须实现comparable接口，重写接口中的compareTo方法，定义默认排序的规则。

Comparable接口的排序规则：

compareTo方法返回0，认为相等
compareTo方法返回正数，当前对象后置
compareTo方法返回负数，当前对象前置

public class Person implements Comparable<Persion> {
    private String name;
    private int age;
    
    public int getAge() {
        return age;
    }
    
    public void setAge(int age) {
        this.age = age;
    }
    
    // 重写排序的规则
    @override
    public int compareTo(Person p) {
        // 返回0表示：认为元素是相同的
        
        //自定义比较规则，比较两个人的年龄
        return this.getAge() - p.getAge(); // 按年龄升序排序
    }
    
}

sort(List<T> list, Comparator<? super T>) 方法的使用

Comparator和Comparable的区别：

Comparable是自己(this)和别人(参数)比较，需要实现Comparable接口，重写compareTo方法
Comparator相当于找一个裁判，重写compare方法，不需要实现Comparable接口

Collections.sort(list1, new Comparator<Student>() { //匿名类
    //重写比较规则
    @Override
    public int compare(Student s1, Student s2) {
        int result = s1.getAge() - s2.getAge(); // 返回正数，s1后置；返回负数，s1前置
        if (result == 0) {
		result = o1.getName().charAt(0) - o2.getName().charAt(0);
        }
        return result;
    }
})

Map 接口

Map<K, V>是将键映射到值的对象。元素无序且不能包含重复的键（可以有一对一和多对一的关系）。

常用方法：

V put(K key, V value)：如果插入的键值key未重复，返回值的V为null；否则返回被替换的value
V get(Object key)
V remove(Object key)
boolean containsKey(Object key)

遍历相关方法：

Set<K> keySet()：获取Map集合中所有的键，存储到Set集合中

第一种遍历方式：通过键找值的方式

使用Map集合的keySet()方法，把Map集合所有的key取出来，存储到一个Set集合中
遍历Set集合，获取每个key
通过Map集合的get(key)方法，通过key找到value

Map<String, Integer> map = new HashMap<>();
map.put("苏炳添", '32');
map.put("刘翔", '38');

for(String key : map.keySet()) {
    Integer value = map.get(key);
    System.out.println(key + "=" + value);
}

Set<Map.Entry<K, V>> entrySet()

Map.Entry<K, V>是Map接口中的一个内部接口，当Map集合创建，就会在Map集合中创建一个Entry对象，用来记录键与值（键值对对象、键与值的映射关系）。

  - `K getKey()`
  - `V getValue()`

entrySet()方法将Map集合内部的多个Entry对象取出来，存储到一个Set集合中。

第二种遍历方式：通过Entry对象遍历

使用Map集合中的方法entrySet()，把Map集合中多个Entry对象取出来，存储到一个Set集合中
遍历Set集合，获取每一个Entry对象
使用Entry对象中的getKey()和getValue()获取键与值

Map<String, Integer> map = new HashMap<>();
map.put("苏炳添", '32');
map.put("刘翔", '38');

Set<Entry<String, Integer>> set = map.entrySet();

for(Map.Entry<String, Integer> entry : set) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + "-->" + value);
}

HashMap

java.util.HashMap<K, V>是Map接口的一个实现类，元素无序且不能包含重复的键，基于哈希表实现。

jdk 1.8之前，哈希表 = 数组 + 链表；jdk 1.8开始，哈希表 = 数组 + 链表/红黑树。数组的初始容量为16。

先计算元素的hash值，hash值即作为在数组中对应的下标；

存在不同的元素拥有相同的hash值（hash冲突），数组中存储的元素为链表/红黑树，链表/红黑树中存放最终的元素（相同hash值的元素超过了8个，就会改链表为红黑树存储元素）。

HashMap 不允许重复键的原理

HashMap在调用put方法的时候，put方法会调用key的hashCode方法和equals方法，判断元素是否重复。存储的元素必须重写hashCode方法和equals方法，建立自己的比较方式。

LinkedHashMap

java.util.LinkedHashMap继承了HashMap类，基于哈希表 + 双向链表（维护元素的插入顺序），保证元素有序。

HashTable

与其他集合框架不同，HashTableK/V都不允许存储null对象，底层是一个哈希表。另外它是线程安全的。

它是遗留类，不应该去使用它，而是使用ConcurrentHashMap来支持线程安全，ConcurrentHashMap的效率会更高，因为ConcurrentHashMap引入了分段锁。

HashTable的子类Properties(唯一和IO流相结合的集合)依然活跃着。

TreeMap

基于红黑树实现

容器中的设计模式

适配器模式

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

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

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

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

// 也可以采用如下方式调用asList()
List list = Arrays.asList(1, 2, 3);

泛型

泛型即参数化类型。一提到参数，最熟悉的就是定义方法时有形参，然后调用此方法时传递实参。那么参数化类型怎么理解呢？顾名思义，就是将类型由原来的具体的类型参数化，类似于方法中的变量参数，此时类型也定义成参数形式（可以称之为类型形参），然后在使用/调用时传入具体的类型（类型实参）。

泛型的本质是为了参数化类型（在不创建新的类型的情况下，通过泛型指定的不同类型来控制形参具体限制的类型）。也就是说在泛型使用过程中，操作的数据类型被指定为一个参数，这种参数类型可以用在类、接口和方法中，分别被称为泛型类、泛型接口、泛型方法。

举例

List arrayList = new ArrayList();
arrayList.add("aaaa");
arrayList.add(100);

for(int i = 0; i< arrayList.size();i++){
    String item = (String)arrayList.get(i);
    Log.d("泛型测试","item = " + item);
}

ArrayList可以存放任意类型，例子中添加了一个String类型，添加了一个Integer类型，再使用时都以String的方式使用，因此程序崩溃了。为了在编译阶段解决类似这样的问题，泛型应运而生。

1	List<String> arrayList = new ArrayList<String>();

特性

泛型只在编译阶段有效。看下面的代码：

List<String> stringArrayList = new ArrayList<String>();
List<Integer> integerArrayList = new ArrayList<Integer>();

Class classStringArrayList = stringArrayList.getClass();
Class classIntegerArrayList = integerArrayList.getClass();

if(classStringArrayList.equals(classIntegerArrayList)){
    Log.d("泛型测试","类型相同");
}

输出结果：D/泛型测试: 类型相同。

通过上面的例子可以证明，在编译之后程序会采取去泛型化的措施。也就是说Java中的泛型，只在编译阶段有效。在编译过程中，正确检验泛型结果后，会将泛型的相关信息擦除，并且在对象进入和离开方法的边界处添加类型检查和类型转换的方法。也就是说，泛型信息不会进入到运行时阶段。

泛型类型在逻辑上看以看成是多个不同的类型，实际上都是相同的基本类型。

泛型的使用

泛型类

泛型类型用于类的定义中，被称为泛型类。通过泛型可以完成对一组类的操作对外开放相同的接口。最典型的就是各种容器类，如：List、Set、Map。

泛型类的最基本写法：

class 类名称 <泛型标识：可以随便写任意标识号，标识指定的泛型的类型>{
  private 泛型标识 /*（成员变量类型）*/ var; 
  .....

  }
}

// 例子
//此处T可以随便写为任意标识，常见的如T、E、K、V等形式的参数常用于表示泛型
//在实例化泛型类时，必须指定T的具体类型
public class Generic<T> {
    //key这个成员变量的类型为T，T的类型由外部指定  
    private T key;

    public Generic(T key) { //泛型构造方法形参key的类型也为T，T的类型由外部指定
        this.key = key;
    }

    public T getKey() { //泛型方法getKey的返回值类型为T，T的类型由外部指定
        return key;
    }
}

//泛型的类型参数只能是类类型（包括自定义类），不能是简单类型
//传入的实参类型需与泛型的类型参数类型相同，即为Integer.
Generic<Integer> genericInteger = new Generic<Integer>(123456);

//传入的实参类型需与泛型的类型参数类型相同，即为String.
Generic<String> genericString = new Generic<String>("key_vlaue");
Log.d("泛型测试", "key is " + genericInteger.getKey());
Log.d("泛型测试", "key is " + genericString.getKey());

定义的泛型类，就一定要传入泛型类型实参么？并不是这样，在使用泛型的时候如果传入泛型实参，则会根据传入的泛型实参做相应的限制，此时泛型才会起到本应起到的限制作用。如果不传入泛型类型实参的话，在泛型类中使用泛型的方法或成员变量定义的类型可以为任何的类型。

Generic generic = new Generic("111111");
Generic generic1 = new Generic(4444);
Generic generic2 = new Generic(55.55);
Generic generic3 = new Generic(false);

泛型接口

泛型接口与泛型类的定义及使用基本相同。泛型接口常被用在各种类的生产器中，可以看一个例子：

//定义一个泛型接口
public interface Generator<T> {
    public T next();
}

未传入泛型实参时，与泛型类的定义相同，在声明类的时候，需将泛型的声明也一起加到类中。

// 如果不声明泛型，如：class FruitGenerator implements Generator<T>，编译器会报错："Unknown class"
class FruitGenerator<T> implements Generator<T>{
    @Override
    public T next() {
        return null;
    }
}

当实现泛型接口的类，传入泛型实参时

/**
 * 定义一个生产器实现这个接口，虽然我们只创建了一个泛型接口Generator<T>
 * 但是我们可以为T传入无数个实参，形成无数种类型的Generator接口。
 * 在实现类实现泛型接口时，如已将泛型类型传入实参类型，则所有使用泛型的地方都要替换成传入的实参类型
 * 即：Generator<T>，public T next();中的T都要替换成传入的String类型。
 */
public class FruitGenerator implements Generator<String> {

    private String[] fruits = new String[]{"Apple", "Banana", "Pear"};

    @Override
    public String next() {
        Random rand = new Random();
        return fruits[rand.nextInt(3)];
    }
}

泛型通配符

当使用泛型类或者接口时，传递的数据中，泛型类型不确定时，无法通过Object类型表示任意类型，因为泛型没有继承的概念，可以通过通配符<?>表示。但是一旦使用泛型的通配符后，只能使用Object类中的共性方法，集合中元素自身方法无法使用。

通配符基本使用

泛型的通配符：不知道使用什么类型来接收的时候可以使用?，表示未知通配符。

泛型通配符不能在创建对象时使用，只能作为方法的参数使用。

例：定义一个能遍历所有类型的ArrayList集合

public static void printArray(ArrayList<?> list) {
    // 使用迭代器遍历集合
    Iterator<?> it = list.iterator();
    while(it.hasNext()) {
        Object o = it.next(); //next方法返回Object类型的元素
        System.out.println(o);
    }
}

泛型通配符高级使用——受限泛型

JAVA的泛型可以指定上限和下限。

泛型的上限

类型名称 <? extends 类> 对象名称：只能接收该类型及其子类
泛型的下限

类型名称 <? super 类> 对象名称：只能接收该类型及其父类

红黑树

特点

根节点是黑节点
叶子节点（红黑树只有null节点称为叶子节点)是黑节点(红黑树是一棵满二叉树)

可知，红黑树中至少有一半以上的节点是黑节点
红节点的子结点必须是黑节点（红节点出现的条件很严苛，红节点出现最频繁的情况下，树中的节点也是红黑交错的）
新插入的节点是红节点（为了达到平衡，后续也可能会变成黑节点）
从任意一个节点出发，到任意叶子节点的路径上，黑节点的数量都一样（红黑树的平衡条件）

平衡二叉树（AVL树）的平衡条件是左右子树的深度差<=1；而红黑树没有这么严格，根据上述特点，可以得知其平衡条件为左右子树深度差在一倍以内（特点3 + 5），因此红黑树写的性能更高些。

如果将红黑树中的红节点忽略，黑节点构成的树就是一棵平衡二叉树。红黑树最差情况下（红黑相间，深度翻一倍）的时间复杂度为$O(2\log n_{black}) = O(2\log {n\over2})=O(2(\log n- 1))=O(\log n)$

相关面试题：JAVA 1.8 HashMap的实现，每一个桶？是一个链表，当链表的长度>=8，就会变成红黑树。为什么要选择红黑树这种结构，而不是二叉搜索树或者平衡二叉树？

当元素有序时，二叉搜索树会退化为链表，没有实现性能的优化；AVL树相对于红黑树，其平衡条件更严格，红黑树的插入效率要更高一些，在实际的应用中，红黑树更符合性能的需要。