JavaSE—合集框架（新），javase合集框架

JavaSE—合集框架（新），javase合集框架

一、什么是合集？

答：Java的合集框架支持以下两种类型的容器：

       一种是为了存储一个元素合集，简称为合集（collection）；

       另一种是为了存储键值对，称为映射表（map），映射表使用一个键，快速搜索其对应的值，非常高效；

 

二、合集包含哪些内容？

答：Set用于存储一组不允许重复，无序的元素合集；

       List用于存储允许重复，有序（指的是顺序存储元素）的元素合集；

       Stack（栈类）用于存储采用先进后出的方式处理的对象；

       Queue（队列）用于存储采用先进先出的方式处理的对象；

       Priority Queue用于存储按照优先级顺序处理的对象；

 

三、合集框架的结构

答：以上的合集均是在接口中定义通用特性，之后由对应的抽象类来实现这些接口并提供部分实现，最后再由对应的子类用具体的数据结构实现接口；

 

四、Collection和Collections的区别

答：这里有一个基本的概念非常容易混淆：

       Collection是位于 java.util 下的接口，处理对象合集的根接口，也就是所有合集框架的父接口；

       Collections是 java.util 下的一个类，它包含各种有关合集操作的静态方法；

 

五、合集根接口—Collection

答：Collection接口是处理对象合集的根接口，除了add，size，iterator方法之外（这些方法会在合适的子类中实现0），Abstract-Collection类实现了该接口中的所有方法；

注意： 

list1.retainAll(list2);
//执行上述命令后，list1中只会剩下list1和list2都有的元素

 

六、合集Cloneable接口和Serializable接口的支持

答：除了java.lang.PriorityQueue没有实现Cloneable接口外，合集框架中的其他所有具体类都实现了java.lang.Cloneable和java.lang.Serializable接口，所以除了优先队列外，所有的Cloneable的实例都是可克隆和序列化的；

 

七、迭代器和listIterator

public class Demo {
	public static void main(String[] args) {
		// 此处不能用Collection接口来声明集合，因为listIterator方法是List接口中的方法
		List<String> list = new ArrayList<>();
		list.add("公子羽");
		list.add("明月心");
		list.add("百晓生");
		list.add("叶孤城");
		// 正向迭代器
		Iterator<String> iterator = list.iterator();
		while (iterator.hasNext()) {
			System.out.print(iterator.next() + "\t");
		}
 
		System.out.println();
		/**
		 * 反向迭代器，此处必须给定迭代器开始迭代的位置，也就是将光标移到开始迭代的元素处 
		 * 下一个元素的索引为即将输出的元素的索引
		 * 上一个元素的索引为即将输出的元素的前一个元素的索引
                 * 虽然可以使用get(i)方法进行遍历，但由于效率低下，并不推荐
                 * foreach循环底层也是隐式的运用了iterator
		 */
		ListIterator<String> listIterator = list.listIterator(list.size());
		while (listIterator.hasPrevious()) {
			System.out.println("下一个元素的索引：" + listIterator.nextIndex());
			System.out.println("上一个元素的索引" + listIterator.previousIndex());
			System.out.println(listIterator.previous() + "\t");
		}

	}
}

注意：

        hasNext方法用于向前遍历是确认是否还有下一个元素，hasPrevious方法用于向后遍历时确认是否还有上一个元素；

        next方法返回的是迭代器中的下一个元素，previous方法返回的是迭代器中的前一个元素；

        nextIndex用于返回下一个元素的下标，previousIndex用于返回上一个元素的下标；

listIterator中包含的方法：

 

八、线性表接口—List

答：1、List接口实现了Collection接口，它的两个具体子类：数组线性表ArrayList 和 链表类LinkedList 来创建一个线性表（list）；

        2、List接口增加了面向位置的操作，并且增加了一个能够双向遍历线性表的新线性表迭代器（参考迭代器中的例子）；

 

九、数组（顺序）线性表—ArrayList类

答：ArrayList类底层使用数组存储元素，这个数组是动态创建的，大小是可变的，如果元素的数量超过了数组的容量，就创建一个更多的数组，并将当前数组中的所有元素都复制到新数组中；

 

十、链表线性表—LinkedList类

答：ArrayList对数组进行了封装，实现了长度可变的数组，它的优点在于遍历和随机访问元素的效率比较高；

       LinkedList采用链表存储方式，优点在于插入、删除时效率比较高；

       LinkedList除了List接口中定义的方法之外，还提供了从线性表两端提取、插入、删除元素的方法

 

十一、向量类—Vector类

答：Vector和ArrayList都是AbstractList的子类，Vector是栈类Stack的父类，除了包含访问和修改向量的同步方法之外，Vector和ArrayList是一样的。同步方法用于防止两个或多个线程同时访问和修改某个向量时引起数据的损坏。

对于不需要同步的应用程序来说，使用ArrayList比使用Vector效率更高。

Vector也属于线性表，并且它实现的数组是一个动态数组。

Vector类有如下四个构造方法：

//默认向量，默认大小为10
Vector<Object> v = new Vector<>();
//创建指定大小的向量
Vector<Object> v = new Vector<>(int size);
//创建指定大小和增量的向量
Vector<Object> v = new Vector<>(int size，int incr);
//创建一个包含集合c的向量
Vector<Object> v = new Vector<>(Collection c);

具体类中的方法不再赘述，可自行查阅。

 

十二、队列—Queue接口

答：队列是一种先进先出的数据结构，元素被追加到队列末尾，然后从队列头开始删除。

Queue继承自Collection，方法如下：

 

十三、双端队列Deque和链表LinkedList

答：LinkedList实现了Deque接口，Deque接口继承自Queue接口，因此可以用LinkedList创建一个队列。

LinkedList很适合用于进行队列操作，因为它可以高效的在线性表的两端插入和删除元素。

 

十四、优先队列—PriorityQueue类

答：PriorityQueue实现了一个优先队列，默认情况下，优先队列使用Comparable以元素的自然顺序进行排序，用小最小数值的元素拥有最高的优先级，最先被从队列中删除，如果优先级一样，则任意选一个，也可以在构造方法中指定一个比较器，然后按照比较器顺序进行排序后，以比较器的顺序删除队列。

 

十五、Set接口

答：实现Set的具体类必须确保不能向这个集合添加重复的元素。

Set接口的三个具体类是：散列类HashSet，链式散列集LinkedHashSet，和树形集TreeSet。

因为在Set集合中存储的对象是无序且唯一的，所以所有的需要索引的方法，Set集合都没有。

如果不需要维护元素的顺序，那么HashSet将是效率最高的。

 

十六、散列类—HashSet

答：HashSet类是一个实现了Set接口的具体类，有以下三个构造方法：

//默认构造方法，初始容量为16，负载系数0.75f
HashSet<Object> a=new HashSet<>();
//以集合c创建散列集
HashSet<Object> a=new HashSet<>(Collection c);
//指定容量，负载系数默认0.75f
HashSet<Object> a=new HashSet<>(int size);
//指定容量和负载系数，负载系数范围0~1.0f
HashSet<Object> a=new HashSet<>(int size,float loadFactor);

当元素个数超过了容量与负载系数的乘积，容量会自动翻倍扩容。

比较高的负载系数会降低空间开销，但会增加查找时间，而默认的0.75f的负载系数是对时间开销和空间开销一个很好的权衡。

HashSet中存储的元素，不会按照他们存储的顺序进行存储，如果要强加给他们一个顺序，请使用LinkedHashSet

 

十七、链式散列集LinkedHashSet

答：LinkedHashSet是HashSet的子类，是用一个链表实现来拓展HashSet，它支持对集合内的所有元素按照插入集合的顺序排序。

LinkedHashSet的构造方法类似与HashSet。

LinkedHashSet保持了元素插入集合的顺序，如果要强加一个不同的顺序（例如升序或降序），可以参照TreeSet。

 

十八、树形集TreeSet

答：SortedSet是Set的一个子接口，TreeSet类实现了这个接口，它可以保证集合中的元素是有序的。

SortedSet接口提供了方法first和last以返回集合中第一个和最后一个元素，还有方法headSet（toElement）和tailSet（fromElement）以分别返回集合中元素小于toElement和大于或等于fromElement的那一部分。

NavigableSet拓展了SortSet，并提供了导航方法lower，floor，ceiling和higher分别以返回小于，小于或等于，大于或等于，以及大于一个给定元素的元素。方法pollFirst和pollLast会分别删除并返回树形集的第一个和最后一个元素。

如果要给元素进行制定排序方式，需要实现Comparable或者Comparator接口。

可以让需要排序的类实现Comparable接口，之后重写其中的compareTo方法，来为TreeSet集合制定排序方式。

或者可以单独创建一个类实现Comparator接口，重写compare方法，让该类来作为比较器，如果是这种方式的话，创建TreeSet集合必须使用如下方式：

//new CompareObject为比较器类
Set<Object> set=new TreeSet<>(new CompareObject);

 

十九、映射表

答：可以使用三个具体的类来创建一个映射表：三列映射表HashMap，链式散列映射表LinkedHashMap，树形映射表TreeMap。

映射表是一对利用键/值对存储元素的容器，它提供了通过键快速获取，删除或更新键值对的功能。

映射表中的键可以是任意类型的对象，并且键是不能够重复的，每个键都对应一个值。

Map接口提供了查询、更新和获取合集的值和合集的键的方法，如下图所示：

注意：

当使用put方法在映射表中添加新的条目时，如果原先就已经存在了一个同名的键的键值对条目，那么该条目的值会被put方法中传入的新值所替代，并且返回与这个键相关联的原来的值。

方法entrySet返回该映射表中所有条目的集合，这些条目是接口Map.Entry<k，v>的实例，该接口是Map接口的一个内部接口：

HashMap中的条目时没有顺序的，LinkedHashMap可以让元素按照插入顺序进行排序，也可以按照它们被最后一次访问时候的顺序，从最早到最晚排序，这称为访问顺序排序。无参构造方法是按照插入顺序来创建LinkedHashMap对象的，要按照访问顺序创建，需要使用如下的构造方法：

//将flag设置为true，即是按照访问顺序创建映射表
LinkedHashMap<Object, Object> linkedHashMap = new LinkedHashMap<>(int size, float loadFactor, boolean flag);

TreeMap类对于遍历已经排好序的键时是很高效的，可以让键的类实现Comparable接口，重写compareTo方法来排序，也可以使用外部比较器Comparator接口（Comparator接口中的compare方法）来排序，如果要使用比较器，必须使用指定比较器的构造方法来创建映射表，不再赘述；

另外在Java2以前，都是使用Hashtable来映射建和值，为了适应java合集框架，Hashtable进行了重新设计，但是，为了向后兼容保留了所有的方法，Hashtable实现了Map接口，除了Hashtable的更新方法是同步的以外，它与HashMap的用法是一样的。

 

二十、如何选取合适的映射表来存储数据呢？

答：如果不需要维护映射表中的键值对顺序，就用HashMap；

       如果需要保证映射表中的插入顺序或者访问顺序，就使用LinkedHashMap；

       如果需要映射表按照键排序，那就使用TreeMap。

 

二十一、如何选取合适的合集来存储数据呢？

答：稍后补图