java集合框架(collections framework)详解

什么是集合框架:
java中有一种特殊的类,这些类的内部可以存放多个其他类型的不同对象
文章涉及集合数组的区别，collection接口，iterator迭代器，list接口及其用法，LinkedHashSet集合等有关内容
简介:
集合和数组的区别:

在java中，Collection接口是集合框架的根接口，所有集合的类型都实现了此接口或从其子接口中继承,例如:list和set接口。
Collection接口
既然list和set是其子接口,那么意味着list和set的实现都含有collection接口含有的方法,根据数据结构的不同，一些collection允许有重复的元素，而另一些则不允许。一些collection是有序的，而另一些则是无序的。这里首先了解一下集合框架出现的接口,如图:

此处collection与map均位于集合框架的顶层,他们的区别是collection内每次存放的是对象例如:student,而map存放的是键值对就好像将学生直接放入collection类型教室,但放入map类型的教室时就要给学生起个别名,这个别名就是键,而具体的学生就是值,且键唯一;Collection有一些集合的通用性操作方法，分为两类：一类是普通方法；一类是带有All的方法，这类方法操作的是集合。

Iterator通用迭代器
因为不同类型的集合存储数据时数据结构不同，想要写一个通用的遍历集合的方法是不现实的。但无论是哪种类型的集合，只有集合自身对集合中的元素是最了解的，因此在实现Collection接口时，不同集合类都实现了自己独有的遍历方法，这称为集合的迭代器Iterator。其实Collection继承了java.lang.Iterable接口，该接口只提供了一个方法：iterator()，只要是实现了这个接口的类就表示具有迭代的能力，也就具有foreach增强遍历的能力。
Iterator接口提供了3个方法：
hasNext()：判断是否有下一个元素。
Next()：获取下一个元素。注意它返回的是Object(暂不考虑泛型)类型。
remove()：移除迭代器最后返回的一个元素。此方法为Collection迭代过程中修改元素的唯一安全的方法。
list

list是指有顺序可重复的容器;其实现类有3个:ArrayList,LinkedList,Vector
ArrayList继承自List接口，List接口又继承自Collection接口。ArrayList类存储的集合中，元素有序、可重复,且每个元素都有唯一的数字下标。
注意:ArrayList底层封装了数组,故其特点是查询效率高,增删效率低.数组的长度是有限的,其扩容的本质是先定义一个更大的数组,然后将数组的内容复制到新数组中来实现的.注意ArrayList是线程非安全的,
List集合的迭代器ListIterator
通过listIterator()方法可以获取ListIterator迭代器。该迭代器接口提供了如下几种方法：
hasNext()：是否有下一个元素
hasPrevious()：是否有前一个元素，用于逆向遍历
next()：获取下一个元素
previour()：获取前一个元素，用于逆向遍历
add(element)：插入元素。注：这是迭代器提供的add()，而非List提供的add()
remove()：移除next()或previous()获取到的元素。注：这是迭代器提供的remove()，而非List提供的remove()
set(element)：设置next()或previour()获取到的元素。注：这是迭代器提供的set()，而非List提供的set()
Vector
线程安全的,
**注意,**底层是一个长度可动态增长的对象数组,它的方法都加了synchronized,因此是线程安全的但效率低
LinkedList:
底层是双向链表实现的,其增删效率高,查询效率低,故其适用于频繁的对集合内元素进行增删改时,此时的效率较高
（2）数据增长：
ArrayList与Vector都有一个初始的容量大小，当存储进它们里面的元素的个数超过了容量时，就需要增加ArrayList与Vector的存储空间，每次要增加存储空间时，不是只增加一个存储单元，而是增加多个存储单元，每次增加的存储单元的个数在内存空间利用与程序效率之间要取得一定的平衡。Vector默认增长为原来两倍，而ArrayList的增长策略在文档中没有明确规定（从源代码看到的是增长为原来的1.5倍）。ArrayList与Vector都可以设置初始的空间大小，Vector还可以设置增长的空间大小，而ArrayList没有提供设置增长空间的方法。
总结：即Vector增长原来的一倍，ArrayList增加原来的0.5倍。

set接口
Set接口也实现了Collection接口。它既然能单独成类，它和List集合的数据结构一定是大有不同的。
特点:
1.Set集合中的元素无序。这里的无序是相对于List而言的，List的有序表示有下标Index的顺序，而Set无序是指没有index也就没有顺序。
2.Set集合中的元素不可重复。若重复,就添加不进去.
3.因为无序，因此Set集合中取出元素的方法只有一种：迭代。
4.实现Set接口的两个常见类为：
(1)HashSet：hash表数据结构；
1).不同步；
2).查询速度快；
3).判断元素是否重复的唯一方法是：先调用hashcode()判断对象是否相同，相同者再调用equals()方法判断内容是否相同。所以，要将元素存储到此数据结构的集合中，必须重写hashcode()和equals()。
(2).TreeSet：二叉树数据结构；
1).二叉树是用来排序的，因此该集合中的元素是有序的。这个有序和List的有序概念不同，此处的有序指的是存储时对元素进行排序，例如按照字母顺序，数字大小顺序等，而非index索引顺序。
2).既然要排序，而equals()方法只能判断是否相等。因此数据存储到TreeSet集合中时需要能够判断大小。
3).有两种方法用于构造有序的TreeSet集合：
a.待存储对象的类实现Comparable接口并重写它的compareTo()方法；
b.在构造TreeSet集合时指定一个比较器comparator。这个比较器需要实现Comparator接口并重写compare()方法。
(3).LinkedHashSet：链表形式的HashSet，仅在HashSet上添加了链表索引。因此此类集合有序(Linked)、查询速度快(HashSet)。不过很少使用该集合类型。
Map接口

用于存储键值对,其存储的键值是通过键来标识的,所有键不能重复,值可以重复
1.map接口的实现类有:HashMap,TreeMap,HashTable
2.常用的方法:
put(),get(),remove(),boolean containsKey(object key),Boolean containsValue(Object Value), void putAll(Map t)
3.HashMap 是 Map 的一个实现类，用来存放键值对。它允许将 null 作为 key 或者 value。HashMap采用散列算法实现,是Map接口常用的实现类,其底层采用哈希表存储数据,若键重复,新值会覆盖旧值,其在查找,删除,修改父母效率都非常高
4.Hashtable 同样也是 Map 的一个实现类，不过它不允许将 null 作为 key 或者 value。线程安全,但效率低
5.哈希表:本质上就是”数组+单向链表”,故融合了2者优点:查询效率和增删效率都高;
Entry[ ] table 是HashMap的核心数组结构，也称为“位桶数组”，这个位桶数组中的每个数组对象就是一个单向链表，要将“key-value”两个对象成对存入HashMap的Entry[ ]数组中，步骤如下：
（1）获得key的hashcode,通过调用hashcode()方法；
（2）由hashcode计算hash值（要求在[0, 数组长度-1]区间内）
a.其中一种极其简单和低下的算法：hash值=hashcode/hashcode,意味着将所有键值对对象全部存储到Entry[]索引为1的位置上，形成一个非常长的单向链表；
b. 一种简单和常用的算法：hash值=hashcode%数组长度，缺点：使用除法，效率会低；
c.JDK改进的算法：首先约定数组长度必须为2的整数幂，然后采用位运算实现取余：hash值 =hashcode&(数组长度-1)。
6.TreeMap底层是用红黑二叉树实现的，HashMap的效率高于TreeMap,在需要key按照自然顺序排序时才使用TreeMap。
7.HashMap和HashTable的区别:
①继承不同。

public class Hashtable extends Dictionary implements Map 
public class HashMap extends AbstractMap implements Map

②Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。
③Hashtable中，key和value都不允许出现null值。
在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
④两个遍历方式的内部实现上不同。
Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。
⑤哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
⑥Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。