Java 集合

前言

1、集合

  • 一些集合对它们的元素有排序,有些没有。
集合 接口 可组织 可排序 线程安全 可复制 可为空
HashSet Set N N N N One null
LinkedHashSet Set Y N N N One null
TreeSet Set Y Y N N N
ArrayList List Y N N Y Y
LinkedList List, Deque Y N N Y Y
Vector List Y N Y Y Y
HashMap Map N N N N (key) One null (key)
LinkedHashMap Map Y N N N (key) One null (key)
TreeMap Map Y Y N N (key) N (key)
HashTable Map N N Y N (key) N (key)
ArrayDeque Deque Y N N Y N
PriorityQueue Queue N N Y N

1.1 Collection

  • Collection 是一个接口。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    package java.util;

    /**
    * The root interface in the <i>collection hierarchy</i>. A collection
    * represents a group of objects, known as its <i>elements</i>. Some
    * collections allow duplicate elements and others do not. Some are ordered
    * and others unordered. The JDK does not provide any <i>direct</i>
    * implementations of this interface: it provides implementations of more
    * specific subinterfaces like <tt>Set</tt> and <tt>List</tt>. This interface
    * is typically used to pass collections around and manipulate them where
    * maximum generality is desired.
    *
    * @author Josh Bloch, Neal Gafter
    * @see Set, List, Map, SortedSet, SortedMap, HashSet, TreeSet, ArrayList, LinkedList, Vector, Collections, Arrays, AbstractCollection
    * @since 1.2
    */

    public interface Collection<E> extends Iterable<E> {

    }
  • Collection 是 Set、List、Queue 和 Deque 的父接口。

关键字 介绍
Set 集合
List 数组
Queue 队列,先进先出
Deque 链表,双向链表,继承 Queue,间接的继承了 Collection
  • Collection 和 Map 之间没有关系,Collection 是放一个一个对象的,Map 是放键值对的。

  • Collection 和 Collections 的区别

    • Collection 是接口,是 List 和 Set 等的父接口。
    • Collections 是工具类,提供了排序,混淆等等很多实用方法。

1.2 泛型

  • 不指定泛型的容器,可以存放任何类型的元素。指定了泛型的容器,只能存放指定类型的元素以及其子类。

    1
    2
    3
    4
    5
    // 不使用泛型的容器
    List heros1 = new ArrayList();

    // 使用泛型的容器,后面的泛型可以用 <> 来代替
    List<Hero> heros2 = new ArrayList<Hero>();

1.3 hashcode

  • 所有的对象,都有一个对应的 hashcode(散列值)。

1.4 聚合操作

  • JDK8 之后,Java 引入了对集合的聚合操作,可以非常容易的遍历,筛选,比较集合中的元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    import java.util.Comparator;
    import java.util.Collections;

    List<Hero> heros = new ArrayList<>();

    String name = heros // 通过聚合操作找出来的 hp 第三高的英雄名称
    .stream()
    .sorted((h1, h2) -> h1.hp > h2.hp ? -1 : 1)
    .skip(2)
    .map(h -> h.getName())
    .findFirst()
    .get();
  • 要用好聚合,必须先掌握 Lambda 表达式

1.5 Collections

  • Collections 是一个容器的工具类,就如同 Arrays 是数组的工具类。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    package java.util;

    /**
    * This class consists exclusively of static methods that operate on or return
    * collections. It contains polymorphic algorithms that operate on
    * collections, "wrappers", which return a new collection backed by a
    * specified collection, and a few other odds and ends.
    *
    * This class is a member of the Java Collections Framework.
    *
    * @author Josh Bloch, Neal Gafter
    * @see Collection, Set, List, Map
    * @since 1.2
    */

    public class Collections {

    }
  • 常用方法

关键字 简介
reverse 反转
shuffle 混淆
sort 排序
swap 交换
rotate 滚动
synchronizedList 线程安全化
  • 示例

    1
    2
    3
    4
    5
    6
    7
    List<Integer> numbers = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
    numbers.add(i);
    }

    // 反转
    Collections.reverse(numbers);
  • Collection 和 Collections 的区别

    • Collection 是接口,是 List 和 Set 等的父接口。
    • Collections 是工具类,提供了排序,混淆等等很多实用方法。

2、排序

  • 集合框架提供了排序集合的以下方法

    • 引入 Comparator 比较器
    • 实现 Comparable 接口

2.1 Comparator 比较器

  • 按照对象中的某个属性进行排序,直接调用 sort 会出现编译错误,因为类中有各种属性,可以引入比较器 Comparator,指定比较的算法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    import java.util.Comparator;
    import java.util.Collections;

    List<Hero> heros = new ArrayList<>();

    Comparator<Hero> comparator = new Comparator<Hero>() { // 匿名类,引入 Comparator,指定比较的算法
    @Override
    public int compare(Hero h1, Hero h2) { // 重写 compare 方法,按照 hp 进行排序,正数表示 h1 比 h2 要大
    return (h1.hp >= h2.hp) ? 1 : -1;
    }
    };

    Collections.sort(heros, comparator); // 容器工具类 Collections 使用比较器排序
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    import java.util.Comparator;
    import java.util.Collections;

    List<Hero> heros = new ArrayList<>();

    Collections.sort(heros, new Comparator<Hero>() { // 匿名方法
    @Override
    public int compare(Hero h1, Hero h2) { // 重写 compare 方法,按照 hp 进行排序,正数表示 h1 比 h2 要大
    return (int)(h1.hp - h2.hp);
    }
    });

2.2 Comparable 接口

  • 使类实现 Comparable 接口,在类里面提供比较算法,Collections.sort 就有足够的信息进行排序了。

    1
    2
    3
    4
    5
    6
    7
    8
    public class Hero implements Comparable<Hero> {              // Hero 类实现了接口 Comparable,即自带比较信息
    public int hp;

    @Override
    public int compareTo(Hero anotherHero) { // 重写 compareTo 方法,指定比较方式,如果返回 -1, 就表示当前的更小,否则就是更大
    return (hp < anotherHero.hp) ? 1 : -1;
    }
    }
    1
    2
    3
    4
    5
    import java.util.Collections;

    List<Hero> heros = new ArrayList<>();

    Collections.sort(heros); // Collections 直接进行排序,无需额外的 Comparator

3、遍历

  • 集合框架提供了遍历集合的以下方法

    • 使用 迭代器
    • 使用 增强型 for 循环
    • 使用 forEach() 方法

3.1 迭代器

  • 集合提供了一个迭代器来遍历其所有元素。

  • Java 中的迭代器是 Iterator<E> 接口的一个实例。迭代器接口包含以下方法。

    1
    2
    3
    4
    5
    6
    7
    8
    public interface Iterator<E> {

    boolean hasNext(); // 检查是否有尚未访问的元素
    E next(); // 访问集合中的下一个元素

    default void remove(); // 删除集合的最后访问元素
    default void forEachRemaining(Consumer<? super E> action); // 遍历所有元素,对集合中尚未由迭代器访问的每个元素执行操作
    }
  • 迭代器可以对集合执行以下三个操作

    • 检查是否有尚未访问的元素。
    • 访问集合中的下一个元素。
    • 删除集合的最后访问元素。
  • 迭代器是一次性对象。我们不能重置迭代器,它不能被重用。要再次遍历同一集合的元素,请通过调用集合的 iterator() 方法来创建一个新的 Iterator。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;

    // Create a list of strings
    List<String> names = new ArrayList<>();
    names.add("A");
    names.add("B");
    names.add("C");

    // Get an iterator for the list
    Iterator<String> nameIterator = names.iterator(); // 创建迭代器

    // Iterate over all elements in the list
    while (nameIterator.hasNext()) { // 如果集合中有更多元素要迭代,返回 true,否则返回 false
    // Get the next element from the list
    String name = nameIterator.next(); // 返回集合中的下一个元素
    System.out.println(name);
    }

    nameIterator.remove(); // 删除 next() 方法最后返回的元素

    System.out.println(names);
    1
    2
    3
    Iterator<String> nameIterator = names.iterator();           // 创建迭代器

    nameIterator.forEachRemaining(System.out::println); // 遍历所有元素,对集合中尚未由迭代器访问的每个元素执行操作

3.2 增强型 for 循环

  • 可以使用增强型 for 循环遍历任何实现 Iterable 接口的集合。

    1
    2
    3
    4
    Collection<T> yourCollection = ;

    for (T element : yourCollection) {
    }
  • 增强型 for 循环有几个限制

    • 不能使用增强型 for 循环从集合中删除元素。
    • 对于增强型 for 循环,没有办法从集合的中间开始。
    • 增强型 for 循环不提供访问先前访问的元素的方式。
  • 在幕后,增强型 for 循环获取迭代器并调用 hasNext()next() 方法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    import java.util.ArrayList;
    import java.util.List;

    // Create a list of strings
    List<String> names = new ArrayList<>();
    names.add("A");
    names.add("B");
    names.add("C");

    for (String name : names) { // 增强型 for 循环
    System.out.println(name);
    }

3.3 forEach() 方法

  • Iterable 接口包含一个新的 forEach 方法,该方法遍历所有元素并应用操作。

    1
    void forEach(Consumer<? super T> action);             // 遍历所有元素并应用操作
  • forEach() 方法在从 Collection 接口继承的所有集合类型中都可用。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    import java.util.ArrayList;
    import java.util.List;

    // Create a list of strings
    List<String> names = new ArrayList<>();
    names.add("A");
    names.add("B");
    names.add("C");

    names.forEach(System.out::println); // forEach() 方法

4、Set

  • Set 集合

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    package java.util;

    /**
    * A collection that contains no duplicate elements. More formally, sets
    * contain no pair of elements <code>e1</code> and <code>e2</code> such that
    * <code>e1.equals(e2)</code>, and at most one null element. As implied by
    * its name, this interface models the mathematical <i>set</i> abstraction.
    *
    * This interface is a member of the Java Collections Framework.
    *
    * @author Josh Bloch, Neal Gafter
    * @see Collection, List, SortedSet, HashSet, TreeSet, AbstractSet, Collections#singleton(java.lang.Object), Collections#EMPTY_SET
    * @since 1.2
    */

    public interface Set<E> extends Collection<E> {

    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public class HashSet<E> extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    }

    public class LinkedHashSet<E> extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    }

    public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
    }
  • Set 中的元素,不能重复。区分元素是否重复的方法如下。

    • 以 HashSet 为例,判断重复的逻辑是。
    • 首先看 hashcode 是否相同,如果不同,就是不重复的。
    • 如果 hashcode 一样,再比较 equals,如果不同,就是不重复的,否则就是重复的。
  • Set 中的元素,没有顺序。严格的说,是没有按照元素的插入顺序排列。

Set 简介
HashSet 无序存放,具体顺序,既不是按照插入顺序,也不是按照 hashcode 的顺序
LinkedHashSet 按照插入顺序存放
TreeSet 按照从小到大排序存放

4.1 HashSet

  • HashSet 中的元素 不能重复,无序存放。

    1
    HashSet<Object> names = new HashSet<>();
    1
    2
    3
    4
    5
    6
    7
    8
    HashSet<String> names = new HashSet<String>();

    // 插入数据
    names.add("gareen");

    // 第二次插入同样的数据,是插不进去的,容器中只会保留一个
    names.add("gareen");
    System.out.println(names);
  • 常用方法

方法 简介
add Adds the specified element to this set if it is not already present.
contains Returns true if this set contains the specified element.
remove Removes the specified element from this set if it is present.
clear Removes all of the elements from this set.
size Returns the number of elements in this set (its cardinality).
isEmpty Returns true if this set contains no elements.
iterator Returns an iterator over the elements in this set.
  • HashSet 和 ArrayList 的区别

    • HashSet 是集合,其中的数据是无顺序的,其中的数据不能够重复。
    • ArrayList 是数组,其中的数据是有顺序的,其中的数据可以重复。

4.2 LinkedHashSet

  • LinkedHashSet 中的数据是按照插入顺序存放的。

4.3 TreeSet

  • TreeSet 中的数据是按照从小到大排序存放的。

5、List

  • List 数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    package java.util;

    /**
    * An ordered collection (also known as a <i>sequence</i>). The user of this
    * interface has precise control over where in the list each element is
    * inserted. The user can access elements by their integer index (position in
    * the list), and search for elements in the list.<p>
    *
    * This interface is a member of the Java Collections Framework.
    *
    * @author Josh Bloch, Neal Gafter
    * @see Collection, Se, ArrayList, LinkedList, Vector, Arrays#asList(Object[]), Collections#nCopies(int, Object)
    * @see Collections#EMPTY_LIST, AbstractList, AbstractSequentialList
    * @since 1.2
    */

    public interface List<E> extends Collection<E> {

    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    }

    public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    }

    public class Vector<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    }

5.1 ArrayList

  • ArrayList数组的工具类,最常见的容器类。容器的容量会随着对象的增加,自动增长,不用担心会出现数组的边界问题。

    1
    2
    3
    4
    5
    6
    // 容器类 ArrayList,用于存放对象
    ArrayList heros = new ArrayList();
    heros.add(new Hero("盖伦"));

    // 容器的容量 容量 会随着对象的增加,自动增长,不用担心会出现数组的边界问题
    heros.add(new Hero("提莫"));
  • ArrayList 实现了 List 接口。常见的写法会把引用声明为接口 List 类型。

    1
    2
    // 引用声明为 List 类型
    List heros = new ArrayList();
  • 常用方法

方法 简介
add 增加
addAll 把另一个容器所有对象都加进来
get 获取指定位置的对象
contains 判断是否存在
indexOf 获取对象所处的位置
set 替换
remove 删除
clear 清空
size 获取大小
toArray 转换为数组
  • ArrayList 和 LinkedList 的区别

    • ArrayList 是数组结构,定位很快,但是插入和删除很慢。
    • LinkedList 是双向链表结构,插入和删除很快,但是定位很慢。
  • ArrayList 和 Vector 的区别

    • 类的声明一模一样。
    • Vector 是线程安全的类,而 ArrayList 是非线程安全的。
  • ArrayList 和 HashSet 的区别

    • ArrayList 是数组,其中的数据是有顺序的,其中的数据可以重复。
    • HashSet 是集合,其中的数据是无顺序的,其中的数据不能够重复。

5.2 LinkedList

  • 序列分先进先出 FIFO,先进后出 FILO。

    • FIFO 在 Java 中又叫 Queue 队列。
    • FILO 在 Java 中又叫 Stack 栈。
  • LinkedList 是一个双向链表结构的 List,可以很方便的在头部和尾部插入数据。

    1
    2
    3
    4
    5
    6
    7
    // LinkedList 是一个双向链表结构的 list
    LinkedList<Hero> ll = new LinkedList<Hero>();

    // 可以很方便的在头部和尾部插入数据
    ll.addLast(new Hero("hero1"));
    ll.addLast(new Hero("hero2"));
    ll.addLast(new Hero("hero3"));
  • 与 ArrayList 一样,LinkedList 也实现了 List 接口,有诸如 add,remove,contains 等等方法。

方法 简介
add 增加
addAll 把另一个容器所有对象都加进来
get 获取指定位置的对象
contains 判断是否存在
indexOf 获取对象所处的位置
set 替换
remove 删除
clear 清空
size 获取大小
toArray 转换为数组
  • LinkedList 同时实现了双向链表结构 Deque,可以很方便的在头尾插入删除数据。
方法 简介
addFirst 在最前面插入元素
addLast 在最后插入元素
getFirst 查看最前面元素
getLast 查看最后面元素
removeFirst 取出最前面元素
removeLast 取出最后面元素
  • LinkedList 还实现了队列 Queue 接口。
方法 简介
offer 在最后添加元素
peek 查看第一个元素
poll 取出第一个元素
  • ArrayList 和 LinkedList 的区别

    • ArrayList 是数组结构,定位很快,但是插入和删除很慢。
    • LinkedList 是双向链表结构,插入和删除很快,但是定位很慢。
  • heap(堆)和 stack(栈)的区别

    • heap: 堆。
    • stack: 栈 (在一些书籍里,会被翻译为堆栈,实际上指的就是单纯的这个栈)。

    • 存放的内容不一样

      • heap: 是存放对象的。
      • stack: 是存放基本类型(int, float, boolean 等等)、引用(对象地址)、方法调用。
    • 存取方式不一样

      • heap: 是自动增加大小的,所以不需要指定大小,但是存取相对较慢。
      • stack: 是固定大小的,并且是 FILO 先入后出的顺序,并且存取速度比较快。

5.3 Vector

  • Vector 是线程安全的类。

  • ArrayList 和 Vector 的区别

    • 类的声明一模一样。
    • Vector 是线程安全的类,而 ArrayList 是非线程安全的。

6、Map

  • Map 键值对(字典)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    package java.util;

    /**
    * An object that maps keys to values. A map cannot contain duplicate keys;
    * each key can map to at most one value.
    *
    * This interface is a member of the Java Collections Framework.
    *
    * @author Josh Bloch
    * @see HashMap, TreeMap, Hashtable, SortedMap, Collection, Set
    * @since 1.2
    */

    public interface Map<K,V> {

    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    }

    public class LinkedHashMap<K,V> extends HashMap<K,V>
    implements Map<K,V> {
    }

    public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
    }
    1
    2
    3
    public class Hashtable<K,V> extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    }
  • 对于 Map 而言,key 是唯一的,不可以重复的。

    • 以相同的 key 把不同的 value 插入到 Map 中会导致旧元素被覆盖,只留下最后插入的元素。
    • 同一个对象可以作为值插入到 map 中,只要对应的 key 不一样。

6.1 HashMap

  • HashMap 储存数据的方式是 键值对。key 是唯一的,不可以重复。value 可以重复。

    1
    HashMap<String, Object> dictionary = new HashMap<>();
    1
    2
    3
    4
    5
    6
    HashMap<String, String> dictionary = new HashMap<>();
    dictionary.put("adc", "物理英雄");
    dictionary.put("apc", "魔法英雄");
    dictionary.put("t", "坦克");

    System.out.println(dictionary.get("t"));
  • 常用方法

关键字 简介
put 增加、替换
get 获取对象
clear 清空
  • HashMap 和 Hashtable 的区别

    • HashMapHashTable 都实现了 Map 接口,都是键值对保存数据的方式。
    • HashMap 可以存放 null,不是线程安全的类。
    • Hashtable 不能存放 null,是线程安全的类。

6.2 LinkedHashMap

  • LinkedHashMap

6.3 TreeMap

  • TreeMap

6.4 HashTable

  • HashTable

  • HashMap 和 Hashtable 的区别

    • HashMapHashTable 都实现了 Map 接口,都是键值对保存数据的方式。
    • HashMap 可以存放 null,不是线程安全的类。
    • Hashtable 不能存放 null,是线程安全的类。

7、树

  • 是一种非线性存储结构,存储的是具有 “一对多” 关系的数据元素的集合。

7.1 二叉树

  • 二叉树由各种节点组成。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public class Node {

    // 左子节点
    public Node leftNode;

    // 右子节点
    public Node rightNode;

    // 值
    public Object value;
    }
  • 特点

    • 每个节点都可以有左子节点,右子节点。各个节点的度不能超过 2。
    • 每一个节点都有一个值。
  • 排序

    • 排序的第一个步骤是把数据插入到该二叉树中,插入基本逻辑是,小、相同的放左边,大的放右边。
    • 接下来要做的是看,把这些已经排好序的数据,遍历成我们常用的 List 或者数组的形式。二叉树的遍历分左序,中序,右序。
文章目录
  1. 1. 前言
  2. 2. 1、集合
    1. 2.1. 1.1 Collection
    2. 2.2. 1.2 泛型
    3. 2.3. 1.3 hashcode
    4. 2.4. 1.4 聚合操作
    5. 2.5. 1.5 Collections
  3. 3. 2、排序
    1. 3.1. 2.1 Comparator 比较器
    2. 3.2. 2.2 Comparable 接口
  4. 4. 3、遍历
    1. 4.1. 3.1 迭代器
    2. 4.2. 3.2 增强型 for 循环
    3. 4.3. 3.3 forEach() 方法
  5. 5. 4、Set
    1. 5.1. 4.1 HashSet
    2. 5.2. 4.2 LinkedHashSet
    3. 5.3. 4.3 TreeSet
  6. 6. 5、List
    1. 6.1. 5.1 ArrayList
    2. 6.2. 5.2 LinkedList
    3. 6.3. 5.3 Vector
  7. 7. 6、Map
    1. 7.1. 6.1 HashMap
    2. 7.2. 6.2 LinkedHashMap
    3. 7.3. 6.3 TreeMap
    4. 7.4. 6.4 HashTable
  8. 8. 7、树
    1. 8.1. 7.1 二叉树
隐藏目录