2018-01-27
这一天是周二，我们下午开始了课程。
Java中两个关键数据结构
主要分为 Collection
和 Map 两个主要接口（接口只提供方法，并不提供实现），而程序中最终使用的数据结构是继承自这些接口的数据结构类
Collection的特点
•Collection接口并不是一个根接口，它的超级接口是Iterator，需要提供其遍历、移除元素(可选操作)的能力。
•Collection接口定义了基本的容器操作方法。
•remove()和contains()判断元素是否相等的依据是类似的。
–对于remove(Objecto)，若Collection中包含的元素e，满足(o==null?
e==null : o.equals(e))，移除其中的一个；
–对于contains(Objecto)，若Collection中包含至少一个或多个元素e，满足(o==null
? e==null : o.equals(e))，则返回true。
•AbstractCollection抽象类实现了一部分Collection接口的方法，主要是基于iterator实现的，如remove()、toArray()，以及利用本身的属性size实现的size()。如果读一下源码，可以发现虽然AbstractCollection利用add()实现了addAll()，但是add()本身的实现是直接抛UnsupportedOperationException异常的。实际上add()是一种“可选操作”，目的是延迟到需要时再实现。
List
List中的元素是有序的，因而我们可以按序访问List中的元素，以及访问指定位置上的元素。对于“按顺序遍历访问元素”的需求，使用List的超级接口Iterator即可以做到，这也是对应抽象类AbstractList中的实现；而访问特定位置的元素（也即按索引访问）、元素的增加和删除涉及到了List中各个元素的连接关系，并没有在AbstractList中提供。
ArrayList
•ArrayList是最常用的List的实现，可以简单的认为是一个动态数组；实际上ArrayList就是用数组实现的，长度不够时，调用Arrays.copyOf方法，拷贝当前数组到一个新的长度更大的数组
•特点：
–随机访问速度快，插入和移除性能较差(数组的特点)；
–支持null元素；
–有顺序；
–元素可以重复；
–线程不安全；
Vector和Stack(不建议继续使用)
•Vector：线程安全的动态数组
•Stack：继承Vector，基于动态数组实现的一个线程安全的栈；
•Vector与ArrayList基本是一致的，不同的是Vector是线程安全的，会在可能出现线程安全的方法前面加上synchronized关键字；
•Vector：随机访问速度快，插入和移除性能较差(数组的特点)；支持null元素；有顺序；元素可以重复；线程安全；
•Stack：后进先出，实现了一些栈基本操作的方法（其实并不是只能后进先出，因为继承自Vector，可以有很多操作，从某种意义上来讲，不是一个栈）；
•如果要使用栈行为，应该使用LinkedList。
Set
Set接口模仿了数学概念上的set，各个元素不要求重复。除了这一点，几乎和Collection本身是一样的。
Set接口有一个直接子接口SortedSet，该接口要求Set中所有元素有序。和通过Iterable接口依次访问所有元素的“有序”不同，这个“有序”要求Set包括一个比较器，可以判断两个元素的大于、小于或等于关系。此外，该接口提供了访问第一个元素、访问最后一个元素、访问一定范围内元素的方法。SortedSet的子接口NavigableSet进一步扩展了这个系列的方法，提供了诸如返回大于/小于元素E的第一个元素的方法HashSet、LinkedHashSet和TreeSet
•Set接口的实现类，最大特点是不允许出现重复元素；
•HashSet：基于HashMap实现，一个性能相对较好的Set；
•LinkedHashSet：基于LinkedHashMap实现，一个保存了插入顺序的Set；
•TreeSet；基于TreeSet实现，一个实现了排序的Set；
讲完了课程之后我们又有了一个作业