Java集合详解(Collection接口和Map接口)

Posted on |

Java的 util 包中有两个重要的父接口：Collection 和 Map 。这两个接口提供了诸多数据结构的实现，使我们可以专注于程序的逻辑而不必关心底层细节。

在这篇博文中，我们将讨论以下几种接口，以及它们分别的实现类。

  • java.util package
    • Collection interface
      • List interface
        • ArrayList class
        • LinkedList class
        • Vector class
          • Stack
      • Queue interface
        • PriorityQueue class
      • Set interface
        • HashSet class
        • LinkedHashSet class
        • SortedSet interface
          • TreeSet class
    • Map interface
      • Hashtable class
      • HashMap class
      • LinkedHashMap class
      • SortedMap interface
        • TreeMap class

List接口

List接口对应于 List 抽象数据类型。

1. Overview

List接口有3种具体的实现： - ArrayList类：底层数据结构为 动态数组(array) ， 其中扩展因子为0.5。 - LinkedList类：底层数据结构为 双向链表(doubly linked list) 。 - Vector类：底层数据结构为 动态数组(array)， 其中扩展因子为1。

根据数据结构的知识，如果你需要进行很多的 insertion 或 deletion 操作，那么选用 LinkedList class 会比较好；而如果大量的操作都是 access 操作，那么 ArrayList class 是更好的选择。

⛱️ ArrayList vs. Vector

Vector 和 ArrayList 的底层数据结构都是数组。两者唯一的区别在于：ArrayList中的方法不是线程安全的，而Vector中的方法是同步的，意味着线程安全。所以，如果你需要线程安全，那么应该使用Vector。但对于单线程环境，使用使用Vector会花费更多的资源，所以用ArrayList更好。

如果你查看底层代码，你会发现，Vecotr中的重要操作，如add, remove, get等，这些方法都被 synchronized 关键字所修饰，来保证线程的安全性。

接下来，让我们来几个List的代码片段。

Demos

两种实例化方法

首先需要说明的是，在实例化一个List的时候，除了我们很熟悉的 List<Integer> L = new ArrayList<>(); 方法之外，Java9增加的静态工厂方法 .of() 也可以创建实例，代码如下：

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

public class Demo {
    public static void main(String[] args) {
		List<Integer> L = List.of(0, 1, 2, 3, 4);
//		L.add(5);    // Exception, because L is immutable.
		System.out.println(L);  // [0, 1, 2, 3, 4]
	}
}

不过需要注意的是，使用上述方法创建的List是不可变的(immutable)，也就是说一旦创建好一个List，那么它的值，它的大小都是不可变的。后面的 Set/Map/Queue 也是一样的，就不再赘述了。

List的基本用法

让我们来看一个 ArrayList 的代码片段：

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

public class ArrayListDemo {
	public static void main(String[] args) {
		List<String> words = List.of("Apple", "Peach");
		List<String> wordsArrayList = new ArrayList<>(words);
		System.out.println("Original list: " + wordsArrayList);

		/* Appends an item at the end of list. */
		wordsArrayList.add(0, "Dog");  // position is optional
		System.out.println("after adding Dog at index 0: " + wordsArrayList);

		/* Appends all items at the end of list. */
		List<String> newList = List.of("Mouse", "Cat", "Zebra");
		wordsArrayList.addAll(0, newList);  // position is optional
		System.out.println("after adding a list: " + wordsArrayList);

		/* Removes a specific item. */
		wordsArrayList.remove(0);   //  == wordsArrayList.remove("Dog");
		System.out.println("after removing item at index 0: " + wordsArrayList);

		/* Replaces the item at the specified position. */
		wordsArrayList.set(3, "Fish");
		System.out.println("after changing element at index 3: " + wordsArrayList);
		System.out.println();
	}
}

输出：

1
2
3
4
5
Original list: [Apple, Peach]
after adding Dog at index 0: [Dog, Apple, Peach]
after adding a list: [Mouse, Cat, Zebra, Dog, Apple, Peach]
after removing item at index 0: [Cat, Zebra, Dog, Apple, Peach]
after changing element at index 3: [Cat, Zebra, Dog, Fish, Peach]

无论是ArrayList，还是LinkedList，或是Vector都符合上述展示的List的使用方法，在此就不在写 LinkedList 和 Vector 的代码了。

遍历List

接下来让我们来看一下如何遍历列表元素。这里我们展示3种不同遍历方法，注意它们的使用。

  1. 第1种方法，也是最基本的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;
import java.util.List;

public class ArrayListDemo {
    public static void main(String[] args) {
        List<Integer> L0 = List.of(0, 1, 2, 3, 4);
        List<Integer> L = new ArrayList<>(L0);
        System.out.println("original list: " + L);
        
        /* Removes the odd item */
        for (int i = 0; i < L.size(); i++) {
            int num = L.get(i);
            if (num % 2 != 0) {
            	L.remove(i);
            }
        }
        
        System.out.println("even list: " + L);
    }
}

输出：

1
2
original list: [0, 1, 2, 3, 4]
even list: [0, 2, 4]
  1. 第2种方法，我们使用 foreach 循环：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.ArrayList;
import java.util.List;

public class ArrayListDemo {
    public static void main(String[] args) {
        List<Integer> L0 = List.of(0, 1, 2, 3, 4);
        List<Integer> L = new ArrayList<>(L0);
        System.out.println("original list: " + L);
        
        for (Integer num: L) {
            if (num % 2 != 0) {
                L.remove(num);
            }
        }
        
        System.out.println("even list: " + L);
    }
}

输出：

1
2
3
4
original list: [0, 1, 2, 3, 4]
Exception in thread "main" java.util.ConcurrentModificationException
    ...
    ...

你可以看到，当使用foreach循环时，如果你在循环体内想要进行 remove/add 操作会报错。在这种情况下，你可以使用第1种方法，也可以使用下面讲的第3种方法。

  1. 第3种方法，使用 .iterator() 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayListDemo {
	public static void main(String[] args) {
		List<Integer> L0 = List.of(0, 1, 2, 3, 4);
		List<Integer> L = new ArrayList<>(L0);
		System.out.println("original list: " + L);

		/** .iterator() method:  // in List interface
		 * Returns an iterator over the elements in this list in proper sequence.
		 *
		 * .hasNext() method:  // in Iterator interface
		 * Returns {@code true} if the iteration has more elements.
		 */
		Iterator<Integer> iterator = L.iterator();
		while (iterator.hasNext()) {
			int num = iterator.next();
			if (num % 2 != 0) {
				iterator.remove();
			}
		}

		System.out.println("even list: " + L);
	}
}

// 未完待续

(区别：java.util.Collection 是一个集合接口; java.util.Collections 是一个包装类, 包含有各种有关集合操作的静态多态方法。)

Set Interface

Queue Interface

Map Interface