集合知识点整理

1.前言：数据结构——队列

队列接口先说明有哪些功能，但不说是如何实现的，队列有两种实现方式：

• 循环数组
• 链表

循环数组更加高效，但循环数组是个有界集合，容量有限，如果对象的数量没有上限，最好用链表来实现。

一旦构建了集合就不需要知道到底使用了哪种实现。所以可以使用接口类型存放集合的引用

List<String> list = new ArrayList<>();
list.add("abc");

如果我们想修改成另一种实现，只需要把ArrayList改成LinkedList。

---

2.Collection 接口

collection接口有两个基本方法：

// 如果添加元素确实改变了集合就返回 true;如果没有改变就返回 false，比如添加的元素已经存在就不会改变原集合
boolean add(E element);

// 迭代器，见下一点
Iterator<E> iterator();

---

3.迭代器

Iterator接口有4个方法：

public interface Iterator<E>{
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemaining(Student<? super E> stu);
}

反复调用 next() 方法，能逐个访问集合的每个元素，但如果访问到了集合的末尾，会抛出一个 NoSuchElementException，所以我们在调用next()前最好使用hasNext()检查下。

List<String> list = new ArrayList<>();
list.add("abc");
list.add("123");
list.add("qwe");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next()); // abc 123 qwe
}

当然，如果要循环一个集合，更简单的方法是使用forEach:

for (String s : list) {
    System.out.println(s);
}

也可以使用forEachRemaining：

iterator.forEachRemaining(element -> System.out.println(iterator.next()));

顺序问题：元素被访问的顺序取决于集合类型，如果对 ArrayList 进行迭代，迭代器将从索引0开始，每迭代一次，索引值加1。如果是 HashSet ，每个元素会按照某种特定的次序出现，虽然也能访问到所有元素，但顺序是随机的。

remove()删除的是上次调用 next 方法时返回的元素。所以调用 remove 之前必须要有 next 方法被调用。

---

4.集合中的接口

集合框架的接口

需要注意的是：数组支持的有序集合因为可以快速随机访问，所有最好提供一个整数索引来访问，链表最好使用迭代器来遍历。

---

5.Java 库中的具体集合

image-20180909112447085

集合类型	描述
ArrayList	一种可以动态增长和缩减的索引序列
LinkedList	一种可以在任何位置进行高效地插入和删除操作的有序序列
ArrayDeque	一种用循环数组实现的双端队列
HashSet	一种没有重复元素的无序集合
TreeSet	一种有序集
EnumSet	一种包含枚举类型值的集
LinkedHashSet	一种可以记住元素插入次序的集
PriorityQueue	一种允许高效删除最小元素的集合
HashMap	一种存储键 / 值关联的数据结构
TreeMap	一种键值有序排列的映射表
EnumMap	一种键值属于枚举类型的映射表
LinkedHashMap	一种可以记住键 / 值添加次序的映射表
WeakHashMap	一种其值无用武之地后可以被垃圾回收器回收的映射表
IdentityHashMap	一种用 == 而不是 equals 比较键值的映射表

---

6.链表

数组列表的问题：从中间删除一个元素之后，该元素后面的元素都需要向前移动，在中间插入也是。

链表就没有这个问题。

链表让我想到了比特币的区块结构，看图吧

image-20180909122239957

每个 Link 可以看成一个节点，每个节点存放着前一个节点的引用和后一个节点的引用，所以链表实际上都是双向链接的。回到数组列表的问题，当我们需要插入一个元素的时候，只需要修改该节点以及其前后节点的引用就可以了。

但链表不支持快速的随机访问，如果要查看第100个元素，就必须从头开始，越过99个元素。所以如果程序需要采用整数索引访问元素时，通常不选用链表。

---

7.数组列表

List 接口用于描述一个有序集合，并且集合中每个元素的位置十分重要。有两种访问元素的协议：

1. 用迭代器
2. 用 get 和 set 方法随机访问每个元素

---

8.散列集

如果我们想要访问某个元素，但又忘了它的位置，这时候就需要散列集。该集运用的数据结构为散列表（hash table）。散列表会为每个对象计算一个整数，成为散列码（hash code）。散列码是由对象的实例域产生的。比如下表。

字符串	散列码
"Lee"	76268
"lee"	107020
"eel"	100300

如果是我们自己定义的类，就要实现这个类的hashCode()方法，同时还有equals()方法。

set 类型：set 是没有重复元素的元素集合。set 的 add 方法首先会集中查找要添加的对象，如果不存在，就将这个元素添加进去。

---

9.数集

TreeSet可以看成一个有序的散列集。当添加的时候会比较慢，但查询会比散列集快很多。

使用数集必须能比较元素，所有必须实现 comparable 接口。

---

10.队列与双端队列

队列可以让人们有效的在尾部添加一个元素，在头部删除一个元素。有两个端头的队列，即为双端队列，可以让人们有效的在头部和尾部同时添加或删除元素。不支持在队列中添加元素。Deque 接口由 ArrayDeque 和 LinkedList 实现。

---

11.优先级队列

优先级队列中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行索引。也就是说，无论何时调用 remove 方法，总是获得当前优先级队列中最小的元素。

---

12.映射的两个实现

• HashMap：散列映射对键进行散列。
• TreeMap：树映射用键的整体顺序对元素进行排序，并将其组织成搜索树。

如果不需要按照一定顺序访问键，就选择散列，因为散列更快一些。

一些基本的操作：

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
String myName = maps.get("second");
System.out.println(myName); // zyc

键必须是唯一的，如果 put 的键是重复的，则会覆盖前一个。而且 put 会返回被覆盖的那个值。

---

13.迭代

• 利用 forEach 和 lambda 表达式：

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.forEach((k,v) ->
             System.out.println("key:" + k +",val:" + v));

• 利用迭代器：

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
Iterator<Map.Entry<String,String>> entryIterator = maps.entrySet().iterator();
entryIterator.forEachRemaining(System.out::println);
// entryIterator.forEachRemaining(element -> System.out.println(element));

---

14.Merge

当有这样一个需求：需要更新/新增的映射项在映射存在或者不存在的时候会进行不同的操作，这时候就需要用上merge 了。具体看代码吧

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.merge("first","i am new",(oldVal, newVal) -> {
    System.out.println("1执行了:" + oldVal + "," + newVal);
    return oldVal;
});
maps.merge("first1","i am new",(oldVal, newVal) -> {
    System.out.println("1执行了:" + oldVal + "," + newVal);
    return oldVal;
});

maps.forEach((k,v) ->
             System.out.println("key:" + k +",val:" + v));

/*
    1执行了:ethan,i am new
    key:third,val:zyy
    key:first1,val:i am new
    key:first,val:ethan
    key:second,val:zyc
 */

因为first已经存在了，所以会执行后面的函数，而first1不存在，所以根本就没有执行后面的值，而是仅仅把i am new设为first1对应的值。

---

15.映射视图

虽然很多数据结构认为映射属于集合，但在 java 中，映射并不在集合框架中。不过映射视图是实现了 Collection 的对象。视图包括键集合、值集合以及键值对集合。并且对三者进行remove操作会影响原视图。键是不能重复的，所以直接删除，但值时可以重复的，这里只删除了其中一个，不建议以删除值来删除键值对。

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.put("forth","zyc");
Set<String> keys = maps.keySet();
Collection<String> vals = maps.values();
Set<Map.Entry<String,String>> keyVals = maps.entrySet();
System.out.println(keys);
System.out.println(vals);
System.out.println(keyVals);
keys.remove("first");
vals.remove("zyc");
System.out.println(keyVals);

/*
    [third, forth, first, second]
    [zyy, zyc, ethan, zyc]
    [third=zyy, forth=zyc, first=ethan, second=zyc]
    [third=zyy, second=zyc]
*/