集合的分类

集合可以分类为以下两大种：

  • 单列集合
  • 双列集合

Java 中的集合框架的继承和实现体系大致如下：

  • Collection
    • List
      • ArrayList
      • LinkedList
      • Vector
    • Set
      • HashSet
        • LinkedHashSet
      • TreeSet
  • Map
    • HashMap
      • LinkedHashMap
    • Hashtable
      • Properties
    • TreeMap
红色标签 为接口（Interface），蓝色标签 为实现类（Implementation）

以上结构仅展示一些经常会用到的实现类和接口，并不是完整的结构，下图才是完整的结构：


引用自Wikipedia 的 Java collections framework

Collection（单列集合）

Collection 是单列集合的顶层接口，以下为常用方法：

方法名称 说明
boolean add(E e) 把给定的对象添加到当前集合当中
void clear() 清空集合中所有元素
boolean remove(E e) 把给定的元素在当前集合中删除
boolean contains(Object o) 判断当前集合中是否包含给定对象
boolean isEmpty() 判断当前集合是否为空
int size() 返回集合中的元素个数

List

List 集合中的元素有序，可重复，且有索引，因此多了很多索引操作的方法：

方法名称 说明
void add(int index, E element) 在集合中的指定位置插入给定元素
E remove(int index) 删除指定索引处的元素，返回被删除的元素
E set(int index, E element) 修改指定索引处的元素，返回被修改的元素
E get(int index) 返回指定索引处的元素

ArrayList

ArrayList 的底层是一个数组，在扩容时有特殊机制

ArrayList 底层原理

  1. 利用空参构造创建集合时，在底层会创建一个默认长度为 0 的数组
  2. 当往集合中添加元素时，底层会创建一个新的长度为 10 的数组
  3. 当存满时继续添加元素，会触发集合的扩容，此时有两种情况：
    1. 添加单个元素或添加的多个元素个数和原来的元素个数之和小于原来长度的 1.5 倍，集合会扩容至原来的 1.5 倍
    2. 添加的元素过多，会直接扩容至原来的元素个数加添加的元素个数

LinkedList

LinkedList 的底层是靠链表实现的

LinkedList 特有方法

方法名称 说明
void addFirst(E e) 在列表的开头插入给定元素
void addLast(E e) 在列表的结尾插入给定元素
E getFirst() 返回列表开头的元素
E getLast() 返回列表结尾的元素
E removeFirst 删除列表开头的元素
E removeLast 删除列表结尾的元素

Set

Set 集合中的元素无序，不重复，且没有索引，和 Collection 的 API 基本一致

HashSet

HashSet 的底层是一个 HashMap，所以使用的数据结构 HashMap 是一样
当向 HashSet 添加元素时，实际上是在往 HashMap 添加一个 key = 此元素，value = 虚拟 Object 对象的键值对
这个虚拟Object对象没有实际含义，可以看作value为空，只是因为HashMap的底层实现要求value不可为null

在使用 HashSet 存储自定义对象时，必须重写 hashCode()和 equals()方法

LinkedHashSet

LinkedHashSet 与 HashSet 相比较多了可以保证数据的存储和取出的顺序时一样的

LinkedHashSet 底层是一个 LinkedHashMap，所以底层原理是一样的
当向 LinkedHashSet 添加元素时，实际上是在往 LinkedHashMap 添加一个 key = 此元素，value = 虚拟 Object 对象的键值对

TreeSet

TreeSet 是可以排序的，默认按照从小到大的顺序排序

TreeSet 底层是一个 TreeMap，所以底层原理是一样的，都是基于红黑树来实现的
当向 TreeSet 添加元素时，实际上是在往 TreeSet 添加一个 key = 此元素，value = 虚拟 Object 对象的键值对

TreeSet 中的元素若为自定义对象，需要实现 Comparable 接口或者在构造时传入 Comparator 的实现类对象

Map（双列集合）

Map 也叫映射，是一种可以将键和值对应起来的结构，

Map 是双列集合的顶层接口，以下是一些常用的方法：

方法名称 说明
V put(K key, V value) 添加或覆盖元素，若是添加则返回 null，若是覆盖则返回被覆盖的 value
V remove(Object key) 根据键删除键值对元素
V get(Object key) 根据键获取值
V repalce(K key, V value) 根据键将值替换成新的值，并将旧的值进行返回
boolean repalce(K key, V oldValue, V newValue) 根据键值对将值替换成新的值，存在此键值对则替换且返回 true，否则返回 false
void clear() 移除所有的键值对元素
boolean containsKey(Object key) 判断集合是否包含指定的键
boolean containsValue(Object value) 判断集合是否包含指定的值
boolean isEmpty() 判断集合是否为空
int size() 返回集合的长度，即键值对个数
Set keySet() 返回键的 Set 集合
Set<Map.Entry<K, V>>entrySet() 返回键值对对象的 Set 集合

HashMap

HashMap 中存储的元素是无序，不重复，且无索引的

HashMap 映射的底层在 JDK8 前后是不一样的
在 JDK8 以前：数组+链表（哈希表）
在 JDK8 及其以后：数组+链表+红黑树

HashMap 底层原理：

  1. 创建一个默认长度 16，默认加载因子为 0.75（Load Factor）的数组，数组名 table
    加载因子是用来控制哈希表扩容时机的，当表中存储的元素大于16*0.75时，哈希表扩充到原来的两倍
  2. 根据键值对的键（key）的哈希值跟数组的长度计算出应存入的位置
    index = (table.length - 1) & 键的哈希值，此哈希值是调用键的hashCode()获取的
  3. 判断当前位置是否为 null，如果是 null 直接存入
  4. 如果位置不为 null，表示已有元素，则调用 equals 方法比较键的属性值
  5. 一样：不存；不一样：存入数组，形成链表
    JDK8 以前：新元素存入数组，老元素挂在新元素下面
    JDK8 以后：新元素直接挂在老元素下面
  6. 当链表的长度大于 8 且数组的长度大于等于 64 时，链表会转换成红黑树

若在使用 HashMap 存储的键是自定义对象时，必须重写 hashCode()和 equals()方法
若在使用 HashMap 存储的值是自定义对象时，不需要重写 hashCode()和 equals()方法

LinkedHashMap

LinkedHashMap 中存储的元素是有序，不重复且无索引的

LinkedHashMap 与 HashMap 相比，多了可以保证数据的存储和取出的顺序时一样的

HashMap 的底层在原有 HashMap 的基础上增加了双链表机制，每个添加的元素都记录了上一个添加的元素的地址值和下一个要添加的元素的地址值
在遍历时会从第一个添加的元素开始遍历

Hashtable

Properties

TreeMap

TreeMap 中存储的元素是可排序，不重复，且无索引的
可排序是指能对键进行排序操作
TreeMap 是可以排序的，默认按照从小到大的顺序排序，底层是基于红黑树来实现的

TreeMap 中的元素的键若为自定义对象，需要实现 Comparable 接口或者在构造时传入 Comparator 的实现类对象
TreeMap 中的元素的值若为自定义对象，不需要实现 Comparable 接口或者在构造时传入 Comparator 的实现类对象

集合的遍历

collection 集合的遍历有以下三种方式：

  • 迭代器遍历
  • 增强 for 遍历
  • lambda 表达式遍历

list 集合的遍历有以下五种方式：

  • 迭代器遍历
  • 列表迭代器遍历
  • 增强 for 遍历
  • lambda 表达式遍历
  • 普通 for 循环遍历（依赖索引）

set 集合的遍历方式和 collection 集合的遍历方式一样：

  • 迭代器遍历
  • 增强 for 遍历
  • lambda 表达式遍历

map 映射的遍历方式有以下三种方式：

  • 根据键遍历
  • 根据键值对遍历
  • lambda 表达式遍历

迭代器遍历

使用集合中的iterator()方法获取迭代器，以下是迭代器对象常用方法：

方法名称 说明
boolean hasNext() 判断当前位置是否有元素，有返回 true，无则返回 false
E next() 获取当前位置的元素，并将迭代器对象移向下一个元素
void remove() 删除上一次调用 next()返回的对象

使用 Iterator 正向遍历 ArrayList：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main{
    public static void main(String[] args) {
        String s1 = "🐂🍺";
        String s2 = "牛啤";
        Collection<String> coll1 = new ArrayList<>();
        coll1.add(s1);
        coll1.add(s2);
        coll1.add("aaa");
        coll1.add("bbb");
        Iterator<String> iterator1 = coll1.iterator();
        while (iterator1.hasNext()) {
            String s = iterator1.next();
            if (s.equals("bbb")) iterator1.remove();
            System.out.println(s);
        }
        System.out.println(coll1.size());
        System.out.println(coll1);
    }
}

🐂🍺
牛啤
aaa
bbb
3
[🐂🍺, 牛啤, aaa]

使用 Iterator 正向遍历 LinkedList：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main{
    public static void main(String[] args) {
        String s1 = "🐂🍺";
        String s2 = "牛啤";
        Collection<String> coll2 = new LinkedList<>();
        coll2.add(s1);
        coll2.add(s2);
        coll2.add("aaa");
        coll2.add("bbb");
        Iterator<String> iterator2 = coll2.iterator();
        while (iterator2.hasNext()) {
            String s = iterator2.next();
            if (s.equals("aaa")) iterator2.remove();
            System.out.println(s);
        }
        System.out.println(coll2.size());
        System.out.println(coll2);
    }
}

🐂🍺
牛啤
aaa
bbb
3
[🐂🍺, 牛啤, bbb]

在使用迭代器遍历时，禁止使用集合的 remove 方法，会导致ConcurrentModificationException报错

列表迭代器遍历

List 集合中特有的迭代器，用方法listIterator()来获取指向 0 索引的迭代器，使用listIterator(int index)可以得到指向指定索引的迭代器，ListIterator是Iterator的子接口，所以包含父类中的方法，以下是常用方法：

方法名称 说明
void add(E e) 在指向处插入元素
boolean hasNext() 判断当前位置是否有元素，有返回 true，无则返回 false
E next() 获取当前位置的元素，并将迭代器对象移向下一个元素
int nextIndex() 返回当前位置的索引
boolean hasPrevious() 判断上一个位置是否有元素，有返回 true，无则返回 false
E previous() 获取上一个位置的元素，并将迭代器对象移向上一个元素
int previousIndex 返回上一个位置的索引
void remove() 删除上一次调用 previous()或 next()返回的元素
void set(E e) 修改上一次调用 previous()或 next()返回的元素

使用 ListIterator 反向遍历 ArrayList：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main{
    public static void main(String[] args) {
        String s1 = "🐂🍺";
        String s2 = "牛啤";
        List<String> list1 = new ArrayList<>();
        list1.add(s1);
        list1.add(s2);
        list1.add("aaa");
        list1.add("bbb");
        ListIterator<String> listIterator1 = list1.listIterator(list1.size());
        while (listIterator1.hasPrevious()) {
            String s = listIterator1.previous();
            if (s.equals("bbb")) listIterator1.remove();
            System.out.println(s);
        }
        System.out.println(list1.size());
        System.out.println(list1);
    }
}

bbb
aaa
牛啤
🐂🍺
3
[🐂🍺, 牛啤, aaa]

使用 ListIterator 反向遍历 LinkedList：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main{
    public static void main(String[] args) {
        String s1 = "🐂🍺";
        String s2 = "牛啤";
        List<String> list2 = new LinkedList<>();
        list2.add(s1);
        list2.add(s2);
        list2.add("aaa");
        list2.add("bbb");
        ListIterator<String> listIterator2 = list2.listIterator(list2.size());
        while (listIterator2.hasPrevious()) {
            String s = listIterator2.previous();
            if (s.equals("aaa")) listIterator2.remove();
            System.out.println(s);
        }
        System.out.println(list2.size());
        System.out.println(list2);
    }
}

bbb
aaa
牛啤
🐂🍺
3
[🐂🍺, 牛啤, bbb]

增强 for 遍历

增强 for 遍历的底层其实就是迭代器遍历，与迭代器遍历相比在使用时可以简化书写

1
2
3
for (String s : coll) {
    System.out.println(s);
}

lambda 表达式遍历

使用 forEach 方法来遍历集合
void forEach(Consumer<? super E> action)

1
2
3
4
5
6
coll.forEach(new Consumer<String>() {
    @Override
    public void accept(String s) {
        System.out.println(s);
    }
});

accept 方法中填写遍历中要做的事

由于 Consumer 接口是一个函数式接口，所以可以将匿名内部类改写为 lambda 表达式

1
coll.forEach((System.out::println));

根据键遍历

调用 Map 对象的 keySet()，得到键的 Set 集合，接着根据键的值在 Map 中获取对应的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
    public static void main(String[] args) {
        Map<String, String> hm = new HashMap<>();
        System.out.println(hm.put("a", "b"));  //null
        System.out.println(hm.put("b", "bcd"));//null
        System.out.println(hm.put("c", "adb"));//null
        System.out.println(hm.put("abc", "a"));//null

        Set<String> keys = hm.keySet();

        for (String key : keys) {
            String value = hm.get(key);
            System.out.println(key + " = " + value);
        }
        //a = b
        //b = bcd
        //c = adb
        //abc = a
    }
}

根据键值对遍历

调用 Map 对象的 entrySet()，得到键值对对象的 Set 集合，接着调用 entry 对象的 getKey()和 getValue()方法获取对应的键和值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main {
    public static void main(String[] args) {
        Map<String, String> hm = new HashMap<>();
        System.out.println(hm.put("a", "b"));  //null
        System.out.println(hm.put("b", "bcd"));//null
        System.out.println(hm.put("c", "adb"));//null
        System.out.println(hm.put("abc", "a"));//null

        Set<Map.Entry<String, String>> entries = hm.entrySet();

        for (Map.Entry<String, String> entry : entries) {
            String key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key + " = " + value);
        }
        //a = b
        //b = bcd
        //c = adb
        //abc = a
    }
}

不可变集合

在 List、Set、Map 接口中，都有一个静态方法 of()，可以获取一个不可变的集合

方法名称 说明
static List of(E… elements) 创建指定元素的 List 集合
static Set of(E… elements) 创建指定元素的 Set 集合
static <K, V> Map<K, V> of(K k, V v) 创建指定键和值的 Map 集合
static <K, V> Map<K, V> ofEntries(Entry<? extend K, ? extend V>… entries) 创建指定键值对的 Map 集合
static <K, V> Map<K, V> copyOf(Map<? extends K, ? extends V> map) 创建指定 Map 的不可变集合副本

当进行添加，删除，修改的操作时会抛出UnsupportedOperationException异常