Java Collection框架

Java Collection框架,List 列表、Queue 队列、Deque 双端队列、Set 集合、Map 映射

集合框架

Java 集合框架中主要封装的是典型的数据结构算法,如动态数组、双向链表、队列、栈、Set、Map 等;
Java 的 Collection 框架和 C++ 的标准模板库(STL)是相似的东西,集合框架极大的方便了 Java 程序的编写。

Collection 框架主要位于 java.util 包,类继承结构:
Java8 Collection 框架,类结构图

主要分为以下几个部分:
1) 数据结构
List列表、Queue队列、Deque双端队列、Set集合、Map映射
2) 算法
Collections常用算法类、Arrays静态数组的排序、查找算法
3) 迭代器
Iterator通用迭代器、ListIterator针对 List 特化的迭代器
4) 比较器
Comparator比较器

简要分析
1) List 主要实现类:ArrayList、LinkedList
ArrayList:”动态数组”,支持随机存取,尾部插入删除方便,内部插入删除效率低(因为要移动数组元素);如果内部数组容量不足则自动扩容,因此当数组很大时,效率较低;
LinkedList:”双向链表”,在任意位置插入删除都很方便,但是不支持随机存取,每次都只能从一端开始遍历,不过,它不像 ArrayList 那样需要进行内存拷贝,因此相对来说效率较高,但是因为存在额外的前驱和后继节点指针,因此占用的内存比 ArrayList 多一些。

2) Queue 主要实现类:ArrayDeque、LinkedList、PriorityQueue
ArrayDeque:基于数组实现的双端队列,“循环数组”,可作为 Stack 栈使用;
LinkedList:基于双向链表实现的双端队列,可以作为 Stack 栈使用;
PriorityQueue:“最小堆”,“完全二叉树”,优先级队列,使用数组保存了完全二叉树。

3) Deque 主要实现类:ArrayDeque、LinkedList
ArrayDeque:基于数组实现的双端队列,“循环数组”,可作为 Stack 栈使用;
LinkedList:基于双向链表实现的双端队列,可以作为 Stack 栈使用。

4) Set 主要实现类:HashSet、LinkedHashSet、TreeSet、EnumSet(RegularEnumSet、JumboEnumSet)
HashSet:基于 HashMap 实现,元素不可重复,特性同 HashMap;
LinkedHashSet:基于 LinkedHashMap 实现,元素不可重复,特性同 LinkedHashMap;
TreeSet:基于 TreeMap 实现,元素不可重复,特性同 TreeMap;
RegularEnumSet:枚举专用的 Set 集合,由 EnumSet 调用,因为该类的权限为 [default],元素必须为枚举类型,与其他 Set 实现不同,其内部使用位向量实现,拥有极高的时间和空间性能;
JumboEnumSet:枚举专用的 Set 集合,由 EnumSet 调用,因为该类的权限为 [default],元素必须为枚举类型,与其他 Set 实现不同,其内部使用位向量实现,拥有极高的时间和空间性能。

5) Map 主要实现类:HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、EnumMap
HashMap:key 不可重复,使用 equals 判断,根据 key 的 hashCode 存储数据,具有很快的访问速度,记录的遍历顺序与记录的输入顺序基本不一致;最多只允许一条记录的 key 为 null;
LinkedHashMap:key 不可重复,使用 equals 判断,HashMap 的子类,内部使用双向链表保存了记录的插入顺序,使得输入的记录顺序和输出的记录顺序是相同的;
TreeMap:key 不可重复,使用 equals 判断,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用 Iterator 遍历时,得到的记录是排过序的;如需使用排序的映射,建议使用 TreeMap;
IdentityHashMap:key 不可重复,使用 == 判断,比较内存地址,可以说是某种意义上的可重复 key 的映射;
WeakHashMap:弱引用 Map,特别适合用于需要缓存的场景,WeakHashMap 中的 Entry 可能随时被 GC 回收;
EnumMap:枚举专用的 Map 映射,其 key 必须为某种枚举类型的枚举常量,内部通过数组实现,因此效率比一般的 Map 高。

主要接口

Iterable 接口

Iterable,”可迭代的”,如果一个集合类实现了该接口,那么表示这个集合类可进行迭代操作,比如 JDK1.5 提供的 foreach 循环。

Collection 框架主要有两大接口:Collection、Map,其中 Collection 接口继承了 Iterable 接口,因此所有实现了 Collection 接口的类都是可迭代的,可用于类似 foreach 操作;Map 虽然没有直接实现 Iterable 接口,但是它提供了对应的 Collection 视图,因此也能进行类似的迭代操作。

Iterable 接口位于 java.lang 包,其主要方法为 iterator(),用来获取当前集合对象的一个迭代器 Iterator。

Iterator 接口

前面说了 Iterable 可迭代对象,它的主要方法就是 iterator(),获取可迭代对象的迭代器;而迭代器就是 Iterator,这个接口位于 java.util 包,一般来说每个集合类都有自己的特定迭代器实现,一般是一个内部类。

Iterator 接口有两个主要方法:hasNext()、next(),通常这两个方法需要配合使用:
hasNext() 方法,判断当前集合对象是否还有下一个可操作元素,如果有则返回 true,通常用于 for、while 条件;
next() 方法,获取当前集合对象的下一个可操作元素,与此同时,迭代器将向后推进一个元素单位,指向下一个位置。

Collection 接口

java.util.Collection 接口是 Java Collection 框架的两大主要接口之一,有三个主要子接口 List、Queue、Set;
因为 Collection 接口是 java.lang.Iterable 的子接口,因此 List、Queue、Deque、Set 都可以用于 foreach 循环。

Comparable 接口

java.lang.Comparable,可比较的,对象的属性;
java.util.Comparator,比较器,比较对象的工具。

它们的区别就如同 Iterable、Iterator 之间的区别:

  • 如果一个类实现了 Comparable 接口,表示这个类的对象之间支持比较操作,可直接用于自然排序(一般为升序);
  • 如果一个类没有实现 Comparable 接口,但是它有专门的 Comparator 比较器,那么也可用于排序,定制性更高一些。

Comparable 接口,如果一个类实现了此接口,则说明它的对象支持自然排序

Comparator 接口

java.util.Comparator 函数式接口,主要方法为int compare(T o1, T o2)

候选比较器例子:

Cloneable 接口

java.lang.Cloneable 接口和 java.io.Serializable 接口都是”标记接口”,没有任何方法签名。
稍微研究一下 Collection 框架的源码就可以发现,它们几乎都实现了 Cloneable、Serializable 接口。

Cloneable 接口:如果一个类实现了该接口,表示这个类的对象支持 clone() 操作,即对象是可克隆的;
Serializable 接口:如果一个类实现了该接口,表示这个类支持 readObject()/writeObject() 序列化操作。

在 Object 类中,有一个 protected 的 clone() 方法,并且是一个 native 方法:
protected native Object clone() throws CloneNotSupportedException;
默认情况下,我们不能直接调用一个对象的 clone() 方法,因为它被 protected 所修饰。

那么我们先把它给重写,并且把其访问性改为 public 试试:

编译没有问题,但运行时抛出异常 CloneNotSupportedException,不支持 clone 操作;
这是因为我们没有实现 Cloneable 接口,就和 Serializable 序列化一样,会进行类型检查。

可以了,先提前说一下,这种直接调用 Object.clone() 方法的克隆方式称为”浅拷贝”;我们来看一下它的局限性:

对于值类型 int、float,没有所谓的深拷贝浅拷贝之分,因为它就是一个简简单单的数值;
对于引用类型(数组也是引用类型),默认的浅拷贝只会拷贝它的引用,也就是内存地址。

这样的话两个对象之间修改就会互相影响,很显然不是我们想要的理想结果;
我们既然通过 clone 创建新对象,目的就是为了它们之间的修改不会对对方产生影响。

那么如何做到”深拷贝”呢,其实也很简单,只要把每个引用对象都拷贝就行了,如下:

目前看来好像达到了我们的”深拷贝”目的,但是,有个问题,如果有的数据成员没有实现 Cloneable 接口怎么办;
如果是我们自己的类还好说,进行简单的修改就好了,但是如果是其它的呢,比如 Java API,我们是不可能去修改的。

其实还有一种办法,可以做到完美的”深拷贝”,那就是 java.io.Serializable 接口,对的,通过序列化来进行深拷贝。如果你还不了解对象序列化,请猛戳 Serializable - 对象序列化与反序列化

特别的,如果序列化对象的成员变量为引用类型,并且它不属于 String、Array、Enum,Serializable 类型,那么在执行序列化的过程中,将会抛出运行时异常 NotSerializableException。因此对于这些引用类型的成员变量,有三种选择:
1) 使用 transient 关键字声明该成员,在序列化时跳过该成员变量,在反序列化之后自动赋值 null;
2) 如果该引用类型是你自己创建的类,那么可以直接让其实现 java.io.Serializable 接口;
3) 创建一个派生类,这个派生类没有任何声明的方法和属性,仅仅用于序列化和反序列化。

其中第一、二种方式并不是我们想要的,我们来实现第三种方式:

通过这种方式虽然可以完美解决 Object.clone()”深拷贝”问题,但是相对来说效率还是比较低下的,毕竟存在多次内存拷贝。

List 列表

List 接口

ListIterator 接口

java.util.ListIterator 是 Iterator 的一个子接口,是专门用于 List 列表的迭代器。

逆向迭代的例子:

ArrayList 类

java.util.ArrayList 实现了 List 接口,内部使用 Object[] 数组存储元素,允许 null 元素,数组容量不足时自动增长。它与大多数集合类一样,是非线程安全的,如果需要进行额外的同步,可以考虑 Collections 的<T> List<T> synchronizedList(List<T> list)静态方法进行包装;如果是读多写少,请考虑使用 java.util.concurrent.CopyOnWriteArrayList。

LinkedList 类

java.util.LinkedList 实现了 List 和 Deque 接口,内部使用双向链表实现,允许 null 元素,在遍历链表时,可能从头结点或尾结点开始,以近的为准。它与大多数集合类一样,是非线程安全的,如果需要额外的同步,可以考虑 Collections 的<T> List<T> synchronizedList(List<T> list)静态方法进行包装,如果是读多写少的应用场景,可以考虑使用写时复制容器 java.util.concurrent.CopyOnWriteArrayList。

Queue 队列

Queue 接口

java.util.Queue 队列,遵循 FIFO 先进先出原则,在队尾插入元素叫做入队,在队头弹出元素叫做出队。

Deque 接口

java.util.Deque 双端队列,是具有队列性质的一种数据结构。Deque 是 Queue 的子接口,主要有两个实现类:ArrayDeque、LinkedList。

ArrayDeque 类

java.util.ArrayDeque 是 java.util.Deque 的一个实现类,内部使用数组(循环数组)存储元素,容量不足会自动增长,ArrayDeque 不允许 null 元素。它与大多数集合类一样,是非线程安全的,如果需要支持并发的 FIFO 队列,请使用 java.util.concurrent.ConcurrentLinkedDeque。ArrayDeque 在作为 stack 栈使用时,它可能比 Stack 更快;ArrayDeque 在作为 queue 队列使用时,它可能比 LinkedList 更快。

PriorityQueue 类

java.util.PriorityQueue 优先队列,优先队列的元素根据其自然顺序(Comparable)或者使用提供的比较器(Comparator)来排序,无论是哪种方式,PriorityQueue 都不允许 null 元素。而依据自然排序的优先级队列也不允许插入不可比较对象,这将导致 ClassNotFoundException。优先级队列的对头元素是权值最小的元素(即由比较器决定的最小的元素),而内部存储元素的数组也会在容量不足时自动增长。它与大多数集合类一样,是非线程安全的,如果需要额外的同步,请考虑使用优先级阻塞队列 java.util.concurrent.PriorityBlockingQueue。

例子:

Map 映射

Map 接口

SortedMap 接口

java.util.SortedMap 是 Map 的子接口,它定义了一个有序的映射。插入的元素要么实现了 java.lang.Comparable 接口,而支持自然排序,要么在构造时提供一个 java.util.Comparator 比较器,而支持自定义排序;如果都不符合,则抛出 ClassCastException 异常。同时,keySet()、values()、entrySet() 方法返回的视图也是一个有序的 Map。

java.util.NavigableMap 是 SortedMap 的子接口,它定义了一个可导航的映射。所谓的导航方法就是定位方法,比如查找小于、小于等于、大于等于、大于给定 key 的一个 key。但是请注意,这些导航方法都是为了定位而设计的,而不是为了遍历 Entry。

HashMap 类

HashMap 允许 null 键、null 值不保证遍历的顺序与插入的顺序是一样的,也不保证遍历的顺序可以永恒不变(自动扩容的原因)。HashMap 是数组链表的结合体,HashMap 底层是一个Entry[]数组,该数组可以自动扩容;Entry[] 数组的每个元素都是一个链表,Entry 有一个 next 指针指向下一个 Node 节点。因为 HashMap 使用 hash() 哈希函数计算 key-value 键值对的索引值,因此它同时具有数组和链表的优点:查找,插入/删除都具有很高的性能。它与大多数集合类一样,是非线程安全的,如果需要额外的同步,请考虑使用并发 HashMap:java.util.concurrent.ConcurrentHashMap。HashMap 的数据结构如下图所示:
HashMap 数据结构

LinkedHashMap 类

LinkedHashMap 是 HashMap 的子类,底层还是使用的 HashMap,没有变化;不同的是,LinkedHashMap 可以按照插入顺序进行遍历,也可以根据访问顺序进行遍历。
可以保存顺序的原理就是它除了使用哈希表保存键值对之外,还在内部维护了一个运行时双向链表;当按照访问顺序进行排序时,LinkedHashMap 会将最近访问的键值对移动到链表的尾部

LinkedHashMap 例子:

TreeMap 类

java.util.TreeMap 实现了 NavigableMap 接口,因此它支持一系列的导航方法。TreeMap 内部使用红黑树(Red-Black tree)实现,它为 containsKey()、get()、put() 和 remove() 操作提供了 log(n) 的时间复杂度。TreeMap 的 key 根据其自然顺序(Comparable)或者使用提供的比较器(Comparator)来排序,这取决于它的构造函数。但是依据自然排序的 TreeMap 不允许插入不可比较对象,这将导致 ClassNotFoundException 异常。TreeMap 允许 null 值,如果是使用自然排序,则不允许 null 键,如果是使用自定义排序,是否允许 null 键将取决于传入的比较器,如果该比较器允许 null 参数,则该 Map 也支持,否则将导致 NullPointerException 异常。它与大多数集合类一样,是非线程安全的,如果需要额外的同步,可以考虑使用 Collections 的<K, V> NavigableMap<K, V> synchronizedNavigableMap(NavigableMap<K, V> m)静态包装方法,或者使用并发的 TreeMap:java.util.concurrent.ConcurrentSkipListMap。

例子:

IdentityHashMap 类

java.util.IdentityHashMap 与 HashMap 在数据结构上没有太大的差别。不同的是,HashMap 使用k1 == null ? k2 == null : k1.equals(k2)判断两个 key 是否”相等”,而 IdentityHashMap 则使用k1 == k2判断两个 key 是否”相等”。并且,HashMap 使用 key.hashCode() 来查找存储桶,而 IdentityHashMap 则使用 System.identityHashCode(key) 来查找存储桶。还有,HashMap 使用拉链法解决哈希冲突,而 IdentityHashMap 则使用线性探测法解决哈希冲突。此类的典型用途:序列化深度拷贝维护代理对象。IdentityHashMap 和 HashMap 一样,允许 null 键、null 值,并且不保证 entry 的遍历顺序与输入顺序一致,更不保证该顺序会一直不变(自动扩容的原因)。它与大多数集合类一样,是非线程安全的,如果需要额外的同步,请考虑使用 Collections 的<K, V> Map<K, V> synchronizedMap(Map<K, V> m)静态包装方法。

例子:

Integer 自动装箱并非每次都是 new 一个新的 Integer 对象,自动装箱调用 Integer.valueOf() 方法;valueOf() 首先检查 int 是否在区间 [-128, 127],如果是则返回已存在的 Integer 对象(如果有的话),否则 new 一个新的对象。

WeakHashMap 类

java.util.WeakHashMap 与 HashMap 具有类似的性能特征,并且具有相同的初始容量和负载因子的效率参数,并且 WeakHashMap 也允许 null 键、null 值。它们之间最大的不同是,WeakHashMap 的 key 是弱键,即弱引用对象,如果 GC 线程发现一个对象只存在弱引用,则该对象随时都会被回收。

为了明白 WeakHashMap 的特性,必须先了解 Java 的四种引用类型:
1) 强引用(StrongReference)
一般情况下我们使用的都是强引用,如Test t = new Test()的 t 就是一个强引用

当内存不足,JVM 宁愿抛出 OutOfMemoryError 错误,使程序异常终止,也不会回收强引用对象来释放内存

2) 软引用(SoftReference)

如果一个对象只有软引用,则内存空间足够,GC 就不会回收它;如果内存空间不足了,就会回收这些对象的内存

3) 弱引用(WeakReference)

只具有弱引用的对象拥有更短暂的生命周期;在 GC 线程扫描它所管辖的内存区域的过程中,一旦发现了只具有弱引用的对象,不管当前内存空间足够与否,都会回收它的内存

4) 虚引用(PhantomReference)

虚引用主要用来跟踪对象被垃圾回收器回收的活动,虚引用必须和引用队列(ReferenceQueue)联合使用

“虚引用”顾名思义,就是形同虚设,与其他几种引用都不同,虚引用并不会决定对象的生命周期;如果一个对象仅持有虚引用,那么它就和没有任何引用一样,在任何时候都可能被垃圾回收器回收。当垃圾回收器准备回收一个对象时,如果发现它还有虚引用,就会在回收对象的内存之前,把这个虚引用加入到与之关联的引用队列中。

除了强引用之外,其他三种引用都在 java.lang.ref 包中。

这里解释一下引用队列(ReferenceQueue)

如果我们在创建一个引用对象时,指定了 ReferenceQueue,那么当引用对象指向的对象达到合适的状态(根据引用类型不同而不同)时,GC 会把引用对象本身添加到这个队列中,方便我们处理它;因为引用对象指向的对象 GC 会自动清理,但是引用对象本身也是对象(是对象就占用一定资源),所以需要我们自己清理。

举个例子:SoftReference<String> ss = new SoftReference<String>("abc", queue)
其中,ss 是一个引用对象(一个普通的对象,本身是强引用),指向"abc"对象(该对象只有一个软引用 ss 指向它);"abc"对象会在一定时机被 GC 自动清理,但是 ss 对象本身的清理工作依赖于 queue,当 ss 出现在 queue 中时,说明其指向的对象已经无效,可以放心清理 ss 了。

引用对象的四种状态
每一时刻,Reference 对象都处于下面四种状态中:
1) Active:”活动状态”,新创建的引用对象都是这个状态,GC 会根据引用对象是否在创建时指定 ReferenceQueue 参数进行状态转移,如果指定了,那么转移到 Pending 状态,如果没指定,转移到 Inactive 状态;
2) Pending:”待定状态”,该状态的引用对象等着被内部线程 ReferenceHandler 处理(会调用 ReferenceQueue.enqueue 方法)
3) Enqueued:”入队状态”,调用 ReferenceQueue.enqueued 方法后的引用对象处于这个状态中;
4) Inactive:”死亡状态”,处于该状态的引用对象将被 GC 自动清理。
java.lang.ref 引用对象的四种状态

总之,我们目前只需要知道以下两点就可以了:

如果构造函数中指定了 ReferenceQueue,那么引用对象需手动进行清理;
如果构造函数中没有指定 ReferenceQueue,那么 GC 会自动清理引用对象。

软引用、弱引用的应用场景
软引用/弱引用都可用来实现内存敏感的高速缓存;通常和引用队列联合使用,如果引用对象所引用的对象被 GC 回收,Java 虚拟机就会把这个引用对象加入到与之关联的引用队列中,方便我们进行后需清理工作。

它们的区别是:软引用的生命周期比弱引用的生命周期更长一些,因为软引用只有在内存不足时才会进行垃圾回收,而弱引用随时都可能被 GC 回收。

WeakHashMap 和 HashMap 最主要的区别就在于 Entry 类,WeakHashMap 的 Entry 是 java.lang.ref.WeakReference 的子类,内部将 key 作为弱引用对象。

主要方法

EnumMap 类

java.util.EnumMap 是枚举类型 key 专用的 Map,EnumMap 中的 key 必须来自同一个 Enum 枚举类,不允许 null 键,允许 null 值,但测试是否存在 null 键或者移除 null 键会正常工作。因为枚举常量的 ordinal() 值是不变的,所以 EnumMap 直接使用了 Object[] 数组来存储 values,而 key 根本不需要存储,key 可以根据传入的枚举类的 Class 对象获取。因为在内部是使用数组实现的,因此 EnumMap 的效率比普通的 Map 高。它与大多数集合类一样,是非线程安全的,如果需要额外的同步,请使用 Collections 的<K, V> Map<K, V> synchronizedMap(Map<K, V> m)静态包装方法。

Set 集合

HashSet、LinkedHashSet、TreeSet 都是其对应 Map 的一个包装类;它们底层都是使用对应的 Map 存储元素,因此相关特性也和底层容器一样。在 Set 中的”元素”其实就是 Map 中的 key,而 value 部分则使用一个static final Object PRESENT = new Object()占位。

Set 接口

SortedSet 接口

HashSet 类

java.util.HashSet 实现了 Set 接口,内部使用 HashMap 作为存储容器,因此,HashSet 也允许 null 元素。

LinkedHashSet 类

java.util.LinkedHashSet 实现了 Set 接口,是 HashSet 的子类,它依旧使用 LinkedHashMap 作为存储容器。LinkedHashSet 与 HashSet 的区别是,LinkedHashSet 会记录元素的插入顺序,其原理是额外的维护了一个双向链表,因此相比 HashSet 有一定的性能损失。

TreeSet 类

java.util.TreeSet 实现了 NavigableSet 接口,这意味着它支持一系列的导航方法,在内部,它也是使用 TreeMap 作为存储容器的。如果此 TreeSet 是自然排序的,则不允许 null 元素,如果此 TreeSet 是自定义排序的,并且传入的比较器允许 null 参数,则此 TreeSet 支持 null 元素,否则将抛出 NullPointerException 异常。

EnumSet 抽象类

java.util.EnumSet 是枚举类型的专用集合,该集合中的元素必须都来自同一个枚举类,EnumSet 不允许 null 元素,但测试是否存在 null 元素或移除 null 元素会正常工作。EnumSet 并不是使用 EnumMap 存储元素的,而是使用了更加高效的实现 - 位向量,它是一种极为高效的位运算操作,由于直接存储和操作都是 bit,因此 EnumSet 空间和时间性能都十分可观,足以媲美传统上基于 int 的“位标志”的运算。EnumSet 返回的迭代器是有序的,它根据枚举常量的 ordinal() 进行自然排序。EnumSet 是抽象类,它有两个实现类(实现类的访问权限是包权限,因此无法在外部直接访问):RegularEnumSet、JumboEnumSet。EnumSet 抽象类提供了几个静态方法,用于创建这两个实现类的对象,具体使用谁由 EnumSet 内部决定。

Collections

java.util.Collections 类是 Java 集合框架的一员,它提供了很多 static 方法服务于各集合对象;
比如:对集合元素的排序、取极值、批量拷贝、集合结构转换、循环移位以及匹配性检查等功能。

因为 Collections 类的构造方法被声明为 private,因此无法进行对象的实例化。

Collection 总结

对于集合框架,仅仅学习怎么用是不够的,我们更应该学习它们的原理,毕竟数据结构与算法是逃避不了的。先抛开树(红黑树、AVL 树等)不说,线性表(顺序表、单链表、双链表)、队列、栈、数组查找、数组排序,这些最基本的是必须要会的!

本节内容的所有源码(GitHub 仓库):Java Collection 框架的简单实现

List 接口

“列表”,三个实现类:ArrayList(数组)、SLinkedList(单向链表)、DLinkedList(双向链表)

ArrayList 类

“动态数组”,随机访问性能好,尾部插入删除方便,其它位置插入删除要移动元素,效率不高

SLinkedList 类

“单向链表”,插入删除性能好,随机访问性能差,因为存在额外的指针域,因此占有的内存多一些

DLinkedList 类

“双向链表”,插入删除性能好,随机访问性能差,因为存在额外的指针域,因此占有的内存多一些

Queue 接口

“队列”,FIFO(先进先出),实现类:ArrayQueue、SLinkedQueue、DLinkedQueue

ArrayQueue 类

“动态数组”

SLinkedQueue 类

“单向链表”

DLinkedQueue 类

“双向链表”

Stack 接口

“栈”,LIFO(后进先出),实现类:ArrayStack、SLinkedStack、DLinkedStack

ArrayStack 类

“动态数组”

SLinkedStack 类

“单向链表”

DLinkedStack 类

“双向链表”

Set 接口

“集合”,保证元素的唯一性(hashCode()、equals() 方法判定)

HashSet 类

普通的哈希表,遍历的顺序不保证为插入的顺序,并且该顺序也不保证永恒不变(自动扩容)

LinkedHashSet 类

与 HashSet 不同的是,它可以维护元素的插入顺序,并且支持按照访问顺序动态的排列

Map 接口

“映射”,保证 key 的唯一性(hashCode()、equals() 方法判定)

HashMap 类

普通的哈希表,遍历的顺序不保证为插入的顺序,并且该顺序也不保证永恒不变(自动扩容)

LinkedHashMap 类

与 HashMap 不同的是,它可以维护 entry 的插入顺序,并且支持按照访问顺序动态的排列

BinaryTree 类

二叉树的相关遍历方法:先序遍历、中序遍历、后序遍历、层次遍历

ArrayAlgorithm 类

数组的相关算法:数组查找、数组排序、数组洗牌、数组翻转