JAVA集合框架
一、集合框架接口
集合框架是一个统一的架构，负责保存、装载数据，因此结合类也称容器类，集合框架主要由接口、抽象类和实现类构成。JAVA结合框架可以分为set、list、map、queue四大体系，其中set代表无序不可重复的集合；list代表有序、可重复的集合；map代表具有映射关系的集合；queue代表队列集合。 图1 JAVA集合框架 从图1可以看出： （1）实线边框的是实现类，比如ArrayList、LinkedList、HashMap等抽象类；折线边框的是抽象类，比如AbstractCollection、AbstractList、AbstractMap等抽象类；点线边框的是接口，比如Collection、Iterator、List等接口。 （2）上述所有的结合类，都实现了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含hashNext()、next()、remove()三种方法；它的一个子接口LinkedIterator在它的基础上又添加了三种方法，分别是add()、previous()、hashPrevious()三种方法。 （3）如果是先Iterator接口，那么在遍历集合中元素的时候，只能往后遍历，被遍历后的元素不会在遍历到，通常无序集合实现的都是这个接口，比如HashSet，HashMap实现类；而那些元素有序的集合，实现的一般都是LinkedIterator接口，实现这个接口的集合可以双向遍历，既可以通过next()访问下一个元素，又可以通过previous()访问前一个元素，比如ArrayList实现类。 （4）在抽象类的使用上，如果要自己实现一个集合类，去实现那些抽象的接口会非常麻烦，工作量很大。这个时候就可以使用抽象类，这些抽象类中给我们提供了许多现成的实现，我们只需要根据自己的需求重写一些方法或者添加一些方法就可以实现自己需要的集合类，工作量大大降低。 Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。 所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个 Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。 Iterator it = collection.iterator(); // 获得一个迭代子
二、List集合框架接口
List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。 ArrayList实现类
ArrayList实现了可变大小的数组，它允许所有元素，包括null。ArrayList没有同步。size、isEmpty、get、set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。 Vector实现类
Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和 ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了 Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出 ConcurrentModificationException，因此必须捕获该异常。 Vector是基于数组的方式实现的，是同步的，所以它查询速度要比ArrayList慢、比LinkedList快，它的插入和删除相对要比LinkedList慢一些。 LinkedList实现类
LinkedList实现了List接口，允许null元素，链式存储的线性表，其本质就是一个双向链表。此外LinkedList提供额外的get、remove、insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。 List list = Collections.synchronizedList(new LinkedList(...)); LinkedList是基于链式存储的线性表实现的，是非同步的，所以它查询速度要比ArrayList、Vector慢，但是它的插入和删除相对要比ArrayList、Vector快。 Stack 实现类
Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。 注意：如果想从集合类中获得一个数组可以使用toArray()方法；如果想从数组中获得一个列表可以使用asList()方法 。 注意：List集合代表一个有序集合。集合中的每个元素都有其对应的顺序索引。Arraylist和vector是list接口的两个典型实现。他们之间的显著区别就是：vector是线性安全的，而arraylist不是。它们两个都是基于数组实现的list类。List还有一个基于链表实现的LinkedList类。当插入、删除元素的速度非常快。这个类比较特殊，功能也特别多，即实现了List接口，也实现了Dueue接口(双向队列)。可以当成双向队列使用，也可以当成栈使用。 Queue 实现类
Queue用于模拟队列的数据结构。 三、Set集合框架接口
Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。 HashSet实现了Set接口的hash table(哈希表)，依靠HashMap来实现.应该为要存放到散列表的各个对象定义hashCode()和equals()，因为实现了set接口所以不能有重复的元素。HashSet主要的特点是：里面不能存放重复元素，而且采用散列的存储方法，所以没有顺序。这里所说的没有顺序是指：元素插入的顺序与输出的顺序不一致。 TreeSet是依靠TreeMap来实现的.TreeSet是一个有序集合,TreeSet中元素将按照升序排列，缺省是按照自然排序进行排列，意味着TreeSet中元素要实现Comparable接口。我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。 注意：HashSet是基于Hash算法实现的，其性能通常优于TreeSet，通常都应该使用HashSet，在需要排序的功能时，才使用TreeSet。 四、Map集合框架接口
Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。 Hashtable实现类
Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。 Hashtable numbers = new Hashtable();
Integer n = (Integer)numbers.get(“two”);
HashMap实现类
HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。 WeakHashMap实现类
WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。 注意：Map用于保存具有映射关系的数据。Map接口有如下几个常用的实现类：HashMap、HashTable、TreeMap。TreeMap是基于红黑树对TreeMap中所有key进行排序。HashMap和HashTable主要区别有两点：1、Hashtable是线性安全的，因此性能差些。2、HashMap可以使用null作为key或者value。 五、集合框架之间区别
Vector和ArrayList
（1）Vector是线程同步的，所以它也是线程安全的，而Arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用Arraylist效率比较高。 （4）ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要设计到数组元素移动 等内存操作，所以索引数据快插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！ Arraylist和LinkedList
（1）ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 （2）对于随机访问get和set方法，ArrayList绝对优于LinkedList，因为LinkedList要移动指针。 （3）对于新增和删除操作add和remove方法，LinkedList比较占优势，因为ArrayList要移动数据。 （4）如果只对单条数据插入或者删除，ArrayList的速度反而优于LinkedList，但是如果是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList。因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。
|
|
|
