Java 集合框架

集合简介

集合是一个数学概念，远远早于 Java。

早在 Java 2 中之前，Java 就提供了特设类。比如: Dictionary、Vector、Stack 和 Properties，这些类用来存储和操作对象组。

虽然这些类都非常有用，但是它们缺少一个核心的，统一的主题。由于这个原因，使用 Vector 类的方式和使用 Properties 类的方式有着很大不同。

集合框架被设计成要满足以下几个目标：

1. 该框架必须是高性能的，基本集合(动态数组、链表、树、哈希表)的实现也必须是高效的。
2. 该框架允许不同类型的集合，以类似的方式工作，具有高度的互操作性。
3. 对一个集合的扩展和适应必须是简单的。

不同于数组，集合在声明时不需要指定固定的容量，它可以在新增或移除内容时自动地增加或缩减其容量。

Java 集合框架图

Java 集合框架主要包括两种类型的容器，一种是 集合(Collection)，存储一个元素集合，另一种是 图(Map)，存储键/值对映射。

Collection 接口又有 3 种子类型:，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

所有的集合框架都包含如下内容:

• 接口: 代表集合的抽象数据类型。例如 Collection、List、Set、Map 等，之所以定义多个接口，是为了以不同的方式操作集合对象。
• 实现类: 集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如: ArrayList、LinkedList、HashSet、HashMap。
• 算法: 实现集合接口的对象里的方法执行的一些有用的计算。例如: 搜索和排序，这些算法被称为多态，因为相同的方法可以在相似的接口上有着不同的实现。

集合框架体系图

集合接口

• Collection 接口: 最基本的集合接口，一个 Collection 代表一组 Object，即 Collection 元素，Java 不提供直接继承自 Collection 的类，只提供继承于的子接口(比如 List 和 Set)。Collection 接口存储一组 不唯一、无序 的对象。
• List 接口: 一个有序的 Collection，使用此接口可以精确控制每个元素插入的位置，能够通过索引(元素在 List 中的位置，类似于数组的下标)来访问 List 中的元素，第一个元素的索引为 0，而且允许有相同的元素。List 接口存储一组 不唯一、有序(插入顺序) 的对象。
• Set 接口: Set 具有和 Collection 完全一样的接口，只是行为上不同，Set 不保存重复的元素。Set 接口存储一组 唯一、无序 的对象。
• SortedSet 接口: 继承于 Set 保存 有序 的集合。
• Map 接口: Map 接口存储 一组键值对象，提供 key 到 value 的映射。
• Map.Entry: 描述在 一个 Map 中的一个元素(key-value)，是 Map 的一个内部类。
• SortedMap 接口: 继承于 Map，使 key 保持在升序排列。

Set 和 List 的区别

1. Set 接口实例存储的是无序的，不重复的数据，List 接口实例存储的是有序的，可以重复的元素。
2. Set 检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变，实现类有 HashSet、TreeSet。
3. List 和数组类似，可以动态增长，根据实际存储的数据的长度自动增长 List 的长度，查找元素效率高，插入删除效率低，因为会引起其他元素位置改变，实现类有 ArrayList、LinkedList、Vector。

集合实现类

实现类	描述
AbstractCollection	实现了大部分的集合接口。
AbstractList	继承于 AbstractCollection 并且实现了大部分 List 接口。
AbstractSequentialList	继承于 AbstractList ，提供了对数据元素的链式访问而不是随机访问。
LinkedList	实现了 List 接口，允许有 null 元素。主要用于创建链表数据结构，该类没有同步方法，如果多个线程同时访问一个 List，则必须自己实现访问同步，解决方法就是在创建 List 时候构造一个同步的 List，LinkedList 查找效率低。
ArrayList	也是实现了 List 的接口，实现了可变大小的数组，随机访问和遍历元素时，提供更好的性能。该类也是非同步的，在多线程的情况下不要使用，ArrayList 增长当前长度的 50%，插入删除效率低。
AbstractSet	继承于AbstractCollection 并且实现了大部分 Set 接口。
HashSet	实现了 Set 接口，不允许出现重复元素，不保证集合中元素的顺序，允许包含值为 null 的元素，但最多只能一个。
LinkedHashSet	具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。
TreeSet	实现了 Set 接口，可以实现排序等功能。
AbstractMap	实现了大部分的 Map 接口。
HashMap	实现了 Map 接口，根据 key 的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。
TreeMap	继承了 AbstractMap，并且使用一颗树。
WeakHashMap	继承 AbstractMap，使用弱密钥的哈希表。
LinkedHashMap	继承于 HashMap，使用元素的自然顺序对元素进行排序。
IdentityHashMap	继承 AbstractMap 类，比较文档时使用引用相等。

此外还有一些更早的类似集合的实现类，如下:

类	描述
Vector	该类和 ArrayList 非常相似，但是该类是线程同步的，可以用在多线程的情况，该类允许设置默认的增长长度，默认扩容方式为原来的 2 倍。
Stack	栈是 Vector 的一个子类，它实现了一个标准的后进先出的栈。
Dictionary	一个抽象类，用来存储 key-value，作用和 Map 相似。
Hashtable	Dictionary 类的子类。
Properties	继承于 Hashtable，表示一个持久的属性集，属性列表中每个键及其对应值都是一个字符串。
BitSet	创建一种特殊类型的数组来保存位值，BitSet 中数组大小会随需要增加。

集合算法

迭代器

一般遍历数组都是采用 for 循环或者增强 for，这两个方法也可以用在集合框架，但是还有一种方法是采用迭代器遍历集合框架，它是一个对象，实现了 Iterator 接口或 ListIterator 接口。

Iterator，使你能够通过循环来得到或删除集合的元素，ListIterator 继承了 Iterator，以允许双向遍历列表和修改元素。

遍历 ArrayList

public class Test {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("World");
        list.add("HAHAHAHA");
        
        // 第一种方法 使用 for-each 遍历 list
        for (String str : list) {
            System.out.println(str);
        }

        // 第二种方法 把链表变为数组进行遍历
        String[] strArray = new String[list.size()];
        list.toArray(strArray);
        for (int i = 0; i < strArray.length; i++) {
            System.out.println(strArray[i]);
        }

        // 第三种方法 使用迭代器进行遍历
        Iterator<String> ite = list.iterator();
        while (ite.hasNext()) {  // 判断下一个元素之后有值
            System.out.println(ite.next());
        }
    }
}

遍历 Map

public class Test {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>();
        map.put("a", "a1");
        map.put("b", "b2");
        map.put("c", "c3");

        // 第一样方法 普遍使用，二次取值
        for (String key : map.keySet()) {
            System.out.println("key = " + key + " and value = " + map.get(key));
        }

        // 第二种方法
        Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, String> entry = it.next();
            System.out.println("key = " + entry.getKey() + " and value = " + entry.getValue());
        }

        // 第三种方法 推荐，尤其容量大时
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println("key = " + entry.getKey() + " and value = " + entry.getValue());
        }

        // 第四种方法 只能遍历 value
        for (String v : map.values()) {
            System.out.println("value = " + v);
        }
    }
}

比较器

TreeSet 和 TreeMap 的按照排序顺序来存储元素，这是通过比较器来精确定义按照什么样的排序顺序，Comparator 接口可以让我们以不同的方式来排序一个集合。

总结

• 集合框架为程序员提供了预先包装的数据结构和算法来操纵他们。
• 集合是一个对象，可容纳其他对象的引用，集合接口声明对每一种类型的集合可以执行的操作。
• 集合框架的类和接口均在 java.util 包中。
• 对象加入集合类，没有使用泛型的话会自动转换成 Object 类型，在取出的时候需要进行强制类型转换，使用泛型之后不用强制转换。

常用实现类

ArrayList

Java ArrayList

ArrayList 是一个可以动态修改的数组，与普通数组相比，它没有固定大小的限制，可以添加或删除元素。

随机访问和遍历元素时，性能很好，该类时线程非同步的。

ArrayList 继承了 AbstractList，并实现了 List 接口。

常用方法

public class ArrayListTest {
    public static void main(String[] args) {
        ArrayList<String> sites = new ArrayList<>();

        // 添加元素
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        System.out.println(sites);

        // 访问元素
        System.out.println(sites.get(1));

        // 修改元素
        sites.set(2, "Wiki");
        System.out.println(sites);

        // 删除元素
        sites.remove(3);
        System.out.println(sites);

        // 计算大小
        System.out.println(sites.size());
        
        // 排序
        Collections.sort(sites);

        // 迭代访问 for
        for (int i = 0; i < sites.size(); i++) {
            System.out.println(sites.get(i));
        }

        // 迭代访问 for-each
        for (String i : sites) {
            System.out.println(i);
        }

        // 迭代访问 Iterator
        Iterator<String> it = sites.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

引用类型

ArrayList 中的元素实际上是对象，以上实例中，数组列表元素都是字符串 String 类型，如果要存储其他类型，而 只能为引用数据类型，这时就需要使用到基本类型的包装类。

基本类型	引用类型
boolean	Boolean
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character
无	BigInteger
无	BigDecimal

BigInteger、BigDecimal 用于高精度运算，但是它们没有对应的基本类型。

LinkedList

Java LinkedList

链表(Linked List)是一种常见的基础数据结构，是一种线性表，但是不会按照线性的顺序存储数据，而是在每一个节点里存放到下一个节点的地址。

线程非同步的，多线程访问时需要自己实现同步，比如构造一个同步的 List

List list = Collections.synchronizedList(new LinkedList(…))

链表可分为 单向链表 和 双向链表。

单向链表节点包含两个值: 当前节点的值和指向下一个节点的链接。

双向链表节点包含三个值: 当前节点的值和指向上一个和指向下一个节点的链接。

与 ArrayList 相比，LinkedList 增加、删除元素的效率更高，而查找、修改元素的效率较低。

以下情况使用 ArrayList

• 频繁访问列表中的某一个元素。
• 只需要在列表末尾添加和删除元素。

以下情况使用 LinkedList

• 需要通过循环迭代来访问列表中的某些元素。
• 频繁的在列表开头、中间、末尾等位置进行添加、删除元素。

常用方法

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        System.out.println(sites);

        // 添加元素到头部
        sites.addFirst("Wiki");
        System.out.println(sites);

        // 添加元素到尾部
        sites.addLast("Wiki");
        System.out.println(sites);

        // 移除头部元素
        sites.removeFirst();
        System.out.println(sites);

        // 移除尾部元素
        sites.removeLast();
        System.out.println(sites);

        // 获取头部元素
        System.out.println(sites.getFirst());

        // 获取尾部元素
        System.out.println(sites.getLast());
    }
}

HashSet

Java HashSet

HashSet 是基于 HashMap 来实现的，是一个不允许有重复元素的集合，允许有一个 null 值。

HashSet 实现了 List 接口，是无序的，非线程安全的，如果多个线程同时修改 HashSet，则结果是不确定的，必须在多线程访问时显式同步对 HashSet 的并发访问。

常用方法

public class HashSetTest {
    public static void main(String[] args) {
        HashSet<String> sites = new HashSet<>();

        // 添加元素
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");
        sites.add("Runoob");  // 重复的元素不会被添加
        System.out.println(sites);

        // 判断元素是否存在
        System.out.println(sites.contains("Runoob"));

        // 删除元素
        sites.remove("Taobao");
        System.out.println(sites);

        // 删除所有元素
        sites.clear();
        System.out.println(sites);

        // 计算大小
        System.out.println(sites.size());
    }
}

HashMap

Java HashMap

HashMap 是一个散列表，存储的内容是键值对(key-value)映射。

HashMap 实现了 Map 接口，是无序的，它根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。

常用方法

public class HashMapTest {
    public static void main(String[] args) {
        HashMap<Integer, String> sites = new HashMap<Integer, String>();

        // 添加元素
        sites.put(1, "Google");
        sites.put(2, "Runoob");
        sites.put(3, "Taobao");
        sites.put(4, "Zhihu");
        System.out.println(sites);

        // 访问元素
        System.out.println(sites.get(3));

        // 删除元素
        sites.remove(4);
        System.out.println(sites);

        // 清空元素
        sites.clear();
        System.out.println(sites);

        // 计算大小
        System.out.println(sites.size());

        // 迭代元素
        Iterator<Map.Entry<Integer, String>> entries = sites.entrySet().iterator();
        while (entries.hasNext()) {
            Map.Entry<Integer, String> entry = entries.next();
            System.out.println(entry.getKey() + " " + entry.getValue());
        }

        for (Integer i : sites.keySet()) {
            System.out.println(i + " " + sites.get(i));
        }

        for (Map.Entry<Integer, String> site : sites.entrySet()) {
            System.out.println(site.getKey() + " " + site.getValue());
        }

        for (String v : sites.values()) {
            System.out.println(v);
        }
    }
}

Iterator

Java Iterator

Iterator 迭代器不是一个集合，它是一个接口，拥有访问集合的方法，可用于迭代 ArrayList、HashSet 等集合。

Iterator 是 Java 迭代器最简单的实现，还有一个集合中的接口 ListIterator，它扩展了 Iterator 接口。

迭代器 it 的基本操作:

• it.next() 返回迭代器的下一个元素，并更新迭代器的状态。
• it.hasNext() 检测集合中是否还有元素。
• it.remove() 将迭代器返回的元素删除。

常用方法

public class IteratorTest {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<>();
        nums.add(12);
        nums.add(8);
        nums.add(2);
        nums.add(23);

        // 获取迭代器
        Iterator<Integer> it = nums.iterator();

        // 判断集合是否还有元素
        while (it.hasNext()) {
            // 返回迭代器的下一个元素
            Integer i = it.next();
            // 删除小于 10 的元素
            if (i < 10) {
                it.remove();
            }
        }

        System.out.println(nums);
    }
}