JAVA之常用数据类型篇（下）

数据类型篇（下）"/>

JAVA之常用数据类型篇（下）

九、 集合

1. 集合的接口与实现是分离的（设计原则）

如：一个队列接口的最小形式可能是下面这样（只包含增加、删除、查询大小等功能）：

这个接口并没有说明队列是如何实现的。通常，队列有两种实现方式：一种是使用循环数组，另一种是使用链表。

                        

每一个实现都可以使用一个实现了Queue接口的类表示：

             

当在程序中使用队列时，一旦构建了集合（那个接口）就不需要知道究竟使用了那种实现。因此，只有在构建集合对象时，使用具体类才有意义。

利用这种方式，一旦改变了想法，就可以轻松的使用另外一种不同的实现。例如，如果觉得LinkedListQueue是个更好的选择，就将代码修改为：

补充：

List lt=new LinkedList() 和 LinkedList lt=new LinkedList() 的区别是什么？

List是接口，LinkedList是它的实现类。第一种方式更通用。例如a是一台手机，可以是水果手机也可以是谷物手机，如果说是一台水果手机，那就只能是水果手机，不能是别的手机。（多态的概念）

2. 集合类概览

所有的集合类都位于java.util包下。最基本的接口有两个：Collection和Map，它们下面包含了一些字接口或实现类。

           

3. Collection接口

Collection接口是List、Set 和 Queue 接口的父接口，通常情况下不被直接使用。所有实现了这个接口的子类，都可以调用其中的方法。

大小与转换

int size()     返回集合有多少个元素

Object[] toArray()   把集合转换为一个数组，所有的集合元素变成对应的数组元素。   

添加元素

1. boolean add(E e)      向集合中添加元素e，如果添加后集合改变了，返回true，否则返回false。    // 比如，对于ArrayList，往里面add重复元素时，这个list仍然会改变，所以返回true，而对于HashSet，往里面add重复元素时，不会改变集合（因为set不能保留重复元素），所以返回false

2. boolean addAll(Collection c)   将集合c中的所有元素添加到集合中。

删除元素

1. boolean remove(Object o)   从集合中删除一个指定元素，当集合中包含了一个或多个元素 o 时，该方法只删除第一个符合条件的元素，该方法将返回 true。//注意：对于Collection，不同类的实现对应的remove功能不同。如，对于像List的remove是按照索引删除！！比如List<E> list = new ArrayList<>(); list.remove(index)就是调的List的remove，按照索引删除。那对于List如何删除特定的元素呢？官方推荐的是使用迭代器（见下），具体可以参考如下几种方法：List如何删除特定元素？

而Set中的remove方法就是删除特定值，所以Set<E> set = new HashSet<>(); set.remove(e)，还是按照值来删除，不是索引。

2. boolean removeAll(Collection c)  从集合中删除所有在集合 c 中出现的元素（相当于把调用该方法的集合减去集合 c）。如果该操作改变了调用该方法的集合，则该方法返回 true。

3. boolean retainAll(Collection c)   从集合中删除集合 c 里不包含的元素（相当于把调用该方法的集合变成该集合和集合 c 的交集），如果该操作改变了调用该方法的集合，则该方法返回 true。

4. void clear()  清除集合中的所有元素，将集合长度变为 0。

5. 使用迭代器删除。（见下面）

6. 注意：Collection无法按照索引删除（当然，使用迭代器除外），因为像Set是没有索引顺序的，只有像List之类的才有顺序，而按照索引删除在这些接口/类内部重新定义了。

迭代器

Collection的iterator()方法返回一个实现了Iterator接口的对象，该对象内部有如下三大类方法：

注意：它不像ListIterator一样，还具有add、set、previous等功能，仅具有三个常用方法！！！

通过反复调用next方法可以逐个访问集合中的每个元素，但是如果到达集合末尾，next方法会抛出一个NoSuchElementException。因此，需要再调用next之前调用hasNext方法。

注意：

1. 元素被访问的顺序取决于集合类型，如果对ArrayList迭代，迭代器将从索引0开始，每迭代一次，索引值加1。然而，如果对HashSet迭代，每个元素将会按照某种随机的次序出现，虽然可以确定在迭代过程中能够遍历到所有元素，但却无法预知每个元素被访问的次序。

2. 注意与C++中迭代器的区别！！！C++中迭代器，只要给定一个索引i，迭代器就可以进行++操作直接移动到指定元素上，而Java中查找元素的唯一方法是调用next，因此应该不断调next。并且，java迭代器是认为在两个元素中间的！！当调用next时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。

3. Iterator接口的remove方法将会删除上次调用next方法时返回的元素。注意：对next方法和remove方法的调用具有相互依赖性，即如果调用remove之前没有调用next，将是不合法的，会报一个IllegalStateException异常。

例如，想删除两个相邻的元素，不能直接这样调用：

it.remove()
it.remove() //error

而是应该这样调：

it.remove()
it.next()
it.remove()  //ok

判断操作

1. boolean isEmpty()   判断集合是否为空

2. boolean contains(Object o)   判断集合是否存在指定元素

3. boolean containsAll(Collection c)   判断集合中是否包含集合c中的所有元素

具体操作实例：

public static void main(String[] args) {ArrayList list1 = new ArrayList(); // 创建集合 list1ArrayList list2 = new ArrayList(); // 创建集合 list2list1.add("one"); // 向 list1 添加一个元素list1.add("two"); // 向 list1 添加一个元素list2.addAll(list1); // 将 list1 的所有元素添加到 list2list2.add("three"); // 向 list2 添加一个元素System.out.println("list2 集合中的元素如下：");Iterator it1 = list2.iterator();while (it1.hasNext()) {System.out.print(it1.next() + "、");    // 输出one、two、three、}
}

示例2：

public static void main(String[] args) {ArrayList list1 = new ArrayList(); // 创建集合 list1ArrayList list2 = new ArrayList(); // 创建集合 list2list1.add("one");list1.add("two");list1.add("three");System.out.println("list1 集合中的元素数量：" + list1.size()); // 输出list1中的元素数量，为3list2.add("two");list2.add("four");list2.add("six");System.out.println("list2 集合中的元素数量：" + list2.size()); // 输出list2中的元素数量list2.remove(2); // 删除第 3 个元素System.out.println("\nremoveAll() 方法之后 list2 集合中的元素数量：" + list2.size());  // 2System.out.println("list2 集合中的元素如下：");Iterator it1 = list2.iterator();while (it1.hasNext()) {System.out.print(it1.next() + "、");  // 输出two、four}list1.removeAll(list2);System.out.println("\nremoveAll() 方法之后 list1 集合中的元素数量：" + list1.size());  // 2System.out.println("list1 集合中的元素如下：");Iterator it2 = list1.iterator();while (it2.hasNext()) {System.out.print(it2.next() + "、");  // one、three}
}

4. 具体的集合——List

import java.utils.List

List描述的是一种有序、可重复的集合。可以通过索引来访问指定位置的集合元素。List 集合默认按元素的添加顺序设置元素的索引，第一个添加到 List 集合中的元素的索引为 0，第二个为 1，依此类推。

List接口Collection的子接口，常用方法如下：

大小

int size()返回列表中的元素数。

增加、删除、改变、查询元素

1. boolean add(E e) 向列表的尾部添加指定的元素
2.void add(int index, E element) 在列表的指定位置插入指定元素        // List特有，Set没有！！甚至TreeSet这种有序集合也没有！！！

3. E remove(int index) 移除列表中指定位置的元素        // 按照索引删除，List特有！！！
4. void clear() 从列表中移除所有元素

5. E set(int index, E element)用指定元素替换列表中指定位置的元素    // List特有！！！
6. E get(int index) 返回列表中指定位置的元素   // List特有！！！

7. int indexOf(E element)  返回与指定元素相等的列表中第一次出现的位置，如果没有，则返回-1    // List特有！！

8. int lastIndexOf(E element)  返回与指定元素相等的列表中最后一次出现的位置，如果没有，则返回-1    // List特有！！

9. List<E> subList(int fromlndex, int tolndex)   返回一个新的集合，新集合中包含 fromlndex 和 tolndex 索引之间的所有元素。包含 fromlndex 处的元素，不包含 tolndex 索引处的元素。

判断

1. boolean isEmpty() 如果列表不包含元素
2. boolean contains(Object o) 如果列表包含指定的元素，则返回 true

3. boolean containsAll(Collection c)   判断集合中是否包含集合c中的所有元素

链表迭代器（重点介绍）

ListIterator<E> listIterator()返回此列表元素的列表迭代器。（继承自Iterator）

和Iteratro相比，它还具有向前遍历的功能！

• List的实现类一：ArrayList

底层是通过数组实现，它具有如下特点：

优点

1. ArrayList 类实现了可变数组的大小

2. 提供了快速基于索引访问元素的方式，对尾部成员的增加和删除支持较好。

缺点

向ArrayList中间插入/删除元素时，效率较低，因此当需要大量插入删除操作时，应选用LinkedList

ArrayList类除了包含 Collection 接口中的所有方法之外,还包括上面列出的List中的所有方法！！！

• List的实现类二：LinkedList

LinkedList 类采用链表结构保存对象，具有如下特点：

优点

1. LinkedList 类实现了可变数组的大小

2. 便于向集合中插入或者删除元素

缺点

LinkedList 类随机访问元素的速度则相对较慢，当需要经常随机访问元素时，用ArrayList

LinkedList类除了包含Collection和上面列出的List的所有方法外，还具有以下特殊方法：

void addFirst(E e)	将指定元素添加到此集合的开头
void addLast(E e)	将指定元素添加到此集合的末尾
E getFirst()	返回此集合的第一个元素
E getLast()	返回此集合的最后一个元素
E removeFirst()	删除此集合中的第一个元素
E removeLast()	删除此集合中的最后一个元素

5. 具体的集合——Set

特点

1.Set中元素没有顺序：Set 集合中的对象不按特定的方式排序，只是简单地把对象加入集合。

例如：HashSet会按照哈希算法将值填入set

Set<Integer> list = new HashSet<>();
list.add(10);
list.add(9);
list.add(11);
list.add(8);
System.out.println(list.toString());     // 输出的是[8, 9, 10, 11]，而不是[10, 9, 11, 8]

2.Set中元素不重复：Set 集合中不能包含重复的对象，并且可以包含 null 元素。

常用方法

Set具有Collection中的所有方法，具体如下：

•  boolean add(Object o)   :向集合中加入一个对象的引用，如果对象已经存在，则返回false，否则返回true
• void clear()                        :删除集合中所有的对象，即不再持有这些对象的引用
• boolean isEmpty()           :判断集合是否为空
• boolean contains(Object o): 判断集合中是否持有特定对象的引用
• Iterartor iterator()              : 返回一个Iterator对象，可以用来遍历集合中的元素
• boolean remove(Object o) :从集合中删除一个对象的引用
• int size()                               :返回集合中元素的数目
• Object[] toArray()                 :返回一个数组，该数组中包括集合中的所有元素

Set的常用实现类一：HashSet

HashSet是采用散列表（哈希表）来存储集合中的元素的。也就是说，HashSet 会调用该对象的 hashCode（）方法得到该对象的 hashCode 值，然后根据 hashCode 值决定该对象在 HashSet 中的存储位置。

关于散列表的详细知识，可以参考如下链接：哈希表原理详解

我们知道，

数组：寻址容易，插入和删除困难；

链表：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是要提起的散列表（哈希表）

注意：如果两个元素通过 equals（）方法比较返回 true，但它们的 hashCode 不同，HashSet 将会把它们存储在不同的位置，可以添加成功。所以， HashSet 集合判断两个元素是否一样的标准是两个对象的 equals（）方法和 hashCode（）方法返回的值都相同。例如，

上面的例子中，类 A 重写了 equals（）方法，而且都返回 true；类 B 重写了 hashCode（）方法，都返回1；类 C 重写了 equals（）和 hashCode（）方法，返回固定值。此时，我们往 HashSet 集合中分别添加两个ABC对象然后打印出来，可以看出，里面有两个 A 对象，两个 B 对象，一个 C 对象。

关于equals()和hashCode()关系详解，参见如下链接：hashcode()与equals()关系

具体总结如下：

1. HashSet 集合判断两个元素是否一样的标准是两个对象的 equals（）方法和 hashCode（）方法返回的值都相同，只有一个相同不能保证两个元素就一定是一样的。

2. hash函数可以保证相同的输入具有相同的输出，但无法保证不同的输入具有不同的输出，因为可能出现散列冲突。

3. 在写一个类的时候，如果以后这个类定义的元素有可能用于HashSet或HashMap，则在重写equals方法时，必须也要重写hashCode方法。

4. 在向HashSet或HashMap添加对象时，hashCode()方法会得到调用，判断已经存储在集合/Map中的对象的hash code值是否与增加的对象的hash code值一致；如果不一致，直接加进去；如果一致，再进行equals方法的比较，equals方法如果返回true，表示对象已经加进去了，就不会再增加新的对象，否则加进去。

具体结合下面一幅图理解：

HashSet中的常用方法都在上面Set里列出来了。

见下面一个例子：

class Example {}public class test {public static void main(String[] args) {Set<Integer> set = new HashSet<>();Integer a = new Integer(1000);Integer b = new Integer(1000);set.add(a);set.add(b);System.out.println(set.size());System.out.println(a == b);Set<Example> set1 = new HashSet<>();Example aa = new Example();Example bb = new Example();set1.add(aa);set1.add(bb);System.out.println(set1.size());System.out.println(aa == bb);}
}

输出：

1
false
2
false

默认的hash函数的输入是对象的地址，如果两个对象地址不同，那么它们的hash值有可能不同（但不能保证一定不同，因为可能散列冲突，这是需要通过equals进一步判断是不是同一个对象）。但Integer类重写了hash函数，可是按照值来计算哈希值，所以上述两个Integer的地址虽然不一样，但哈希值是一样的，并且进一步通过equals判断值也是一样的，所以set就只有一个元素。

 

Set常用实现类二——TreeSet

TreeSet 类同时实现了 Set 接口和 SortedSet 接口。SortedSet 接口是 Set 接口的子接口，可以实现对集合进行自然排序，因此使用 TreeSet 类实现的 Set 接口默认情况下是自然排序的，这里的自然排序指的是升序排序。

TreeSet的底层使用的数据结构是红黑树，关于红黑树的复习，可参考两篇博文：面试常问：什么是红黑树？    30张图带你彻底理解红黑树

注意：1. TreeSet是一个有序的集合，不过这个有序并不是按照添加入集合的顺序排序，而是按照 Comparable接口中定义的方法排序！

2. 将一个元素加入到TreeSet中要比加入到散列表中慢，这是因为它底层是用红黑树实现的。

3. 在写一个类的时候，如果以后这个类定义的元素有可能用于TreeSet，并且想让元素按照自定义规则排序，那么就需要实现Comparable接口自定义排列顺序！！

例如：

class P implements Comparable<P> {String name;int age;public P(String name,int age) {this.name = name;this.age = age;}@Overridepublic String toString() {return "Person [name=" + name + ", age=" + age + "]";}@Overridepublic int compareTo(P o) {return this.age-o.age;}
}public class ComparableTest {public static void main(String[] args) {List<P> personList = new ArrayList<P>();personList.add(new P("ace",22));personList.add(new P("xb",21));personList.add(new P("glm",36));personList.add(new P("sxy",20));System.out.println("比较大小");P ace = new P("ace",22);P xb = new P("xb",21);String result = acepareTo(xb)==0?"一样大":acepareTo(xb)>0?"ace大":"xb大";System.out.println(result);System.out.println("按照年龄");Collections.sort(personList);for(P p:personList)System.out.println(p);System.out.println();}
}

输出：

Java中有很多默认实现了Comparable接口的类，他们比较方式如下：

4. 注意，使用Comparable接口有局限性，比如某一个TreeSet想根据对象的年龄排序，而另一个TreeSet却想根据对象的名字排序，但是这个对象的Comparable的compareTo()方法却只能实现一次，怎么办？

答：可以将Comparable对象传递给TreeSet构造器来告诉树集使用不同的比较方法。

首先，定义一个实现了Comparable接口的类：

然后，将这个对象传递给TreeSet构造器：

 

TreeSet常用方法：

E first()	返回此集合中的第一个元素。其中，E 表示集合中元素的数据类型
E last()	返回此集合中的最后一个元素
E poolFirst()	获取并移除此集合中的第一个元素
E poolLast()	获取并移除此集合中的最后一个元素
SortedSet<E> subSet(E fromElement,E toElement)	返回一个新的集合，新集合包含原集合中 fromElement 对象与 toElement 对象之间的所有对象。包含 fromElement 对象，不包含 toElement 对象
SortedSet<E> headSet<E toElement〉	返回一个新的集合，新集合包含原集合中 toElement 对象之前的所有对象。 不包含 toElement 对象
SortedSet<E> tailSet(E fromElement)	返回一个新的集合，新集合包含原集合中 fromElement 对象之后的所有对 象。包含 fromElement 对象

注意：表面上看起来这些方法很多，其实很简单。因为 TreeSet 中的元素是有序的，所以增加了访问第一个、前一个、后一个、最后一个元素的方法，并提供了 3 个从 TreeSet 中截取子 TreeSet 的方法。

6. 具体的集合——Queue

import java.util.Queue;

队列可以让人方便高效的在头部删除元素，在尾部添加元素。它有一个扩充了的接口Deque(双端队列)，可以让人有效地在头部和尾部同时添加和删除元素。同时，有一个实现类PriorityQueue(优先级队列)，可以让人方便地获取队列中最小的元素（优先级最高）。

Queue包含的方法如下：

1. boolean add(E element);

2. boolean offer(E element);     

// 如果队列没有满，将给定元素添加到这个队列的尾部并返回true。如果队列满了，第一个方法抛出IlleagalStateException异常，第二个方法返回false。

3. boolean remove();

4. boolean poll();

// 加入队列没有满，删除并返回队列的头部元素。如果队列是空的，第一个方法抛出NoSuchElement异常，第二个方法返回null。

5. E element()

6. E peek()

// 如果队列不为空，返回队列的头部元素但不删除。如果队列为空，第一个方法抛出NoSuchElement异常，第二个方法返回null。

Queue的实现类之PriorityQueue

PriorityQueue(优先级队列)是使用了堆的数据结构来组织数据。它可以按照任意顺序插入元素，但总会将最小的元素（优先级最高）移动到堆顶，也因此无论何时调用remove方法，总会获得堆顶元素（即优先级队列中的最小元素）。

使用优先级队列的典型应用场景是任务调度问题，即每一个任务都有一个优先级，任务以随机顺序添加到队列中，每当启动一个新任务时，都将优先级最高的任务从队列中删除。

与TreeSet一样，一个优先级队列既可以保存实现了Comparable接口的对象，也可以保存在构造器中提供比较器的对象。

PriorityQueue实现了Queue中的所有方法，此外，下面还列举了一些构造方法。

1. PriorityQueue();

2. PriorityQueue(int initialCapacity)

// 构造一个存放Comparable对象的优先级队列

3. PriorityQueue(int initialCapacity, Comparator<? super E> c)

// 构造一个优先级队列，并用一个指定的比较器对元素进行排序构造堆

Queue的扩充接口之Deque

Deque是双端队列，支持在首部和尾部同时添加或删除元素。其方法如下：

1. void addFirst(E element)

2. void addLast(E element)

3. boolean offerFirst(E element)

4. boolean offerLast(E element)

// 将对象添加到队列首部或尾部。如果队列满了，则前两个方法将抛出IlleagalStateException异常，而后面两个方法返回False。

5. E removeFirst()

6. E removeLast()

7. E pollFirst()

8. E pollLast()

// 如果队列不空，删除并返回队列头部/尾部元素，如果队列为空，则前两个函数会抛出NoSuchElementException异常，后两个返回null。

9. E getFirst()

10. E getLast()

11. E peekFirst()

12. E peekLast()

// 如果队列不空，返回队列头部/尾部元素，但不删除。如果队列空，则前两个函数会抛出NoSuchElementException异常，后两个返回null。

Deque有两个实现类，分别为：ArrayDeque和LinkedList，实现了上面Deque列出的所有方法。

7. 具体的集合——Map

Map 接口主要有两个实现类：HashMap 类和 TreeMap 类。其中，HashMap 类按哈希算法来存取键对象，而 TreeMap 类可以对键对象进行排序。(注意：散列和比较都只能对键起作用，而不能对值起作用！！！)

究竟选择HashMap还是TreeMap？和Set一样，HashMap稍微快些，如果不需要按照排列顺序访问键，就最好选择HashMap。

注意点：

1. key 和 value 都可以是任何引用类型的数据。Map 的 key 不允许重复，value 可以重复。

2. 每当向Map中添加对象时，必须同时提供一个键，如：staff.put("987-98-996", new Employee("Harry"))；

2. 如果映射表中没有给定键对应的信息，调用get将返回null。

3.如果对同一个键调用两次put方法，则后添加的会取代第一个。

Map包含的方法如下：

大小

1. int size()；  // 返回集合有多少个条目（entry）

增、删、改、查

1. V put(K key, V value)  // 向 Map 集合中添加键-值对，如果当前 Map 中已有一个与该 key 相等的 key-value 对，则新的 key-value 对会覆盖原来的 key-value 对。该方法会返回键对应的旧值，如果这个键以前没有出现过，则返回null。

2. void putAll(Map m)  // 将指定 Map 中的 key-value 对复制到本 Map 中。

3. V remove(Object key)  // 从 Map 集合中删除 key 对应的键-值对，返回 key 对应的 value，如果该 key 不存在，则返回 null

4. boolean remove(Object key, Object value)  // 这是 Java 8 新增的方法，删除指定 key、value 所对应的 key-value 对。如果从该 Map 中成功地删除该 key-value 对，该方法返回 true，否则返回 false。

5. void clear()   // 删除该 Map 对象中的所有 key-value 对。

6. V get(Object key)   // 返回 Map 集合中指定键对象所对应的值。V 表示值的数据类型

判断

1. boolean containsKey(Object key)    // 查询 Map 中是否包含指定的 key，如果包含则返回 true。

2. boolean containsValue(Object value)   // 查询 Map 中是否包含一个或多个 value，如果包含则返回 true。

3. boolean isEmpty()  // 查询该 Map 是否为空（即不包含任何 key-value 对），如果为空则返回 true。

返回三个重要的视图

1. Set<K> keySet()  // 返回 Map 集合中所有键对象的 Set 集合

2. Set<Map.Entry<K, V>> entrySet()  // 返回 Map 集合中所有键-值对的 Set 集合，此 Set 集合中元素的数据类型为 Map.Entry

3. Collection<K> values()  // 返回该 Map 里所有 value 组成的 Collection

注意：keySet与entrySet既不是HashSet，也不是TreeSet，而是实现了Set接口的某个其他类的对象。Set接口扩展了Collection接口，因此可以像使用任何集合一样使用keySet与entrySet。

如：

                    

对于entrySet的操作

1. K getKey()  //返回这个条目的键

2. V getValue() // 返回这个条目的值

使用实例：

public class Test09 {public static void main(String[] args) {HashMap users = new HashMap();users.put("11", "张浩太"); // 将学生信息键值对存储到Map中users.put("22", "刘思诚");users.put("33", "王强文");users.put("44", "李国量");users.put("55", "王路路");System.out.println("******** 学生列表 ********");Iterator it = users.keySet().iterator();while (it.hasNext()) {// 遍历 MapObject key = it.next();Object val = users.get(key);System.out.println("学号：" + key + "，姓名:" + val);}Scanner input = new Scanner(System.in);System.out.println("请输入要删除的学号：");int num = input.nextInt();if (users.containsKey(String.valueOf(num))) { // 判断是否包含指定键users.remove(String.valueOf(num)); // 如果包含就删除} else {System.out.println("该学生不存在！");}System.out.println("******** 学生列表 ********");it = users.keySet().iterator();while (it.hasNext()) {Object key = it.next();Object val = users.get(key);System.out.println("学号：" + key + "，姓名：" + val);}}
}

输出：

******** 学生列表 ********
学号：44，姓名:李国量
学号：55，姓名:王路路
学号：22，姓名:刘思诚
学号：33，姓名:王强文
学号：11，姓名:张浩太
请输入要删除的学号：
22
******** 学生列表 ********
学号：44，姓名：李国量
学号：55，姓名：王路路
学号：33，姓名：王强文
学号：11，姓名：张浩太

 

8. 其他的一些集合简要介绍

1. LinkedHashSet与LinkedHashMap

HashMap和HashSet的遍历是无序的（既不是按照键的大小排序遍历，也不是按照初入先后顺序遍历，而是按照哈希算法排出的顺序遍历，往往不可预知），而LinkedHashMap和LinkedHashSet是两种可以预知迭代顺序的集合类。以LinkedHashMap为例，它是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表（doubly-linked list）的形式将所有entry连接起来（记录当前entry前面一个插入的是哪个entry，后面插入的是哪个entry），这样就可以用于记录元素的插入顺序或访问顺序。

LinkedHashSet集合也是根据元素hashCode值来决定元素存储位置，但它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的。也就是说，当遍历LinkedHashSet集合里元素时，HashSet将会按元素的添加顺序来访问集合里的元素。

           

例如：

则调用staff.keySet().iterator()将按照如下顺序枚举键：

144-25-5464

567-24-2546

157-62-7935

456-62-5527

调用staff.values().iterator()将以下列顺序枚举值：

Amy Lee

Harry Hacker

Gary Cooper

Francesca Cruz

2. EnumSet与EnumMap

当已知一个Set中的所有元素都来自于一个Enum类或一个Map中的所有的key都来自于一个Enum类时，就可以选择使用EnumSet/EnumMap来取代HashSet/HashMap。它们的使用方法和HashSet/HashMap差不多，只不过元素/key是一个枚举类型变量，也正是因为如此，它们的效率也比HashSet/HashMap要高。

参考：一文弄懂EnumMap和EnumSet

3. WeakHashMap

一文搞懂WeakHashMap

4. IdentityHashMap

IdentityHashMap作用

 

9. java视图与包装器

 

10. 算法——Collections类

Collections 类是 Java 提供的一个操作 Set、List 、Queue和 Map 等集合的工具类（其实Collection类中定义的所有方法，传入的参数都是Collection接口，因此所有实现了Collection接口的类都可以使用Collections的方法）。Collections 类提供了许多操作集合的静态方法，借助这些静态方法可以实现集合元素的排序、查找替换和复制等操作。下面介绍 Collections 类中操作集合的常用方法。

• 排序与混排

1. static void sort(List<T> list, Comparator c)         // 根据指定 Comparator 产生的顺序对 List 集合元素进行排序。

a.) 其中Comparator是可选参数，如果不填，默认是根据元素的自然顺序(其实应该是按照待排序对象的comparaTo方法排序)对指定 List 集合的元素按升序进行排序。

b.) 如果想将元素按照自然顺序(其实应该是按照待排序对象的comparaTo方法排序)降序排列，则可以：Collections.sort(items, Collections.reverseOrder())。

c.) 如果想按照自己定义的大小比较方法排序，则可以参照如下例子：

如果想再逆着这个方法排序，则可以Collections.sort(items, Collections.reverseOrder(itemComparator))

注意：JAVA的Collections.sort()方法底层采用的是归并排序实现的，因此它是一个稳定排序算法。

2. void shuffle(List list)      // 刚好与sort相反，它对List元素进行随机打乱

3. void reverse(List list)     // 对list中的元素倒置，注意：并不会倒序排序。如list = [10, 5, 7];则调用完reverse后，list变为[7, 5, 10]

• 查找（用的是二分查找法）与替换

1. int binarySearch(List list, Object key)      // 使用二分搜索法搜索指定的 List 集合，以获得指定对象在 List 集合中的索引。如果要使该方法可以正常工作，则必须保证 List 中的元素已经处于有序状态。

2. boolean replaceAll(List list, Object oldVal, Object newVal)         // 使用一个新值 newVal 替换 List 对象的所有旧值 oldVal。

• 其他的一些简单算法

1. Object max(Collection coll)        // 根据元素的自然顺序，返回给定集合中的最大元素。

2. Object max(Collection coll, Comparator comp)    // 根据 Comparator 指定的顺序，返回给定集合中的最大元素。

3. Object min(Collection coll)    // 根据元素的自然顺序，返回给定集合中的最小元素。

4. Object min(Collection coll, Comparator comp)    // 根据 Comparator 指定的顺序，返回给定集合中的最小元素。

5. boolean addAll(Collection coll, T values)    // 将所有值添加到集合中，如果集合变了，则返回true。

5. int frequency(Collection c, Object o)    // 返回指定集合中指定元素的出现次数

5. void swap(List list, int i, int j)      // 将指定 List 集合中的 i 处元素和 j 处元素进行交换。

6. void rotate(List list, int distance)    // 当 distance 为正数时，将 list 集合的后 distance 个元素“整体”移到前面；当 distance 为负数时，将 list 集合的前 distance 个元素“整体”移到后面。该方法不会改变集合的长度。

7. void fill(List list, Object obj)     // 使用指定元素 obj 替换指定 List 集合中的所有元素。

8. int indexOfSubList(List source, List target)   // 返回子 List 对象在父 List 对象中第一次出现的位置索引；如果父 List 中没有出现这样的子 List，则返回 -1。

9. int lastIndexOfSubList(List source, List target)    // 返回子 List 对象在父 List 对象中最后一次出现的位置索引；如果父 List 中没有岀现这样的子 List，则返回 -1。

10. void copy(List <? super T> dest,List<? extends T> src)   // Collections 类的 copy() 静态方法用于将指定集合中的所有元素复制到另一个集合中。其中，dest 表示目标集合对象，src 表示源集合对象。注意：目标集合的长度至少和源集合的长度相同，如果目标集合的长度更长，则不影响目标集合中的其余元素。如果目标集合长度不够而无法包含整个源集合元素，程序将抛出 IndexOutOfBoundsException 异常。