Map相关常见知识

HashMap 和 Hashtable 的区别

HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过 synchronized 修饰。（保证线程安全使用 ConcurrentHashMap ）；
hashtable 效率略低，基本被淘汰
对 Null key 和 Null value 的支持
- HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；
- Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同
- 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
- 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的 tableSizeFor() 方法保证）
底层数据结构
- JDK 1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间。
- Hashtable 没有这样的机制。
哈希函数的实现：HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而 Hashtable 直接使用键的 hashCode() 值。

保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

/**
 * Returns a power of two size for the given target capacity.
 * 找到大于或等于 cap 的最小2的幂
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

HashMap 的长度为什么是 2 的幂次方

位运算效率更高：位运算(&)比取余运算(%)更高效。当长度(length)为 2 的幂次方时，hash % length 等价于 hash & (length - 1)。
可以更好地保证哈希值的均匀分布：扩容之后，在旧数组元素 hash 值比较均匀的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。
扩容机制变得简单和高效：扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置 i+原容量 length）。

HashMap 和 HashSet 区别

HashSet 底层就是基于 HashMap 实现。除了 clone()、writeObject()、readObject() 是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap 和 TreeMap 区别

TreeMap 和 HashMap 都继承自 AbstractMap ， TreeMap 还实现了 NavigableMap 接口和 SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

NavigableMap 接口提供了丰富的方法来探索和操作键值对:

定向搜索: ceilingEntry(), floorEntry(), higherEntry()和 lowerEntry()等方法可以用于定位大于等于、小于等于、严格大于、严格小于给定键的最接近的键值对。
子集操作: subMap(), headMap()和 tailMap() 方法可以高效地创建原集合的子集视图，而无需复制整个集合。
逆序视图:descendingMap() 方法返回一个逆序的 NavigableMap 视图，使得可以反向迭代整个 TreeMap。
边界操作: firstEntry(), lastEntry(), pollFirstEntry()和 pollLastEntry() 等方法可以方便地访问和移除元素。

实现 SortedMap 接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

public class Person {
    private Integer age;
	//...
    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
		/*也可以用lambda表达式
		TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
		  int num = person1.getAge() - person2.getAge();
		  return Integer.compare(num, 0);
		});
		*/

        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了。

相比于 HashMap 来说， TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

HashSet 如何检查重复?

Note

当你把对象加入 HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用 equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

在 JDK 1.8 中，HashSet 的 add()方法只是简单的调用了 HashMap 的 put()方法，并且判断了一下返回值以确保是否有重复元素。
HashSet 中的源码:

// 返回值：当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

在 HashMap 的 putVal() 方法(put 方法会调用 putVal 方法) 中也能看到如下说明：

// 返回值：如果插入位置没有元素返回null，否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
}

即在 JDK 1.8 中，实际上无论 HashSet 中是否已经存在了某元素，HashSet 都会直接插入，只是会在 add() 方法的返回值处告诉我们插入前是否存在相同元素

HashMap 的底层实现

JDK 1.8 之前 HashMap 底层是数组和链表结合在一起使用也就是链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。如图：

HashMap 中的扰动函数（hash 方法）是用来优化哈希值的分布。通过对原始的 hashCode() 进行额外处理，扰动函数可以减小由于糟糕的 hashCode() 实现导致的碰撞，从而提高数据的分布均匀性。

//JDK1.8
	static final int hash(Object key) {
		int h;
	  // key.hashCode()：返回散列值也就是hashcode
	  // ^：按位异或
	  // >>>:无符号右移，忽略符号位，空位都以0补齐
	  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
//JDK.7
	static int hash(int h) {
		// This function ensures that hashCodes that differ only by
		// constant multiples at each bit position have a bounded
		// number of collisions (approximately 8 at default load factor).
	
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

JDK 1.8 之后在解决哈希冲突时有了较大的变化(1.7 及其之前为拉链法)，当链表长度大于阈值（默认为 8），且总元素个数超过 64时，将链表转化为红黑树，以减少搜索时间。

HashMap 源码链表到红黑树的转换

进入 HashMap 源码，然后搜索 treeifyBin 即可看到。

在 putVal 方法中有一段代码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
		//..
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					//TREEIFY_THRESHOLD = 8
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						//红黑树转换（并不会直接转换成红黑树）
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		//...
}

对于 treeifyBin 方法：需要判断是否真的要转换为红黑树

final void treeifyBin(Node<K,V>[] tab, int hash) {
	int n, index; Node<K,V> e;
	//MIN_TREEIFY_CAPACITY = 64 判断当前数组的长度是否小于 64
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
		//小于，进行数组扩容
		resize();
	else if ((e = tab[index = (n - 1) & hash]) != null) {
		//转化为红黑树
		TreeNode<K,V> hd = null, tl = null;
		do {
			TreeNode<K,V> p = replacementTreeNode(e, null);
			if (tl == null)
				hd = p;
			else {
				p.prev = tl;
				tl.next = p;
			}
			tl = p;
		} while ((e = e.next) != null);
		if ((tab[index] = hd) != null)
			hd.treeify(tab);
	}
}

将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树。

HashMap 多线程操作导致死循环问题

JDK 1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK 1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap 。

HashMap 为什么线程不安全？

JDK 1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。

数据丢失这个在 JDK 1.7 和 JDK 1.8 中都存在。

JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。

参考 HashMap putVal 的源码

同时进行 put 操作，并且发生了哈希冲突：

Example

两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。
不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。
随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。

同时 put 操作导致 size 的值不正确，进而导致数据覆盖的问题：(这里描述的是很常见的多线程问题)

Example

线程 1 执行 if(++size > threshold) 判断时，假设获得 size 的值为 10，由于时间片耗尽挂起。
线程 2 也执行 if(++size > threshold) 判断，获得 size 的值也为 10，并将元素插入到该桶位中，并将 size 的值更新为 11。
随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。线程 1、2 都执行了一次 put 操作，但是 size 的值只增加了 1，也就导致实际上只有一个元素被添加到了 HashMap 中。

HashMap 常见的遍历方式

HashMap 的 7 种遍历方式与性能分析

大致分为：

迭代器遍历
1. EntrySet
2. KeySet
For Each 遍历
3. EntrySet
4. KeySet

Lambda 遍历-JDK 1.8+

Stream 流遍历-JDK.8+(分为 6.单线程和 7. 多线程)

// 创建并赋值 HashMap
Map<Integer, String> map = new HashMap();
map.put(1, "Java");
map.put(2, "JDK");
map.put(3, "Spring Framework");
map.put(4, "MyBatis framework");
map.put(5, "Java中文社群");

// 1遍历 iterator entrySet
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
	Map.Entry<Integer, String> entry = iterator.next();
	System.out.println(entry.getKey());
	System.out.println(entry.getValue());
}
 
// 2遍历 iterator keySet
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
	Integer key = iterator.next();
	System.out.println(key);
	System.out.println(map.get(key));
}

 // 3遍历 foreach entrySet
for (Map.Entry<Integer, String> entry : map.entrySet()) {
	System.out.println(entry.getKey());
	System.out.println(entry.getValue());
}

// 4遍历 foreach  keySet
for (Integer key : map.keySet()) {
	System.out.println(key);
	System.out.println(map.get(key));
}

// 5遍历 lambda
map.forEach((key, value) -> {
	System.out.println(key);
	System.out.println(value);
});

// 6遍历 Streams API 单线程
map.entrySet().stream().forEach((entry) -> {
	System.out.println(entry.getKey());
	System.out.println(entry.getValue());
});

// 7遍历 Streams API 多线程
map.entrySet().parallelStream().forEach((entry) -> {
	System.out.println(entry.getKey());
	System.out.println(entry.getValue());
});

对于 HashMap 遍历的性能分析：

存在阻塞时 parallelStream 性能最高, 非阻塞时 parallelStream 性能最低。

当遍历不存在阻塞时, parallelStream 的性能是最低的：

Benchmark               Mode  Cnt     Score      Error  Units
Test.entrySet           avgt    5   288.651 ±   10.536  ns/op
Test.keySet             avgt    5   584.594 ±   21.431  ns/op
Test.lambda             avgt    5   221.791 ±   10.198  ns/op
Test.parallelStream     avgt    5  6919.163 ± 1116.139  ns/op

加入阻塞代码 Thread.sleep(10)后, parallelStream 的性能才是最高的:

Benchmark               Mode  Cnt           Score          Error  Units
Test.entrySet           avgt    5  1554828440.000 ± 23657748.653  ns/op
Test.keySet             avgt    5  1550612500.000 ±  6474562.858  ns/op
Test.lambda             avgt    5  1551065180.000 ± 19164407.426  ns/op
Test.parallelStream     avgt    5   186345456.667 ±  3210435.590  ns/op

ConcurrentHashMap的底层实现 (和 Hashtable 的区别)

在实现线程安全的方式上不同。

底层数据结构：
- JDK 1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK 1.8 采用的数据结构跟 HashMap 1.8 的结构一样，数组+链表/红黑二叉树。
- JDK 1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
- Hashtable 采用数组+链表的形式
实现线程安全的方式（重要）：
- 在 JDK 1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
- 到了 JDK 1.8 的时候，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK 1.6 以后 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK 1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
- Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

JDK 1.8 之前的 HashMap 和 HashTable 都是使用的数组+链表的形式

拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。如图：

JDK 1.7

JDK 1.8 之前的 ConcurrentHashMap：由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 数组中的每个元素包含一个 HashEntry 数组，每个 HashEntry 数组属于链表结构。

即 Segment 数组 + HashEntry 数组 + 链表

首先将数据分为一段一段（这个“段”就是 Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

Segment 继承了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

Note

可重入锁是一种支持一个线程多次获取同一把锁的锁，也就是说，一个线程在持有锁的情况下，可以再次获取这把锁而不会发生死锁。可重入锁通常会维护一个计数器来记录当前线程获取锁的次数，只有当计数器为零时，锁才会被释放。这种机制确保了在同一个线程内部可以多次获取锁而不会产生死锁的情况。常见的可重入锁包括 ReentrantLock 和 synchronized 关键字。

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

Segment 的结构和 HashMap (JDK 1.8 之前)类似，是一种数组和链表结构。

一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

JDK 1.8

JDK 1.8 及其之后的为：Node 数组 + 链表 / 红黑树(与 HashMap JDK1.8 之后的实现相似)

Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。

Note

TreeNode 是存储红黑树节点，被 TreeBin 包装。TreeBin 通过 root 属性维护红黑树的根结点，因为红黑树在旋转的时候，根结点可能会被它原来的子节点替换掉，在这个时间点，如果有其他线程要写这棵红黑树就会发生线程不安全问题，所以在 ConcurrentHashMap 中 TreeBin 通过 waiter 属性维护当前使用这棵红黑树的线程，来防止其他线程的进入。

源码：

static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
		//...
}

ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

JDK 1.7 和 JDK1.8 实现的区别

线程安全实现方式：
- JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。
- JDK 1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。
Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK 1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。
并发度：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

ConcurrentHashMap 为什么 key 和 value 不能为 null？

ConcurrentMaps（ConcurrentHashMaps，ConcurrentSkipListMaps）不允许使用 null 的主要原因是，在非并发映射中可能刚好可以容忍的歧义，无法得到容纳。主要原因是，如果 map.get(Key) 返回 null，则无法检测键是否显式地映射到 null 还是未映射键。在非并发映射中，您可以通过 map.contains(Key) 来检查这一点，但在并发映射中，map 可能在调用之间发生变化。

多线程下无法正确判定键值对是否存在（存在其他线程修改的情况），单线程是可以的（不存在其他线程修改的情况）。

如果确实需要在 ConcurrentHashMap 中使用 null 的话，可以使用一个特殊的静态空对象来代替 null。

public static final Object NULL = new Object();

ConcurrentHashMap 能保证复合操作的原子性吗？

复合操作是指由多个基本操作(如 put、get、remove、containsKey 等)组成的操作，例如先判断某个键是否存在 containsKey(key)，然后根据结果进行插入或更新 put(key, value)。

ConcurrentHashMap 是线程安全的，意味着它可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况，也不会导致 JDK 1.7 及之前版本的 HashMap 多线程操作导致死循环问题。

但并不意味着它可以保证所有的复合操作都是原子性的

Example

对于下面的代码：

// 线程 A
if (!map.containsKey(key)) {
map.put(key, value);
}
// 线程 B
if (!map.containsKey(key)) {
map.put(key, anotherValue);
}

如果线程 A 和 B 的执行顺序是这样：

线程 A 判断 map 中不存在 key
线程 B 判断 map 中不存在 key
线程 B 将 (key, anotherValue) 插入 map
线程 A 将 (key, value) 插入 map

那么最终的结果是 (key, value)，而不是预期的 (key, anotherValue)。这就是复合操作的非原子性导致的问题。

那如何保证 ConcurrentHashMap 复合操作的原子性呢？
ConcurrentHashMap 提供了一些原子性的复合操作，如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge 等。这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中。

可以改写为：

// 线程 A
map.putIfAbsent(key, value);
// 线程 B
map.putIfAbsent(key, anotherValue);

//or

// 线程 A
map.computeIfAbsent(key, k -> value);
// 线程 B
map.computeIfAbsent(key, k -> anotherValue);

也可以加锁同步，但不建议使用加锁的同步机制，违背了使用 ConcurrentHashMap 的初衷。在使用 ConcurrentHashMap 的时候，尽量使用这些原子性的复合操作方法来保证原子性。

Collections 工具类

排序
查找,替换操作
同步控制(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

排序操作：

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

查找,替换操作

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

同步控制：(别用)
Collections 提供了多个 synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。
我们知道 HashSet，TreeSet，ArrayList, LinkedList, HashMap, TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

效率非常低

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。