JAVA基础（4）——容器（2）——普通容器

川长思鸟来 2022-07-14 21:37 142阅读 0赞

JAVA基础系列规划：

*  [JAVA基础（1）——基本概念][JAVA_1]
 *  [JAVA基础（2）——数据类型][JAVA_2]
 *  [JAVA基础（3）——容器（1）——常用容器分类][JAVA_3_1]
 *  [JAVA基础（4）——容器（2）——普通容器][JAVA_4_2]
 *  JAVA基础（5）——并发（1）——总体认识
 *  JAVA基础（6）——并发（2）——原子
 *  JAVA基础（7）——并发（3）——锁机制
 *  JAVA基础（8）——并发（4）——线程池
 *  [JAVA基础（9）——容器（3）——并发容器][JAVA_9_3]
 *  [JAVA基础（10）——IO、NIO][JAVA_10_IO_NIO]
 *  [JAVA基础（11）——泛型][JAVA_11]
 *  [JAVA基础（12）——反射][JAVA_12]
 *  [JAVA基础（13）——序列化][JAVA_13]
 *  JAVA基础（14）——网络编程

--------------------

在[《 JAVA基础（3）——容器（1）——常用容器分类》][JAVA_3_1]对Java常用容器进行了一个分类。这篇文章将介绍下普通容器，并发容器将单独一篇文章进行介绍。

按照实现接口，对常用普通容器分类如下：

*  实现List接口的有：Vector、ArrayList、LinkedList
 *  实现Queue接口的有：ArrayQueue、LinkedList、PriorityQueue、
 *  实现Set接口的有：HashSet、LinkedHashSet、TreeSet
 *  实现Map接口的有：EnumMap、IdentityHashMap、HashMap、LinkedHashMap、WeakHashMap、TreeMap

要更深入的了解容器的特性，最好的方法就是研读jdk容器的源码。容器很多，实现也各不相同，具体解释也不是一两句话能够说清楚的。这里，我就不再赘述源码的实现了，而是将我在阅读源码时理解到的重点总结出来。

# 1. List #

List是有序列表的意思。

**Vector**

Vector是最早的List，jdk1.0出现。底层为数组，容量是可以动态变化的（当然扩容也是有最大容量限制的），扩容时会发生信息数据拷贝，性能会受影响。序列化时会序列化整个数组，包括未存储数据的区域。数组元素的操作是同步的，保证了数据的安全。但同步会有大量的性能的损失，在单线程使用过程中不需要这一措施，这是ArrayList等非线程安全容器出现的一个原因。

**ArrayList**

ArrayList在jdk1.2出现。和Vector有些类似，区别主要在同步、数据序列化方面。容量也是可以动态变化的，扩容时发生数据拷贝。序列化时不会序列化整个数组，而是只序列化存储的有效数据。

> ArrayList内部维护着Object\[\] elementData，elementData是transient修饰的，表示序列化时不序列化elementData。ArrayList在writeObject方法中手动将存储的元素序列化。  
> ArrayList在序列化的时候会调用writeObject，直接将size和element写入ObjectOutputStream；反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。使用这种序列化的原因在于，elementData是一个缓存数组，通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用序列化方式，可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

ArrayList的主要用途是高效的随机访问，最没有效率的地方就是频繁的添加操作，这个操作可能会引起ArrayList的扩容，扩容的时候会copy数组浪费点时间，而LinkedList没有扩容时的问题。删除操作需要移动数组，按照index进行删除时耗时只在移动数组上，按对象进行删除时耗时在两方面，一方面需要从头比较元素，另一方面进行删除并移动数组。

数组元素即非final，同时数组元素的操作也未考虑线程安全，因此ArrayList非线程安全。要让ArrayList变的线程安全，可使用Collections.synchronizedLis获取ArrayList线程安全封装类。这个封装类实际上是对操作数据的方法进行了synchronized的包装。

**LinkedList**

LinkedList自jdk1.2出现。内部维护一个链表。序列化和ArrayList类似，只序列化有戏数据。LinkedList随机访问的效率很低，大于size>>1的位置，从表头依次查找，小于size>>1的位置，表尾依次查找。添加操作比较高效，没有扩容问题。删除操作的耗时主要在数据查找，需要找到指定index的元素或者指定value的元素，删除Node的耗时很小。由于LinkedList的Node，既不是final的，操作Node的部分也不是线程安全的，因此LinkedList是非线程安全的。同时LinkedList还实现了Queue接口，具有先进先出的特性。

> LinkedList内部维护一个链表，Node< E> first是链表头节点，Node< E> last是链表尾节点，这两个变量只是链表的标识，没有实际的数据意义，因此被transient修饰，不序列化。LinkedList在序列化时会调用writeObject，将size和遍历得到的数据进行序列化。

# 2. Queue #

Queue是一种队列，具有先进先出的特性。需要使用队列特性时，首选ArrayDeque。

**ArrayDeque**

ArrayDeque自jdk1.6出现，内部是循环数组结构，数组的任何一点都可能被看作起点head或者终点tail，使用(tail = (tail + 1) & (elements.length - 1)) == head判断是否越界。可以动态扩容。和ArrayList类似，序列化时只序列化有效数据。数组元素即非final，同时数组元素的操作也未考虑线程安全，因此ArrayDeque非线程安全。关于其用途有这样的描述：作为堆栈时，它比Stack快；作为队列时，它比LinkedList快。

> Java里有一个叫做Stack的类，却没有叫做Queue的类（它是个接口名字）。当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque；既然Queue只是一个接口，当需要使用队列时也就首选ArrayDeque了（次选是LinkedList）。

**PriorityQueue**

PriorityQueue来自jdk1.5，从字面意思看，即保持了队列先进先出的特性，又增加了优先级特性，能保证每次取出的元素都是队列中权值最小的。内部是数组实现的小根堆，同样存在扩容问题。数据元素操作也是非线程安全的，因此PriorityQueue也是非线程安全的。

> 关于大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器。

# 3. Map #

Map是一种键值对结构。

**Hashtable**

Hashtable源自jdk1.0，继承Dictionary，实现Map、Cloneable、Serializable。内部维护private transient Entry< ?,?>\[\] table。默认容量为11，默认负载因子为0.75。序列化时会取出所有数据元素进行序列化。

其内部实现是：通过散列的方法将元素散列到表的不同行上，table的每一行都是一个链表。相同hashcode的元素在同一行，通过链表链接，Entry是链表的一个节点。当table元素个数超过threshold = (int)Math.min(currentCapacity \* loadFactor, MAX\_ARRAY\_SIZE + 1)时，会进行再哈希，再hash后table大小为newCapacity = (oldCapacity << 1) + 1，但不能超过MAX\_ARRAY\_SIZE。因为和table相关的方法都是synchronized的，所以线程安全。

**HashMap**

HashMap源自jdk1.2，继承AbstractMap，实现Map、Cloneable、Serializable。内部维护transient Node< K,V>\[\] table。默认容量16，最大容量1 << 30，默认负载因子0.75。

其内部实现和Hashtable类似，主要区别在于和table相关的方法都是非线程安全的，因此非线程安全。

**LinkedHashMap**

LinkedHashMap源自jdk1.4，继承HashMap，实现Map。内部是Hash表和链表的实现，并且依靠着双向链表保证了迭代顺序是插入的顺序。table相关操作未加线程安全，因此非线程安全。

链表的维护是依靠重写HashMap的三个函数：

afterNodeAccess(Node< K,V> p)
    afterNodeInsertion(boolean evict)
    afterNodeRemoval(Node< K,V> p)

**WeakHashMap**

WeakHashMap源自jdk1.2，和HashMap一样，WeakHashMap 也是一个散列表。具有弱键特性，当某个键不再正常使用时，会被从WeakHashMap中被自动移除。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。某个键被终止时，它对应的键值对也就从映射中有效地移除了。非线程安全。

> 关于弱键，大致上通过WeakReference和ReferenceQueue实现的。eakHashMap的key是“弱键”，即是WeakReference类型的；ReferenceQueue是一个队列，它会保存被GC回收的“弱键”。当某“弱键”不再被其它对象引用，并被GC回收时。在GC回收该“弱键”时，这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中。当下一次我们需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的键值对；同步它们，就是删除table中被GC回收的键值对。

**TreeMap**

TreeMap源自jdk1.2，内部维护红黑树，要更好的理解TreeMap还是需要学习下红黑树算法，需要学习详细实现的，请看源码。

> 红黑树是一种平衡排序二叉树。树中的任何节点的值大于它的左子节点，且小于它的右子节点，同时任何节点左右两个子树的高度差的绝对值不超过1。

TreeMap根据comparator进行值比较，保证数据的顺序。如果需要按自然顺序或自定义顺序遍历键，它是不错的选择，从其中取出来是排序后的键值对。每次put操作内部插入数据后，进行红黑树的再平衡。非线程安全。

put操作主要分为两个步骤，第一：构建排序二叉树，第二：平衡二叉树。

对于排序二叉树的创建，其添加节点的过程如下：

1.  以根节点为初始节点进行检索。
2.  与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。
3.  循环递归2步骤知道检索出合适的叶子节点为止。
4.  将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点。

普通的排序二叉树可能会出现失衡的情况，所以下一步就是要进行调整。fixAfterInsertion(e); 调整的过程会涉及到红黑树的左旋、右旋、着色三个基本操作。

**EnumMap**

EnumMap源自jdk1.5，是一个键为枚举类型的Map，内部使用数组来实现的。put方法通过key的ordinal将值存储到对应的地方，get方法则根据key的ordinal获取对应的值。遍历时，通过hasNext跳过空的数组，也就是说，保证了遍历顺序与Enum中key的先后顺序一致。

EnumMap主要解决在使用枚举数组时的问题，封装了用序数索引数组的操作，运行速度基本和序数索引数组相同，但更加安全。但非线程安全。

**IdentityHashMap**

IdentityHashMap源自jdk1.4，内部使用数组实现，transient Object\[\] table。key的比较的基于引用相等。扩容同样为原数组复制到新数组，扩容后大小为newLength = newCapacity \* 2。非线程安全。基于引用相等的特性，常用在序列化、深度复制或者记录对象代理等场景。

# 4. Set #

Set是无序列表。

**HashSet**

HashSet源自jdk1.2，内部维护着HashMap，是一个key-value结构。set的数据是map的key，因此创建一个private static final Object PRESENT = new Object()作为value。操作基本都是围绕map的key进行操作。和HashMap一样，非线程安全

**LinkedHashSet**

LinkedHashSet源自jdk1.4，extends HashSet< E> implements Set, Cloneable, java.io.Serializable。内部维护map = new LinkedHashMap<>(initialCapacity, loadFactor);，默认容量为16，默认负载因子为0.75。其他操作和HashSet一样。非线程安全

**TreeSet**

TreeSet源自jdk1.2，extends AbstractSet< E> implements NavigableSet< E>, Cloneable, java.io.Serializable。

内部维护private transient NavigableMap< E,Object> m，map是key-value的，set的数据是map的key，因此创建一个private static final Object PRESENT = new Object()作为value。

默认使用new TreeMap< E,Object>()实现NavigableMap。

非线程安全。

[JAVA_1]: http://blog.csdn.net/weitry/article/details/52965546
[JAVA_2]: http://blog.csdn.net/weitry/article/details/53292723
[JAVA_3_1]: http://blog.csdn.net/weitry/article/details/52953113
[JAVA_4_2]: http://blog.csdn.net/weitry/article/details/52964428
[JAVA_9_3]: http://blog.csdn.net/weitry/article/details/52964509
[JAVA_10_IO_NIO]: http://blog.csdn.net/weitry/article/details/52964948
[JAVA_11]: http://blog.csdn.net/weitry/article/details/52964599
[JAVA_12]: http://blog.csdn.net/weitry/article/details/52936835
[JAVA_13]: http://blog.csdn.net/weitry/article/details/53292825