第10章_集合类(上)

gong_yz大约 31 分钟

1、Java的集合体系

1.1 背景

在java中，数组是最简单的一种容器。但是，数组这种数据结构存在着一定的局限，例如：

数组的大小是固定的，一旦创建之后，数组的大小无法改变；
数组只能存储相同的数据类型；
数组只能按照索引位置（数组下标）进行存取；

为了弥补数组存在的一些局限，Java提供了另一种容器类型，那就是集合。Java在java.util包中提供了两种基本的集合类：Collection和Map。

1.2 Collection

Collection是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法。

Collection接口在Java中有很多具体的实现，主要分类三类：List、Queue和Set。图10-1是一张关于Collection的所有实现的整体关系图。

List、Queue和Set这三种集合有各自的特点。

List和Set之间的主要区别就是存入的元素是否有序、是否可重复。

List的特点是元素有序可重复。所谓有序，就是指元素的存储顺序和放入顺序是保持一致的。所谓可重复，就是指在一个List中，同一个元素可以存储多份
List的具体实现有ArrayList、LinkedList和Vector等。
Set的特点是元素无序且不可重复。所谓无顺序，就是指先放入的元素不一定排在前面。所谓不可重复，就是指相同元素在Set中只会保留一份。
Set的具体实现有HashSet、LinkedHashSet和TreeSet等。

Queue这种存储结构和List、Set有很大的区别，Queue表示的是队列，队列中的所有元素都在队列的“尾部”插入，并从队列的“头部”移除。Queue的具体实现有Priority和LinkedList等。

1.3 Map

Map也是一个集合接口，他主要提供了对键值对对象进行基本操作的通用接口方法。

键值对：键值对是计算机系统和应用程序中的一种数据表示形式。数据模型的全部或部分可以表示为<key，value>，<key,value>就是键值对。

Map接口在JAVA中有很多具体的实现，主要有HashMap、Hashtable、LinkedHashMap和ConcurrentHashMap等。他们之前的关系是如图10-2所示。

1.4 Collections

在Java的集合体系中，除了提供了Collection和Map两大类集合，还提供了一个工具类---Collections。

这个类和Collection最大的区别是：Collections是一个类，而Collection是一个接口；Collections不能被实例化，类中提供了很多的静态方法用于操作集合类，比如对集合的搜素、排序和线程安全化操作。

2、如何对集合进行遍历

2.1 遍历

遍历是指沿着某条搜索路线，依次访问树（或图）中每个节点。遍历的概念也适合于多元素集合的情况。

2.2 基于for循环遍历

最简单的集合遍历方式就是借助for循环,即在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止。代码如下:

List<String> strings = ImmutableList.of("a","b","c","d");
for (int i = e; i< strings.size(); i++){
    System.out. print1n(strings.get(i));

}

输出结果如下：

a
b
c
d

ImmutableList是Guava提供的不可变集合工具类，可以方便地初始化一个不可变集合。关于Guava及不可变集合工具类的内容，我们将在第22章展开介绍。

2.3 foreach循环遍历

foreach循环（Foreach Loop）是计算机编程语言中的一种控制流程语句，通常用来循环遍历数组或集合中的元素。

Java从JDK 1.5.0开始引人foreach循环。在遍历数组、集合方面，foreach为开发人员提供了极大的便利。

foreach语法的格式如下:

for(元素类型t元素变量×:遍历对象obj){
    引用了×的java语句;
}

使用foreach语法遍历集合或者数组的时候,可以实现和普通for循环同样的效果，并且代码更加简洁。所以,foreach循环通常也被称为增强for循环。

使用foreach循环遍历集合的代码如下:

List<String>strings = ImmutableList.of("a","b","c","d");
for(String s: strings){
    System.out.println(s);
}

输出结果如下:

a
b
c
d

其实，增强for循环也是Java提供的一个语法糖，如果将以上代码编译后的Class文件进行反编译（使用jad工具)，则可以得到以下代码:

List<String> strings = ImmutableList.of("a", "b","c", "d");
string s;
for(Iterator iterator = strings.iterator(); iterator.hasNext(); System.out.println(s))

s = (String)iterator.next();

可以发现,增强for循环其实是依赖while循环和Iterator实现的（关于增强for循环的介绍和使用,后面很多章节中还会涉及）。

3、ArrayList、LinkedList和Vector之间的区别

底层数据结构

这三种数据结构中，ArravList和Vector只实现了List接口，而LinkedList同时实现了List和Queue接口。所以,LinkedList既是一个列表，也是一个队列。

ArrayList和Vector是采用数组来存储元素的。数组的特点是可以方便地通过下标访问其中的某一个元素，但是想要向其中插入或者删除数据时就会导致很多元素同时进行移位，如图10-3、图10-4所示。

LinkedList是采用双向链表来存储元素的，链表的特点是插人和删除比较方便,因为它使用双链表，所以不需要在内存中移位。但是想要查找其中的某一个元素就比较复杂了,需要从对头开始一直遍历查找,如图10-5所示。

因为底层的实现方式不同，也就决定了ArrayList和Vector更加适合查找操作比较多的场景，而LinkedList适合插人和删除操作比较多的场景。

扩容机制

ArrayList和Vector是通过数组实现的，数组在初始化时需要指定容量，随着元素越来越多，就需要对数组进行扩容，扩大数组的容量。

在ArrayList中定义了grow方法，用于扩大数组容量。

ArrayList中的扩容代码如下：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

其中扩充容量的主要代码如下：

int newCapacity = oldCapacity + (oldCapacity >> 1);

这段代码表示扩容后的容量（newCapacity)是扩容前数组容量（oldCapacity)的1.5倍。oldCapacity >>1是位运算，在二进制中，右移一位，表示十进制的除以2。

Vector的扩容代码如下：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);

}

其中扩充容量的主要代码是:

int newCapacity = oldCapacity +((capacityIncrement > 0) ? capacityIncrement :oldcapacity);

capacityIncrement是用户可以指定的扩容时增加的容量大小，也就是说,如果用户指定了这个数值为X，那么扩容之后的容量（newCapacity）就是扩容前容量（oldCapacity)+X;如果没有指定这个数值，或者这个数值小于/等于0，那么扩容后的容量(newCapacity) =扩容前容量（oldCapacity） ×2。

线程安全性

在这三种数据结构中，有一种数据结构是线程安全的，那就是Vector，它的所有方法都是加锁了的,可以防止并发的发生,例如:

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public void add(int index, E element) {
    insertElementAt(element, index);
}

public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

可以看到,其中Vector的主要方法都是在方法声明处使用synchronized定义的，表明这个方法是不能被并发访问,这样就不会出现线程安全问题。所以,当我们需要在并发场景中使用List的时候,要使用Vector而不是ArrayList，因为它是线程安全的。

这三种数据结构的区别如表10-1所示。

4、SynchronizedList和Vector有什么区别

SynchronizedList源码

SynchronizedList是java.util.Collections中的一个静态内部类。

在多线程的场景中既可以直接使用Vector类，也可以使用Collections.synchronizedList(List<t> list)方法来返回一个线程安全的List。

具体SynchronizedList是如何实现的呢?我们可以看一下其中主要方法的源码:

public void add(int index, E element) {
    synchronized (mutex) {list.add(index, element);}
}

public E remove(int index) {
    synchronized (mutex) {return list.remove(index);}
}

public E get(int index) {
    synchronized (mutex) {return list.get(index);}

}

可以发现，SynchronizedList中实现的方法几乎都是使用同步代码块对List中的方法进行包装。

Collections的synchronizedList方法的入参是一个List类型，我们可以把任意一个List转换成一个线程安全的List，如ArrayList、LinkedList等。

需要注意的是，SynchronizedList中的listIterator和listIterator(int index)方法并没有做同步处理。所以，在使用SynchronizedList进行遍历时，需要开发者手动加锁。

很多人可能有疑问，当我们想要使用一个线程安全的List时，是使用SynchronizedList还是Vecotr呢?

建议读者使用SynchronizedList，因为它可以定义一个线程安全的LinkedList，这是Vector不具备的功能。

即使是使用数组类型的集合，也建议优先使用SynchronizedList而不是Vector，因为相比于ArrayList，Vector只是提供了线程安全而已，而ArrayList却在很多方面做了优化,如扩容列化等。

5、为什么ArrayList的subList结果不能转换成ArrayList

5.1 介绍

在日常开发中，我们需要经常对List进行各种处理，其中有一种操作读者一定不陌生，那就是从一个List中截取出一部分内谷。例如，我们有一个List，结构是[1,2,3,4,5]，当我们想要保留前三个值时，就会用到subList方法:

List<E> subList(int fromIndex,int toIndex);

subList是List接口中定义的一个方法，该方法主要用于返回一个集合中的一段子集，可以理解为截取一个集合中的部分元素,它的返回值也是一个List。例如:

public static void main(String[] args) {
    List<String> names = new ArrayList<String>() {{
        add("Hollis");
        add("hollischaung");
        add("H");
    }};

List subList = names.subList(0, 1);
System.out.println(subList);

}

以上代码的输出结果如下：[Hollis]

但是，subList方法得到的结果是不能转换成ArrayList、Vector、LinkedList等类型的。我们修改以上代码,将subList的返回值强转成ArrayList:

public static void main(String[] args) {
    List<String> names = new ArrayList<String>() {{
        add("Hollis");
        add("hollischuang");
        add("H");
    }};
    ArrayList subList = names.subList(0, 1);
    System.out.print1n(subList);

}

以上代码将抛出异常：java.lang.classCastExcetion：。。。

不只是强转成ArrayList会报错。强转成LinkedList、Vector等List的实现类同样会报错。为什么会发生这样的报错呢?我们接下来深入分析一下。

5.2 底层原理

首先，我们看一下subList方法返回的List到底是什么,这一点在JDK源码中的注释是这样表述的:

Returns a view of the portion of this list between the specifiedfromIndex,inclusive, and tolndex,exclusive.

也就是说,subList返回的是一个视图。

subList的源码如下:

public List<E> subList(int fromIndex,int toIndex){
    subListRangeCheck(fromIndex,toIndex,size);
    return new SubList(this,0,fromIndex,toIndex);

}

这个方法返回了一个SubList,这个类是ArrayList中的一个内部类。SubList这个类中单独定义了set、get、size、add、remove等方法。

当我们调用subList方法时,会通过调用SubList的构造函数创建一个SubList。这个构造函数的源码如下:

SubList(AbstractList<E> parent,
        int offset, int fromIndex, int toIndex) {
    this.parent = parent;
    this.parentOffset = fromIndex;
    this.offset = offset + fromIndex;
    this.size = toIndex - fromIndex;
    this.modCount = ArrayList.this.modCount;

}

可以看到，在这个构造函数中把原来的List及该List中的部分属性直接赋值给自己的一些属性了。

也就是说，SubList并没有重新创建一个List,而是直接引用了原有的List（返回了父类的视图）,只是指定了它要使用的元素的范围而已—从fromIndex（包含）到tolndex（不包含）。

所以，为什么不能将subList方法得到的集合直接转换成ArravList呢?因为SubList只是ArrayList的内部类,它们之间并没有继承关系，所以无法直接进行强制类型的转换。

5.3 视图有什么问题

通过查看源码，我们知道,subList方法并没有重新创建一个ArrayList，而是返回了一个ArrayList的内部类——SubList。这个SubList是ArrayList的一个视图。这个视图又会带来什么问题呢?我们需要简单写几段代码分析一下。

5.3.1 非结构性改变SubList

public static void main(String[] args) {
	List<String> sourceList = new ArrayList<String>() {
		{
			add("H");
			add("O");
			add("L");
			add("L");
			add("I");
			add("S");
		}
	}
	;
	List<String> subList = sourceList.subList(2, 5);
	System.out.println("sourceList : " + sourceList);
	System.out.println("sourceList.subList(2, 5) 得到List : ");
	System.out.println("subList : " + subList);
	subList.set(1, "666");
	System.out.println("subList.set(1,666)得到List : ");
	System.out.println("subList : " + subList);
	System.out.println("sourceList : " + sourceList);
}

输出结果如下：

sourceList : [H, O, L, L, I, S]
sourceList.subList(2, 5) 得到List : 
subList : [L, L, I]
subList.set(1,666)得到List : 
subList : [L, 666, I]
sourceList : [H, O, L, 666, I, S]

当我们尝试通过set方法改变subList中某个元素的值时,我们发现，原来的那个List中对应元素的值也发生了改变。同理,如果我们使用同样的方法修改sourceList中的某个元素，那么subList中对应的值也会发生改变。

5.3.2 结构性改变SubList

public static void main(String[] args) {
	List<String> sourceList = new ArrayList<String>() {
		{
			add("H");
			add("O");
			add("L");
			add("L");
			add("I");
			add("S");
		}
	}
	;
	List<String> subList = sourceList.subList(2, 5);
	System.out.println("sourceList : " + sourceList);
	System.out.println("sourceList.subList(2, 5) 得到List : ");
	System.out.println("subList : " + subList);
	subList.add("666");
	System.out.println("subList.add(666)得到List : ");
	System.out.println("subList : " + subList);
	System.out.println("sourceList : " + sourceList);
}

输出结果如下：

sourceList : [H, O, L, L, I, S]
sourceList.subList(2, 5) 得到List : 
subList : [L, L, I]
subList.add(666)得到List : 
subList : [L, L, I, 666]
sourceList : [H, O, L, L, I, 666, S]

我们尝试对subList的结构进行改变，即向其追加元素，那么sourceList的结构同样发生改变。

5.3.3 结构性改变原List

public static void main(String[] args) {
	List<String> sourceList = new ArrayList<String>() {
		{
			add("H");
			add("O");
			add("L");
			add("L");
			add("I");
			add("S");
		}
	}
	;
	List subList = sourceList.subList(2, 5);
	System.out.println("sourceList : " + sourceList);
	System.out.println("sourceList.subList(2, 5) 得到List : ");
	System.out.println("subList : " + subList);
	sourceList.add("666");
	System.out.println("sourceList.add(666)得到List : ");
	System.out.println("sourceList : " + sourceList);
	System.out.println("subList : " + subList);
}

得到的结果如下：

Exception in thread "main" java.util.ConcurrentModificationException
  at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1239)
  at java.util.ArrayList$SubList.listIterator(ArrayList.java:1099)
  at java.util.AbstractList.listIterator(AbstractList.java:299)
  at java.util.ArrayList$SubList.iterator(ArrayList.java:1095)
  at java.util.AbstractCollection.toString(AbstractCollection.java:454)
  at java.lang.String.valueOf(String.java:2994)
  at java.lang.StringBuilder.append(StringBuilder.java:131)
  at com.gyz.test.testdemo.test.Test8.main(Test8.java:30)

我们尝试对sourceList的结构进行改变，即向其追加元素，结果发现抛出了Concurrent-ModificationException异常。

我们简单总结一下，List的subList方法并没有创建一个新的List，而是使用了原List的视图,这个视图使用内部类SubList表示。

所以,我们不能把subList方法返回的List强制转换成ArrayList等类，因为它们之间没有继承关系。

另外,视图和原List的修改还需要注意几点,尤其是它们之间的相互影响:

对父(sourceList）子( subList) List做的非结构性修改（non-structural changes ） ,都会影响到彼此。
对子List做结构性修改,操作同样会反映到父List上。
对父List做结构性修改,会抛出ConcurrentModificationException异常。

5.4 如何创建新的 List

如果需要修改subList，又不想改动原list,那么可以创建subList的一个副本:

subList = Lists.newArrayList(subList);
list.stream().skip(strart).limit(end).collect(Collectors.toList());

6、HashSet、LinkedHashSet和TreeSet之间的区别

6.1 实现方式

Set主要有HashSet、LinkedHashSet和TreeSet等几个具体的空现。这三种Set也有各自的特点，下面从几个方面介绍它们。

实现方式

Set其实是通过Map实现的，所以我们在HashSet等源码中看到一个Map类型的成员变量:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
	private transient HashMap<E,Object> map;
}

这个Map的具体实现在不同类型的Set中也不近相同，比如在HashSet中，这个Map的类型是HashMap;在TreeSet中，这个Map的类型是TreeMap，在LinkedHashSet中，这个Map的类刑是LinkedHashMap。

以下是这几个Set中的默认构造方法:

public HashSet() {
	map = new HashMap<>();
}
public TreeSet() {
	this(new TreeMap<E,Object>());
}
public LinkedHashSet(int initialCapacity, float loadFactor, Boolean dummy) {
	map = new LinkedHashMap<>(initialCapacity,loadFactor);
}

因为HashMap和LinkedHashMap都是基于哈希表实现的，TreeMap是基于红黑树实现的,所以HashSet和LinkedHashSet也是基于哈希表实现的，而TreeSet是基于红黑树实现的。

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。

6.2 有序性

因为TreeSet的底层是基于红黑树实现的，而由于每一棵红黑树都是一棵二叉排序树，所以TreeSet中的元素是天然会进行排序的。

一棵空树，或者是具有下列性质的二叉树即为二叉查找树:

若左子树不空，则左子树上所有节点的值均小于它的根节点的值。
若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值。
左、右子树分别为二叉排序树。

因为TreeSet会对元素进行排序，这就意味着TreeSet中的元素要实现Comparable接口。TreeSet的add方法的实现如下:

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

这里调用了TreeMap的put方法：

public V put(K key, V value) {
	Entry<K,V> t = root;
	if (t == null) {
		compare(key, key);
		// type (and possibly null) check
		root = new Entry<>(key, value, null);
		size = 1;
		modCount++;
		return null;
	}
	int cmp;
	Entry<K,V> parent;
	// split comparator and comparable paths
	Comparator<? super K> cpr = comparator;
	if (cpr != null) {
		do {
			parent = t;
			cmp = cpr.compare(key, t.key);
			if (cmp < 0)
			            t = t.left; else if (cmp > 0)
			            t = t.right; else
			            return t.setValue(value);
		}
		while (t != null);
	} else {
		if (key == null)
		        throw new NullPointerException();
		@SuppressWarnings("unchecked")
		        Comparable<? super K> k = (Comparable<? super K>) key;
		do {
			parent = t;
			cmp = k.compareTo(t.key);
			if (cmp < 0)
			            t = t.left; else if (cmp > 0)
			            t = t.right; else
			            return t.setValue(value);
		}
		while (t != null);
	}
	Entry<K,V> e = new Entry<>(key, value, parent);
	if (cmp < 0)
	    parent.left = e; else
	    parent.right = e;
	fixAfterInsertion(e);
	size++;
	modCount++;
	return null;
}

这个方法主要是对Key进行比较，再把Key放入合适的位置。而Key的比较方式又分为以下两种情况:

定义TreeSet( TreeMap)时指定了比较器(Comparator):当我们定义TreeSet( TreeMap)时,传人了一个 Comparator ,那么后面在插入元素时，就会根据我们指定的比较器进行比较，即调用这个Comparator的 compare方法。
传人的元素实现了Comparable接口:当我们需要添加的对象实现了Comparable接口时，那么后面在插人元素时，就会根据这个元素中实现的 compareTo方法进行比较。

所以，TreeSet中的元素是有序的,具体的排序万式是通过Comparator的compare方法或者Comparable的compareTo方法实现的。

Comparable用于使某个类具备可排序能力。

Comparator是一个比较器接口，可以用来对不具备排序能力的对象进行排序。

读者是否有这样的疑问，Set是无序的,List是有序的，那么TreeSet的有顺序又怎么理解呢?

其实我们说Set的无顺序,指的是Set并不按照插入元素时的顺序存储元素。先插人的元素并不一定在前面。而TreeSet中的元素按照大小排序是一种排序手段，和Set的无顺序不冲突。

而LinkedHashSet和HashSet不同,LinkedHashSet是维护了元素的插入顺序的。

6.3 比较方式

和TreeSet有所区别,HashSet和LinkedHashSet并不会对元素进行排序，所以也就不支持传人Comparator，其中的元素也不要求实现Comparable接口。

在HashSet(LinkedHashSet)中,底层是用HashMap(LinkedHashMap)存储数据的。

当向HashSet中添加元素时，首先计算元素的hashCode值，然后通过扰动计算和按位与的方式计算这个元素的存储位置,如果这个位置为空，就将元素添加进去;如果不为空,则用equals方法比较元素是否相等,相等就不添加,否则找一个空位添加。

关于扰动计算、按位与运算等，后续在讲解HashMap的hash方法时还会展开介绍。

我们现在就知道Set是如何保证元素不重复的了。

6.4 是否允许null

这三种Set对null的处理也不太一样，其中HashSet和LinkedHashSet是可以存储null的,但因为元素不能重复,所以只能存储一个null。

而TreeSet中是不能存储null的,向TreeSet中插人null，会报NullPointerException。

这三种数据结构的区别如表10-2所示。

类别	HashSet	LinkedHashSet	TreeSet
有序性	不维护对象的插入顺序	维护对象的插入顺序	根据提供的 Comparator对元素进行排序
比较方式	使用equals()和 hashCode()方法比较对象	使用equals()和 hashCod()方法比较对象	使用compar()和lcompareT()方法比较对象
是否允许存储空值	允许存储一个 mull	允许存储一个null	不允许存储null

7、HashMap、Hashtable和ConcurrentHashMap之间的区别

7.1 HashMap和TreeMap

首先，在实现方式上，HashMap和LinkedHashMap都是干哈希表实现的。它们继承了AbstractMap类并实现了Map接口。而TreeMap继承了AbstractMap类并实现NavigableMap接口，它的底层是基于红黑树实现的。

在有序性方面，因为HashMap底层是基于哈希表实现的，所以它不提供元素在Map中的排列方式的任何保证，它是无序的。而TreeSet是基于红黑树实现的，所以它天然是有序的，具体的排序方式是通过Comparator的compare方法或者Comarablc的compareTo方法来实现的。

另外，HashMap最多允许存储一个null键和多个null值，然而,TreeMap不允许存储null键，但可能包含多个null值。因为一旦有null作为Key，当使用compareTo()或compare()方法时就会抛出一个NullPointerException异常。

除了区别，HashMap和TreeMap还有很多相似之处:

TreeMap和 HashMap都不支持重复键。如果添加相同的Key，那么后加入的元素会覆盖前面的元素。
TreeMap和 HashMap 的实现都不是同步的,我们需要自己管理并发访问，即它们在默认情况下都不是线程安全的。
TreeMap和 HashMap都是 fail-fast的,即迭代器被创建之后,发生任何修改都会导致ConcurrentModificationException 异常。

7.2 HashMap和Hashtable

前面介绍了HashMap和TreeMap，接下来我们再来了解一下Hashtable（注意，不是HashTable)。

Hashtable是Java中很古老的一个存在,最初它继承的还是Dictionary类，后来才成为Map的-种实现。

Hashtable和后来出现的HashMap一样，都是基于哈希表实现的,但它们之间还是有一定区的。

首先，Hashtable是同步的,而HashMap不是。所以,在并发场景由Hashtable会更加安全，但是同时，在性能力，Hashtable就不如HashMap了，因为非同步对象通常比同步对象的性能更好。
Hashtable不允许存储空键或空值，HashMap允许存储一个空键和任意数量的空值。前面说过，HashMap是fail-fast的，但Hashtable不是。

7.3 Hashtable和 ConcurrentHashMap

Hashtable是线程安全的哈希表的实现，但并不建议继续使用Hashtable，主要是因为它太古老了,很多方面都没有后诞生的HashMap优化得好。

HashMap不适合并发场景，如果想使用线程安全的HashMap，那么该怎么办呢?

有一种办法就是使用同步包装容器，像我们介绍的Collections.synchronizedList就能获取一个List的同步包装容器，同理，我们也可以使用Collections.synchronizedMap获得一个线程安全的Map。
但这种实现的同步方式的粒度还是比较粗的,在高并发的场景中，性能并不好。为了解决这样的问题，Java在并发包中给我们提供了很多新的选择,如ConcurrentHashMap等。

那么，ConcurrentHashMap有什么优势呢?相比Hashtable，它又做了哪些优化呢?

之所以不建议继续使用Hashtable，主要是因为它的效率比较低,没办法支持高并发场景,其背后的原理是Hashtable为了保证线程安全,在put、get等方法上都增加了synchronized.
synchronized加锁过程会把对象锁住,当一个同步方法获得了对象锁之后，这个对象上面的其他同步方法都会被阻塞。这大大降低了并发操作的效率,SynchronizedMap的加锁也是类似的原理。
但ConcurrentHashMap却可以支持高并发的场景,而且从诞生开始,JDK一直在对ConcurrentHashMap做优化。

这里先简单介绍一下Java 8之前的ConcurrentHashMap的实现原理，Java 8中的相关优化将在后面章节介绍。

为了解决像Hashtable那样锁粒度太大的问题,ConcurrentHashMap采用了分段（Segment )设计来降低锁的冲突，提升性能。 ConcurrentHashMap把数据分成多个段(Segment）进行存储（默认为16个）,然后给每一段的数据单独配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据是可以被其他线程访问的。

相比于Hashtable在加锁时锁住整个哈希表，每一次ConcurrentHashMap只会对一个小的分段加锁,大大提升了效率。

7.4 小结

本节主要介绍了HashMap、Hashtable、TreeMap和ConcurrentHashMap等几个常见的Map一些区别及背后的原理。

其中HashMap、TreeMap等的区别和前面草节中介绍的HashSet、 TreeSet的区别是类似的。本节重点介绍的Hashtable、ConcurrentHashMap和SynchronizeaMap是三个线程安全的Map，它们之间的区别如表所示。

ConcurrentHashMap	SynchronizedMap	Hashtable
线程安全，无须锁定整个哈希表,只需要一个桶级锁	线程安全,锁定整个Map对象	线程安全,锁定整个Map对象
同时允许多个线程安全地操作Map对象	一次只允许一个线程对一个 Map对象执行操作	一次只允许一个线程对一个 Map对象执行操作
读操作可以不加锁	读和写操作都需要加锁	读和写操作都需要加锁
当一个线程迭代Map对象时,另一个线程被允许修改,并且不会得到ConcurrentModificationException	当一个线程迭代Map对象时,其当一个线程迭代Map对象时,其他线程不允许修改,否则将得到他线程不允许修改,否则将得到ConcurrentModificationException	当一个线程迭代Map对象时,他线程不允许修改,否则将得到他线程不允许修改,否则将得到ConcurrentModificationException
键和值都不允许为空	键和值都允许为空	键和值都不允许为空
在Java 1.5中引人	在Java 1.2中引入	在Java 1.0中引人

8、不要使用双括号语法初始化集合

8.1 背景

由于Java的集合框架中没有提供任何简便的语法结构,这使得建立常量集合的工作非常烦琐:

定义一个空的集合类变量。
向这个集合类中逐一添加元素。
将集合作为参数传递给方法。

例如,将一个Set变量传给一个方法:

Set users = new HashSet();
users.add("Hollis");
users.add("hollis");
users.add("HollisChuang");
users.add("hollis666");
transferUsers(users);

这样的写法稍微复杂，有没有简洁的方式呢？

其实有一个比较简洁的方式，那就是使用双括号语法（double-brace syntax）建立并初始化一个新的集合：

public class DoubleBraceTest {
    public static void main(String[] args) {
        Set users = new HashSet() {{
            add("Hollis");
            add("hollis");
            add("HollisChuang");
            add("hollis666");
        }};
    }

}

同理，创建并初始化一个HashMap的代码如下：

Map<String, String> users = new HashMap<>() {{
    put("Hollis", "Hollis");
    put("hollis", "hollis");
    put("HollisChunag", "HollisChunag");

}};

不只是Set、Map，JDK中的集合类都可以用这种方式创建并初始化。

当我们使用这种双括号语法初始化集合类之后,在对Java文件进行编译时，可以发现一个奇怪的现象，使用javac对DoubleBraceTest进行编译: javac DoubleBraceTest.java

我们会得到两个Class文件:

DoubleBraceTest.class
DoubleBraceTest$1.class

有的读者一看到这两个文件就知道,其中一定用到了匿名内部类。

使用这个双括号语法初始化集合的效果是创建了匿名内部类，创建的类有一个隐式的this指针指向外部类。

8.2 不建议使用双括号语法初始化集合

使用双括号语法创建并初始化集合会导致很多内部类被创建。因为每次使用双大括号初始化集合时,都会生成一个新类,例如:

Map hollis = new HashMap() {{
    put("firstName", "Hollis");
    put("lastName", "Chuang");
    put("contacts", new HashMap() {{
        put("0", new HashMap() {{
            put("blogs", "http://www.hollischuang.com");
        }});
        put("1", new HashMap() {{
            put("wecaht", "hollischuang");
        }});
    }});

}};

这会使得很多内部类被创建出来：

DoubleBraceTest$1$1$1.class
DoubleBraceTest$1$1$2.class
DoubleBraceTest$1$1.class
DoubleBraceTest$1.class
DoubleBraceTest.class

这些内部类需要被类加载器加载,这就带来了一些额外的开销。

如果使用上面的代码在一个方法中创建并初始化一个Map，并从方法中返回该Map，那么该方法的调用者可能会毫不知情地持有一个无法进行垃圾收集的资源。

public Map getMap() {
    Map hollis = new HashMap() {{
        put("firstName", "Hollis");
        put("lastName", "Chuang");
        put("contacts", new HashMap() {{
            put("blogs", "http://www.hollischuang.com");
        }});
        put("1", new HashMap() {{
            put("wechat", "hollischaung");
        }});
    }};
    return hollis;

}

我们通过调用getMap得到一个通过双括号语法初始化出来的Map:

public class DoubleBraceTest {
    public static void main(String[] args) {
        DoubleBraceTest doubleBraceTest = new DoubleBraceTest();
        Map map = doubleBraceTest.getMap();
    }

}

返回的Map将包含一个对DoubleBraceTest的实例的引用。读者可以尝试通过debug或者以下方式确认这一事实。

Field field = map , getclass().getDeclaredField("this$e");
field.setAccessible(true);
System.out.println(field.get(map).getClass());

8.3 替代方案

8.3.1 使用Arrays工具类

当我们想要初始化一个List时，可以借助Arrays类，Arrays中提供了asList，可以把一个数组转换成List:

List<String> list2 = Arrays.asList("hollis ","Hollis","Ho1lisChuang" );

需要注意的是、通过asList得到的只是一个Arrays的内部雷，即一个原来数组的视图List，如果对它进行增删操作则会报错。

8.3.2 使用Stream

Stream是Java提供的新特性,它可以对传入流内部的元素进行筛选、排序、聚合等中间操作（intermediate operate），最后由最终操作（terminal operation)得到前面处理的结果。

我们可以借助Stream来初始化集合:

List<String> list1 =Stream.of("hollis","Hollis","HollisChuang").collect(collectors.toList());

8.3.3 使用第三方工具类

很多第三方的集合工具类可以实现这个功能,如Guava等:

ImmutableMap.of("k1",“v1",“k2",“v2");
ImmutableList.of("a","b","c","d");

关于Guava和其中定义的不可变集合，我们在后续章节中会详细介绍。

8.3.4 Java9内置的方法

在Java 9的List和Map等集合类中已经内置了初始化的方法，如List中包含了12个重载的of方法：

/**
 * Returns an unmodifiable list containing zero elements.
   *
    *See <a href="#unmodifiable" >Unmodifiable Lists</a> for details.
   *@param <E> the icode List's element type
   *@return an empty {@code List}
* @since 9
  */
static <E> List<E> of() {
	return Immutablecollections.emptyList();
}
static <E> List<E> of(E e1) {
	return new Immutablecollections.List12<>(e1);
}
static <E> List<E> of(E... elements) {
	switch (elements.length) {
		// implicit null check of elements
		case 0:
		            return Immutablecollections.emptyList();
		case 1:
		            return new Immutablecollections.List12<>(elements[0]);
		case 2:
		            return new ImmutableCollections.List12<>(elements[0], elements[1]);
		default:
		            return new Immutablecollections.ListN<>(elements);
	}
}

9、同步容器的所有操作一定是线程安全的吗

9.1 Java中的同步容器

在Java中，同步容器主要包括2类:

Vector、Stack 和 HashTable。
Collections类中提供的静态工厂方法创建的类。

本节以相对简单的Vecotr为例,Vector中几个重要方法的源码如下:

public synchronized Boolean add(E e) {
	modCount++;
	ensureCapacityHelper(elementCount + 1);
	elementData[elementCount++] = e;
	return true;
}
public synchronized E remove(int index) {
	modCount++;
	if (index >= elementCount)
	        throw new ArrayIndexOutOfBoundsException(index);
	E oldValue = elementData(index);
	int numMoved = elementCount - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
	                     numMoved);
	elementData[--elementCount] = null;
	// Let gc do its work
	return oldValue;
}
public synchronized E get(int index) {
	if (index >= elementCount)
	        throw new ArrayIndexOutOfBoundsException(index);
	return elementData(index);
}

可以看到，Vector这样的同步容器的所有公有方法都被synchronized修饰了，也就是说，我们可以在多线程场景中放心地单独使用这些方法，因为这些方法本身的确是线程安全的。

请注意上面这句话中有一个比较关键的词:单独。

虽然同步容器的所有方法都加了锁,但是对这些容器的复合操作,无法保证其线程安全性,需要客户端通过主动加锁来保证。

简单举一个例子,我们定义如下删除Vector中最后一个元素的方法:

public Object deleteLast(Vector v){
    int lastIndex= v.size()-1;
    v.remove(lastIndex);

}

上面这个方法是一个复合方法，包括size()和remove()，乍一看好像并没有什么问题,无论是size()方法还是remove)方法都是线程安全的，那么整个deleteLast方法应该也是线程安全的。

但是，在多线程调用该方法的过程中，remove()方法有可能抛出ArrayIndexOutOfBounds-Exception异常。remove()方法的源码如下:

Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: Array indexout of range: 879
    at java.util.Vector.remove(Vector.java:834)
    at com.hollis.Test.deleteLast(EncodeTest.java:48)
    at com.hollis.Test$2.run(EncodeTest.java:28)
    at java.lang. Thread.run(Thread.java:748)

当index≥elementCount时,会抛出ArrayIndexOutOfBoundsException异常，也就是说，当当前索引值不再有效时,将抛出这个异常。

removeLast方法有可能被多个线程同时执行,线程2通过index()获得的索引值为10，在通过remove()删除该索引位置的元素之前,线程1把该索引位置的值删除了，这时在执行线程1时便会抛出异常,如图10-6所示。

为了避免出现类似问题，可以尝试加锁：

 public void deleteLast() {
    synchronized (v) {
        int index = v.size - 1;
        v.remove(index);
    }
}

在deleteLast中对v进行加锁，即可保证同一时刻不会有具他线程删除v中的元素。另外，以下代码被多线程执行时，也要特别注意:

for (int i =; i< v.size(); i++){
    v.remove(i);
}

由于不同线程在同一时间操作同一个Vector，其中包括删除操作，那么就有可能发生线程安全问题。所以，在使用同步容器时，如果涉及多个线程同时执行删除操作，就要考虑是否需要加锁。

9.2 同步容器的问题

前面说过，同步容器可以保证单个操作的线程安全性，但无法保证复合操作的线程安全，遇到这种情况时,必须通过主动加锁的方式来实现线程安全。

除此之外,由于同步容器对其所有方法都加了锁，导致多个线程访问同一个容器时，只能按顺序访问,即使是不同的操作，也要排队，如get和add要排队执行,这就大大降低了容器的并发能力。

9.3 并发容器

针对同步容器存在的并发度低的问题，从Java5开始，在java.util.concurrent包下提供了大量支持高效并发访问的集合类,我们称之为并发容器,如图10-7所示。

针对同步容器的复合操作的问题，一船在Map中发生的比较多，所以在ConcurrentHashMap中增加了对常用复合操作的支持，比如使用putIfAbsent()实现“若没有则添加”的功能，使用replace()实现替换的功能。这2个操作都是原子操作,可以保证线程安全。

并发容器的详细内容在后续章节中会展开介绍。

9.4 小结

同步容器是通过加锁实现线程安全的，并且只能保证单独的操作是线程安全的，无法保证复合操作的线程安全性。同步容器的读和写操作之间会互相阻塞。

并发容器是Java 5中提供的，主要用来代替同步容器。并发容器有更好的并发能力，而且其中的ConcurrentHashMap定义了线程安全的复合操作。

在多线程场景中，如果使用并发容器，那么一定要注意复合操作的线程安全问题,必要时要主动加锁。

在并发场景中，建议直接使用java.util.concurrent包中提供的容器类，在需要复合操作时，建议使用有些容器自身提供的复合方法。

第10章_集合类(上)

# 1、Java的集合体系

# 1.1 背景

# 1.2 Collection

# 1.3 Map

# 1.4 Collections

# 2、如何对集合进行遍历

# 2.1 遍历

# 2.2 基于for循环遍历

# 2.3 foreach循环遍历

# 3、ArrayList、LinkedList和Vector之间的区别

# 底层数据结构

# 扩容机制

# 线程安全性

# 4、SynchronizedList和Vector有什么区别

# 5、为什么ArrayList的subList结果不能转换成ArrayList

# 5.1 介绍

# 5.2 底层原理

# 5.3 视图有什么问题

# 5.3.1 非结构性改变SubList

# 5.3.2 结构性改变SubList

# 5.3.3 结构性改变原List

# 5.4 如何创建新的 List

# 6、HashSet、LinkedHashSet和TreeSet之间的区别

# 6.1 实现方式

# 6.2 有序性

# 6.3 比较方式

# 6.4 是否允许null

# 7、HashMap、Hashtable和ConcurrentHashMap之间的区别

# 7.1 HashMap和TreeMap

# 7.2 HashMap和Hashtable

# 7.3 Hashtable和 ConcurrentHashMap

# 7.4 小结

# 8、不要使用双括号语法初始化集合

# 8.1 背景

# 8.2 不建议使用双括号语法初始化集合

# 8.3 替代方案

# 8.3.1 使用Arrays工具类

# 8.3.2 使用Stream

# 8.3.3 使用第三方工具类

# 8.3.4 Java9内置的方法

# 9、同步容器的所有操作一定是线程安全的吗

# 9.1 Java中的同步容器

# 9.2 同步容器的问题

# 9.3 并发容器

# 9.4 小结

1、Java的集合体系

1.1 背景

1.2 Collection

1.3 Map

1.4 Collections

2、如何对集合进行遍历

2.1 遍历

2.2 基于for循环遍历

2.3 foreach循环遍历

3、ArrayList、LinkedList和Vector之间的区别

底层数据结构

扩容机制

线程安全性

4、SynchronizedList和Vector有什么区别

5、为什么ArrayList的subList结果不能转换成ArrayList

5.1 介绍

5.2 底层原理

5.3 视图有什么问题

5.3.1 非结构性改变SubList

5.3.2 结构性改变SubList

5.3.3 结构性改变原List

5.4 如何创建新的 List

6、HashSet、LinkedHashSet和TreeSet之间的区别

6.1 实现方式

6.2 有序性

6.3 比较方式

6.4 是否允许null

7、HashMap、Hashtable和ConcurrentHashMap之间的区别

7.1 HashMap和TreeMap

7.2 HashMap和Hashtable

7.3 Hashtable和 ConcurrentHashMap

7.4 小结

8、不要使用双括号语法初始化集合

8.1 背景

8.2 不建议使用双括号语法初始化集合

8.3 替代方案

8.3.1 使用Arrays工具类

8.3.2 使用Stream

8.3.3 使用第三方工具类

8.3.4 Java9内置的方法

9、同步容器的所有操作一定是线程安全的吗

9.1 Java中的同步容器

9.2 同步容器的问题

9.3 并发容器

9.4 小结