17.集合

集合

集合类是Java数据结构的实现。Java的集合类是java.util包中的重要内容，它允许以各种方式将元素分组，并定义了各种使这些元素更容易操作的方法。Java集合类是Java将一些基本的和使用频率极高的基础类进行封装和增强后再以一个类的形式提供。集合类是可以往里面保存多个对象的类，存放的是对象，不同的集合类有不同的功能和特点，适合不同的场合，用以解决一些实际问题。

Java中的集合类可以分为两大类：一类是实现Collection接口；另一类是实现Map接口。
Collection是一个基本的集合接口，Collection中可以容纳一组集合元素（Element）。
Map没有继承Collection接口，与Collection是并列关系。Map提供键（key）到值（value）的映射。一个Map中不能包含相同的键，每个键只能映射一个值。
Collection有两个重要的子接口List和Set。List表达一个有序的集合，List中的每个元素都有索引，使用此接口能够准确的控制每个元素插入的位置。用户也能够使用索引来访问List中的元素，List类似于Java的数组。Set接口的特点是不能包含重复的元素。对Set中任意的两个元素element1和element2都有elementl.equals（element2）= false。另外，Set最多有一个null元素。此接口模仿了数学上的集合概念

Map接口与Collection接口不同，Map提供键到值的映射。Map接口提供三种Collection视图，允许以键集、值集或键一值映射关系集的形式查看某个映射的内容。

一、List集合

List集合代表一个有序集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。
List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector。

• ArrayList
  ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。ArrayList是擅长随机访问的。

public static void main(String[] args) {//定义一个list集合，指定泛型为String，（）中为集合初始长度List<String> list=new ArrayList<String>(100);//list集合的add方法是指向集合中添加一个（符合泛型要求的）元素list.add("张三");list.add("李四");list.add("王五");//list集合的add方法是指向集合中指定位置，添加一个（符合泛型要求的）元素[属于方法重载]list.add(0,"赵六");//list集合使用size（）方法获取集合长度，集合从0开始，最后一位元素为size-1，与数组相似for (int i = 0; i < list.size(); i++) {//list集合通过get（index）方法获取集合中的元素，index为集合下标，集合下标从0开始System.out.println(list.get(i));}}

ArrayList是线程不同步，不安全的集合

• LinkedList
  同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。
  由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

public static void main(String[] args) {//创建list集合的LinkedList实例List<String> list=new LinkedList<String>();//使用add方法添加元素list.add("张三");list.add("李四");list.add("王五");//向下转型获取linkedList对象LinkedList<String> linkedList=(LinkedList<String>)list;//向首位添加元素linkedList.addFirst("赵六");//向末位添加元素linkedList.addLast("最后一位");//使用for循环对象形式迭代集合for (String string : linkedList) {System.out.println(string);}}

LinkedList是线程不同步，不安全的集合

注：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候速度较快，比线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要较长时间。

• Vector
  与ArrayList相似，但是Vector是线程同步的。所以说Vector是线程安全的动态数组集合。它的操作与ArrayList几乎一样。

二、Set集合

Set是一种不包括重复元素的Collection。它维持它自己的内部排序，所以随机访问没有任何意义。与List一样，它同样允许null的存在但是仅有一个。由于Set接口的特殊性，所有传入Set集合中的元素都必须不同，同时要注意任何可变对象，如果在对集合中元素进行操作时，导致e1.equals(e2)==true，则必定会产生某些问题。Set接口有三个具体实现类，分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。
Set是一种不包含重复的元素的Collection，无序，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。需要注意的是:虽然Set中元素没有顺序，但是元素在set中的位置是由该元素的HashCode决定的，其具体位置其实是固定的。
Set接口中的不重复是有特殊要求的，如果一个类重写了hashcode和equals方法，并且重写后的hashcode和equals方法是相同的话。那么这个类实例化的两个对象是不能同时放入到Set集合中去的，也就是Set集合中的去重和hashcode与equals方法直接相关。

• HashSet HashSet
  是一个没有重复元素的集合。它是由HashMap实现的，不保证元素的顺序(这里所说的没有顺序是指：元素插入的顺序与输出的顺序不一致)，而且HashSet允许使用null
  元素。HashSet是非线程同步的，如果多个线程同时访问一个哈希set，而其中至少一个线程修改了该set，那么它必须保持外部同步。
  HashSet按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。
  Set易出现的误区：
  HashSet中可以存放null值，但只能存放一个null值。
  HashSet中存储元素的位置是固定的，也是无序的，HashSet的位置是根据HashCade的实现的。
  HashSet中如果存储可变对象，那么要注意一但对象发生变化，会引起错误。

public static void main(String[] args) {Set<String> set=new HashSet<String>();set.add("张三");set.add("张三1");for (String string : set) {System.out.println(string);}}

• LInkedHashSet
  LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非线程同步。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

public static void main(String[] args) {LinkedHashSet<String> set=new LinkedHashSet<String>();set.add("张三");set.add("张三1");for (String string : set) {System.out.println(string);}System.out.println();}

• TreeSet
  TreeSet是一个有序集合，其底层是基于TreeMap实现的，非线程安全。TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。
  注意：TreeSet集合不是通过hashcode和equals函数来比较元素的.它是通过compare或者comparaeTo函数来判断元素是否相等.compare函数通过判断两个对象的id，相同的id判断为重复元素，不会被加入到集合中。

三、Map集合

Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。同时它也没有继承Collection。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。

• HashMap
  以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，Map中包括了一个内部类Entry，该类封装了一个key-value记录，其内部定义了一个hash表数组（Entry[]
  table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构。

public static void main(String[] args) {Map<Integer, String> map=new HashMap<Integer, String>();map.put(1, "张三");map.put(2, "李四");map.put(3, "王五");map.put(4, "赵六");map.put(5, "你猜");for (Integer i : map.keySet()) {System.out.println(map.get(i));}System.out.println("*******************");for (String str: map.values()) {System.out.println(str);}}

• HashTable Hashtable和HashMap使用方法基本一致 Hashtable和HashMap的区别：
  Hashtable不允许使用null作为key和value，如果试图把nul放进HashTable中，将会引发NullPointerException异常；但HashMap可以使用null作为key或value
  Hashtable是一个线程安全的Map实现类，但HashMap是线程不安全的实现类，所以HashMap要比Hashtable的性能高一点；但是如果有多个线程访问同一个Map对象时，使用Hashtable实现类会更好

四、迭代器Iterator 与 ListIterator

Iterator是一个接口，它是集合的迭代器。集合可以通过Iterator去遍历集合中的元素。

public static void main(String[] args) {ArrayList<String> a = new ArrayList<String>();a.add("aaa");a.add("bbb");a.add("ccc");Iterator<String> it = a.iterator();while (it.hasNext()) {System.out.println(it.next());}}

ListIterator是一个功能更加强大的迭代器, 它继承于Iterator接口,只能用于各种List类型的访问。可以通过调用listIterator()方法产生一个指向List开始处的ListIterator, 还可以调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator。

public static void main(String[] args) {ArrayList<String> a = new ArrayList<String>();a.add("aaa");a.add("bbb");a.add("ccc");ListIterator<String> it = a.listIterator();while (it.hasNext()) {System.out.println(it.next());}System.out.println("******************");while (it.hasPrevious()) {System.out.println(it.previous());}}