Java【有与无】【F2】集合篇

 

1.简介

List集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。

Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问。

Map集合中保存Key-value对形式的元素，访问时只能根据每项元素的key来访问其value。

2.List接口

1）ArrayList

动态数组，允许任何符合规则的元素插入甚至包括null。

默认容量是10，如果初始化时一开始指定了容量，或者通过集合作为元素，则容量为指定的大小或参数集合的大小。

每次扩容为原来的1.5倍，如果新增后超过这个容量，则容量为新增后所需的最小容量。

如果增加0.5倍后的新容量超过限制的容量，则用所需的最小容量与限制的容量进行判断，超过则指定为Integer的最大值，否则指定为限制容量大小。

然后通过数组的复制将原数据复制到一个更大(新的容量大小)的数组。 

线程不安全

查询效率高

参考

2）LinkedList

双向链表

没有初始化大小，也没有扩容的机制

线程不安全

对元素的增加、删除效率高

参考

3）Vector

动态数组

线程安全，速度慢

默认初始容量为10，扩容原容量的1倍

容量的最大范围为Integer.MAX_VALUE即，2^32 - 1，Vector并不是可以无限扩充的

参考

4）Stack

继承自Vector，先进后出(FILO, First In Last Out)的栈。

线程安全

参考

3.Set接口

Set是一种不包括重复元素的Collection。它维持它自己的内部排序，所以随机访问没有任何意义。

线程不安全

1）HashSet

没有重复元素的集合。

它是由HashMap实现的，不保证元素的顺序(这里所说的没有顺序是指：元素插入的顺序与输出的顺序不一致)，而且HashSet允许使用null元素。非同步的，如果多个线程同时访问一个哈希set，而其中至少一个线程修改了该set，那么它必须保持外部同步。 它按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。

实现方式，通过一个HashMap存储元素，元素是存放在HashMap的Key中，而Value统一使用一个Object对象。

使用和理解中容易出现的误区:

a.存放null值
允许存入null值的，但是在HashSet中仅仅能够存入一个null值。

b.存储元素的位置是固定的
存储的元素的是无序的，但是由于HashSet底层是基于Hash算法实现的，使用了hashcode，所以HashSet中相应的元素的位置是固定的。
  
c.必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

参考

2）LinkedHashSet

继承HashSet，底层是基于LinkedHashMap来实现的，有序，非同步。

根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。当遍历该集合时候，会以元素的添加顺序访问集合的元素。

3）TreeSet

有序集合，底层是基于TreeMap实现的，非线程安全。

支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。

当构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。

TreeSet集合不是通过hashcode和equals函数来比较元素的.它是通过compare或者comparaeTo函数来判断元素是否相等.compare函数通过判断两个对象的id，相同的id判断为重复元素，不会被加入到集合中。

4.Map接口

由一系列键值对组成的集合，提供了key到Value的映射。没有继承Collection。

1）HashMap

线程不安全，超过最大值（2^30）就不再扩充

默认加载因子是 0.75，没超过最大值，扩充为原来的2倍

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

参考

2）LinkedHashMap

HashMap的一个子类，保留插入的顺序

它是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。允许使用null值和null键。不保证映射的顺序。

它维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。

非同步的，线程不安全。性能略低于HashMap 。

3）TreeMap

有序的key-value集合，非同步，线程不安全，基于红黑树（Red-Black tree）实现，每一个key-value节点作为红黑树的一个节点。

存储时会进行排序的，会根据key来对key-value键值对进行排序，有两种排序方式，自然排序、定制排序，具体取决于使用的构造方法。

自然排序：
所有的key必须实现Comparable接口，并且所有的key都应该是同一个类的对象，否则会报ClassCastException异常。

定制排序：
定义TreeMap时，创建一个comparator对象，该对象对所有的treeMap中所有的key值进行排序，采用定制排序的时候不需要TreeMap中所有的key必须实现Comparable接口。

判断两个元素相等的标准：
两个key通过compareTo()方法返回0，则认为这两个key相等。
如果使用自定义的类来作为TreeMap中的key值，且想让TreeMap能够良好的工作，则必须重写自定义类中的equals()方法，TreeMap中判断相等的标准是：两个key通过equals()方法返回为true，并且通过compareTo()方法比较应该返回为0。

参考

4）Hashtable

不推荐使用

使用哈希表存储，哈希表的实现是拉链法

key和value都是不能为空的，key不能为空的原因是，在Hashtable的方法内部，会利用key.hashCode()的方法，来计算哈希值；在Hashtable的put方法内部对value做了判空的操作，如果value为空会抛出空指针异常。

线程安全，由于Hashtable是将synchronized关键字直接加在方法，因此多线程的时候可能会引发有效率问题

默认大小是11，没超过最大值，扩充为原来的2倍+1

 

5）WeakHashMap

散列表，它存储的内容是键值对(key-value)映射，键和值都可以是null

当某个键不再正常使用时，会被从WeakHashMap中被自动移除

对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，使该键成为可终止的，被终止，然后被回收。

某个键被终止时，对应的键值对也就从映射中有效地移除了

"弱键"的原理大致是
通过WeakReference和ReferenceQueue实现的。 
WeakHashMap的key是“弱键”，即是WeakReference类型的；
ReferenceQueue是一个队列，它会保存被GC回收的“弱键”。"弱键"如何被自动从WeakHashMap中删除的步骤(01) 新建WeakHashMap，将"键值对"添加到WeakHashMap中。
实际上，WeakHashMap是通过数组table保存Entry(键值对)；
每一个Entry实际上是一个单向链表，即Entry是键值对链表。
(02) 当某"弱键"不再被其它对象引用，并被GC回收时。
在GC回收该“弱键”时，这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中。
(03) 当下一次需要操作WeakHashMap时，会先同步table和queue。
table中保存了全部的键值对，而queue中保存被GC回收的键值对；同步它们，就是删除table中被GC回收的键值对。

参考

 

5.区别

5.1.Iterator 与 ListIterator

Iterator
public interface Iterator<E> {}
Iterator是一个接口，它是集合的迭代器。集合可以通过Iterator去遍历集合中的元素。

Iterator提供的API接口如下：
boolean hasNext()：判断集合里是否存在下一个元素。如果有，hasNext()方法返回 true。
Object next()：返回集合里下一个元素。
void remove()：删除集合里上一次next方法返回的元素。

注意：
（1）Iterator只能单向移动。
（2）Iterator.remove()是唯一安全的方式来在迭代过程中修改集合；如果在迭代过程中以任何其它的方式修改了基本集合将会产生未知的行为。而且每调用一次next()方法，remove()方法只能被调用一次，如果违反这个规则将抛出一个异常。

ListIterator
public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
} 

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

注意：
(1)双向移动（向前/向后遍历）.
(2)产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引.
(3)可以使用set()方法替换它访问过的最后一个元素.
(4)可以使用add()方法在next()方法返回的元素之前或previous()方法返回的元素之后插入一个元素.

5.2.ArrayList与LinkedList

（1）ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 
（2）对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要移动指针。 
（3）对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。 
这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

5.3.HashTable与HashMap

相同点：

（1）都实现了Map、Cloneable、java.io.Serializable接口。
（2）都是存储"键值对(key-value)"的散列表，而且都是采用拉链法实现的。

不同点：

（1）历史原因:HashTable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现 。
（2）同步性:HashTable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的 。
（3）对null值的处理：HashMap的key、value都可为null，HashTable的key、value都不可为null 。
（4）基类不同：HashMap继承于AbstractMap，而Hashtable继承于Dictionary。

      Dictionary是一个抽象类，它直接继承于Object类，没有实现任何接口。Dictionary类是JDK 1.0的引入的。虽然Dictionary也支持“添加key-value键值对”、“获取value”、“获取大小”等基本操作，但它的API函数比Map少；而且Dictionary一般是通过Enumeration(枚举类)去遍历，Map则是通过Iterator(迭代M器)去遍历。 然而由于Hashtable也实现了Map接口，所以，它即支持Enumeration遍历，也支持Iterator遍历。
      AbstractMap是一个抽象类，它实现了Map接口的绝大部分API函数；为Map的具体实现类提供了极大的便利。它是JDK 1.2新增的类。

（5）支持的遍历种类不同：HashMap只支持Iterator(迭代器)遍历。而Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历。

5.4.HashMap、Hashtable、LinkedHashMap和TreeMap

Hashmap

根据键的HashCode 值存储数据，根据键可以直接获取它的值，具有很快的访问速度。

遍历时，取得数据的顺序是完全随机的。

最多只允许一条记录的键为Null;

允许多条记录的值为Null;

不支持线程的同步。如果需要同步，可以用Collections的synchronizedMap方法使HashMap具有同步的能力。

Hashtable

它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable，因此也导致了Hashtale在写入时会比较慢。

LinkedHashMap

保存记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时用带参数，按照应用次数排序。

在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。如果需要输出的顺序和输入的相同，那么用LinkedHashMap可以实现，它还可以按读取顺序来排列，像连接池中可以应用。LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。

如果需要输出的顺序和输入的相同，那么用LinkedHashMap可以实现，它还可以按读取顺序来排列，像连接池中可以应用。

TreeMap

实现SortMap接口，内部实现是红黑树。能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。TreeMap不允许key的值为null。非同步的。 

如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。

5.5.HashSet、LinkedHashSet、TreeSet

HashSet

不保证元素的排列顺序，非同步的

集合元素可以是null，但只能放入一个null。

当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。

如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。

如果两个对象通过equals方法比较返回true时，其hashCode也应该相同。对象中用作equals比较标准的属性，都应该用来计算 hashCode的值。

LinkedHashSet

根据元素的hashCode值来决定元素的存储位置，它使用链表维护元素的次序，看起来像是以插入顺序保存的。

性能比HashSet好，插入时性能稍微逊色于HashSet。

TreeSet

SortedSet接口的唯一实现类，可以确保集合元素处于排序状态。

支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。

向TreeSet中加入的应该是同一个类的对象。

判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0。

自然排序
    使用要排序元素的CompareTo（Object obj）方法来比较元素之间大小关系，然后将元素按照升序排列。
    Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现了该接口的对象就可以比较大小。obj1.compareTo(obj2)方法如果返回0，则说明被比较的两个对象相等，如果返回一个正数，则表明obj1大于obj2，如果是负数，则表明obj1小于obj2。如果将两个对象的equals方法总是返回true，则这两个对象的compareTo方法返回应该返回0。

定制排序
   使用Comparator接口，实现 int compare(T o1,T o2)方法。

5.6.Iterator和ListIterator

（1）ListIterator有add()方法，可以向List中添加对象，而Iterator不能
（2）ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。
（3）ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator无功能。
（4）都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改。

5.7.Collection 和 Collections

java.util.Collection 集合类的一个顶级接口，提供了对集合对象进行基本操作的通用接口方法。

java.util.Collections  集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。
 

详细介绍