Java系列-集合框架理解

Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。 不同接口描述一组不同数据类型。 

日常比较常用的的集合框架关系如上图所示: 

(1).集合接口： 短虚线表示 ,其中5个关键接口Iterator,Collection,Map,List,Set，表示不同集合类型，是集合框架的基础。 

(2).抽象类：长虚线表示AbstractCollection, AbstractList ,AbstractSet ,AbstractMap ,AbstractSequentialList，对集合接口的部分实现。可扩展为自定义集合类。 

(3).实现类：实线表示，对接口的具体实现

ArrayList,LinkedList, Vector,Stack ,HashSet,LinkedHashSet,TreeSet,HashMap,TreeMap,LinkedHashMap,Hashtable,Queue等。 

1.Collection接口

public interface Collection<E>extends Iterable<E>

Collection 层次结构 中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接 实现：它提供更具体的子接口（如 Set 和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。

  Collection接口有几个个主要的子接口List和Set,Queue，注意Map不是Collection的子接口哦这个要牢记。

  Collection中可以存储的元素间无序，可以重复组各 自独立的元素， 即其内的每个位置仅持有一个元素，同时允许有多个null元素对象。

2.List接口

public   interface   List<E>  extends   Collection<E> {}

有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

List 接口提供了特殊的迭代器，称为 ListIterator，除了允许 Iterator 接口提供的正常操作外，该迭代器还允许元素插入和替换，以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。

同时List接口又有几个常用的实现类ArrayList和LinkedList,Stack, Vector等

2.1 ArrayList实现类

 ArrayList数组线性表的特点为:类似数组的形式进行存储，因此它的随机访问速度极快。

 ArrayList数组线性表的缺点为:不适合于在线性表中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。

 可以这样理解ArrayList就是基于数组的一个线性表，只不过数组的长度可以动态改变而已。

List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）

ArrayList 的需要注意点:

a.如果在初始化ArrayList的时候没有指定初始化长度的话，默认的长度为10.

b.ArrayList在增加新元素的时候如果超过了原始的容量的话，ArrayList扩容ensureCapacity的方案为“原始容量*3/2+1"哦。

c.ArrayList是线程不安全的，在多线程的情况下不要使用。

  如果一定在多线程使用List的，您可以使用Vector，因为Vector和ArrayList基本一致，区别在于Vector中的绝大部分方法都

  使用了同步关键字修饰，这样在多线程的情况下不会出现并发错误哦，还有就是它们的扩容方案不同，ArrayList是通过原始

  容量*3/2+1,而Vector是允许设置默认的增长长度，Vector的默认扩容方式为原来的2倍。

  切记Vector是ArrayList的多线程的一个替代品。

d.实现遍历的几种方式

(1). foreach遍历

(2). 转数组遍历

      List<String> list= new   ArrayList<String>();

(3).迭代器遍历

      Iterator<String> ite=list.iterator();

      while (ite.hasNext())

      {

          System.out.println(ite.next());

      }

2.2 LinkedList实现类

extends AbstractSequentialList<E>

implements List<E>, Deque<E>, Cloneable, Serializable

List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

  可以这样理解LinkedList就是一种双向循环链表的链式线性表，只不过存储的结构使用的是链式表而已。

需要注意的点:

a.LinkedList和ArrayList的区别和联系

  ArrayList数组线性表的特点为:类似数组的形式进行存储，因此它的随机访问速度极快。

  ArrayList数组线性表的缺点为:不适合于在线性表中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。

  LinkedList的链式线性表的特点为: 适合于在链表中间需要频繁进行插入和删除操作。

  LinkedList的链式线性表的缺点为: 随机访问速度较慢。查找一个元素需要从头开始一个一个的找。速度你懂的。

b.LinkedList的内部实现

  对于这个问题，你最好看一下jdk中LinkedList的源码。这样你会醍醐灌顶的。

  这里我大致说一下:

  LinkedList的内部是基于双向循环链表的结构来实现的。在LinkedList中有一个类似于c语言中结构体的Entry内部类。

  在Entry的内部类中包含了前一个元素的地址引用和后一个元素的地址引用类似于c语言中指针。

 c.LinkedList不是线程安全的

  注意LinkedList和ArrayList一样也不是线程安全的，如果在对线程下面访问可以自己重写LinkedList

  然后在需要同步的方法上面加上同步关键字synchronized

d.LinkedList的遍历方法:(1)foreach(2)转数组(3)迭代器

2.3 Vector实现类

extends AbstractList<E>

implements List<E>, RandomAccess, Cloneable, Serializable

Vector 类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。但是，Vector 的大小可以根据需要增大或缩小，以适应创建 Vector 后进行添加或移除项的操作。

Vector 是同步的。

2.3 Stack实现类

extends Vector<E>

Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。

首次创建堆栈时，它不包含项。

3.Set接口

3.1 HashSet实现类

   public HashSet() {

   map = new HashMap<E,Object>();

3.2 LinkedHashSet实现类

     Set s = Collections.synchronizedSet(new LinkedHashSet(...));

3.3 TreeSet实现类

 TreeSet是一种排序二叉树。存入Set集合中的值，会按照值的大小进行相关的排序操作。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。底层算法是基于红黑树来实现的。

  TreeSet和HashSet的主要区别在于TreeSet中的元素会按照相关的值进行排序~

  TreeSet和HashSet的区别和联系

  (1). HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key

  (2). Map的key和Set都有一个共同的特性就是集合的唯一性.TreeMap更是多了一个排序的功能.

  (3). hashCode和equal()是HashMap用的, 因为无需排序所以只需要关注定位和唯一性即可.

  a. hashCode是用来计算hash值的,hash值是用来确定hash表索引的.

  b. hash表中的一个索引处存放的是一张链表, 所以还要通过equal方法循环比较链上的每一个对象

  才可以真正定位到键值对应的Entry.

  c. put时,如果hash表中没定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value,并返回旧value

  (4). 由于TreeMap需要排序,所以需要一个Comparator为键值进行大小比较.当然也是用Comparator定位的.

  a. Comparator可以在创建TreeMap时指定

  b. 如果创建时没有确定,那么就会使用key.compareTo()方法,这就要求key必须实现Comparable接口.

  c. TreeMap是使用Tree数据结构实现的,所以使用compare接口就可以完成定位了.

  (5).推荐迭代器遍历

   SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

4.Map接口

说到Map接口的话大家也许在熟悉不过了。Map接口实现的是一组Key-Value的键值对的组合。 Map中的每个成员方法由一个关键字（key）和一个值（value）构成。Map接口不直接继承于Collection接口（需要注意啦），因为它包装的是一组成对的“键-值”对象的集合，而且在Map接口的集合中也不能有重复的key出现，因为每个键只能与一个成员元素相对应。在我们的日常的开发项目中，我们无时无刻不在使用者Map接口及其实现类。Map有两种比较常用的实现：HashMap和TreeMap等。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

  另外前边已经说明了，Set接口的底层是基于Map接口实现的。Set中存储的值，其实就是Map中的key，它们都是不允许重复的。

4.1 HashMap实现类

HashMap实现了Map、CloneMap、Serializable三个接口，并且继承自AbstractMap类。

       HashMap基于hash数组实现，若key的hash值相同则使用链表方式进行保存。

Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码，这些编码值叫做HASH值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。

　　数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，

它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。比如我们存储70个元素，但我们可能为这70个元素申请了100个元素的空间。70/100=0.7，这个数字称为负载因子。我们之所以这样做，也 是为了“快速存取”的目的。我们基于一种结果尽可能随机平均分布的固定函数H为每个元素安排存储位置，这样就可以避免遍历性质的线性搜索，以达到快速存取。

新建一个HashMap时,默认的话会初始化一个大小为16，负载因子为0.75的空的HashMap

我们提到使用Hash，但是Hash值如何与元素的存储建立关系呢？（Hash算法）

在数据结构课中我们学习过Hash的简单算法，就是给你一个Hash因子，通过对该元素的hashCode简单的求余，来实现对其快速的定位和索引。

在HashMap中有这样的代码：

- /**

- * Returns index for hash code h.

- */

- static int indexFor(int h, int length) {

- return h & (length-1);

- }

这个方法在HashMap中非常重要，凡是与查询、添加、删除有关的方法中都有调用该方法，为什么这么短的一个代码使用率这么高？根据代码注释我们知道，这个方法是根据hashCode及当前table的长度（数组的长度，不是map的size）得到该元素应该存放的位置，或者在table中的索引。

 void resize(int newCapacity) { 
        Entry[] oldTable = table; 
        int oldCapacity = oldTable.length; 
        if (oldCapacity == MAXIMUM_CAPACITY) { 
            threshold = Integer.MAX_VALUE; 
            return; 
        } 
 
        Entry[] newTable = new Entry[newCapacity]; 
        transfer(newTable); 
        table = newTable; 
        threshold = (int)(newCapacity * loadFactor); 
    } 
 
    /**
     * Transfers all entries from current table to newTable.
     */ 
    void transfer(Entry[] newTable) { 
        Entry[] src = table; 
        int newCapacity = newTable.length; 
        for (int j = 0; j < src.length; j++) { 
            Entry<K,V> e = src[j]; 
            if (e != null) { 
                src[j] = null; 
                do { 
                    Entry<K,V> next = e.next; 
                    int i = indexFor(e.hash, newCapacity); 
                    e.next = newTable[i]; 
                    newTable[i] = e; 
                    e = next; 
                } while (e != null); 
            } 
        } 
    } 

// Find a power of 2 >= initialCapacity 
int capacity = 1; 
while (capacity < initialCapacity) 
      capacity <<= 1; 
…… 
table = new Entry[capacity]; 

也就是说当我们传入1000时，它并没有给我们构造一个容量为1000的哈希表，而是构建了一个容量为1024大小的哈希表。

从整体上我们发现一个问题，那就是无论什么情况HashMap中哈希表的容量总是2的n次方的一个数。并且有这样一个公式：

  当length=2^n时，hashcode & (length-1) == hashcode % length

也就是这一点验证了第一个问题，hash索引值的计算方法其实就是对哈希因子求余。只有大小为2的n次方时，那样的计算才成立，所以HashMap为我们维护了一个这样大小的一个哈希表。（位运算速度比取模运算快的多）

c) HashMap的使用方法：

我在很多代码中都用到了HashMap，原因是首先它符合存储关联数据的要求，其次它的存取速度快，这是一个选择的问题。

Map的三种遍历方法：

1. 使用keySet遍历，while循环；

2. 使用entrySet遍历，while循环；

3. 使用for循环遍历。

4.2 LinkedHashMap实现类

LinkedHashMap继承自HashMap并且实现了Map接口。和HashMap一样，LinkedHashMap允许key和value均为null。

于该数据结构和HashMap一样使用到hash算法，因此它不能保证映射的顺序，尤其是不能保证顺序持久不变（再哈希）。

如果你想在多线程中使用，那么需要使用Collections.synchronizedMap方法进行外部同步。

LinkedHashMap与HashMap的不同之处在于，LinkedHashMap维护者运行于所有条目的双重链接列表，此链接列表可以是插入顺序或者访问顺序

Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。注意，如果在映射中重新插入 键，则插入顺序不受影响。（如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true，则调用时会将键 k 重新插入到映射 m 中。）

4.3 HashMap与Hashtable的区别：

Hashtable实现Map接口，继承自古老的Dictionary类，实现一个key-value的键值映射表。任何非空的（key-value）均可以放入其中。

区别主要有三点：

1. Hashtable是基于陈旧的Dictionary实现的，而HashMap是基于Java1.2引进的Map接口实现的；

2. Hashtable是线程安全的，而HashMap是非线程安全的，我们可以使用外部同步的方法解决这个问题。

3. HashMap可以允许你在列表中放一个key值为null的元素，并且可以有任意多value为null，而Hashtable不允许键或者值为null。

? WeakHashMap的特点：

我没有使用过这个类。网摘：WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

4.3TreeMap实现类

 public class TreeMap<K,V>

extends AbstractMap<K,V>

implements NavigableMap<K,V>, Cloneable, Serializable

基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

HashMap通过hashcode对其内容进行快速查找，而 TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。

HashMap 非线程安全 TreeMap 非线程安全

两种常规Map性能

HashMap：适用于在Map中插入、删除和定位元素。

Treemap：适用于按自然顺序或自定义顺序遍历键(key)。

HashMap通常比TreeMap快一点(树和哈希表的数据结构使然)，建议多使用HashMap，在需要排序的Map时候才用TreeMap。

5.Queue接口

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头 都是调用 remove() 或 poll() 所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现必须指定其顺序属性。

ava.ulil.concurrent包提供了阻塞队列的4个变种。默认情况下，LinkedBlockingQueue的容量是没有上限的（说的不准确，在不指定时容量为Integer.MAX_VALUE，不要然的话在put时怎么会受阻呢），但是也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。

ArrayBlockingQueue在构造时需要指定容量， 并可以选择是否需要公平性，如果公平参数被设置true，等待时间最长的线程会优先得到处理（其实就是通过将ReentrantLock设置为true来 达到这种公平性的：即等待时间最长的线程会先操作）。通常，公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队 列，此队列按 FIFO（先进先出）原则对元素进行排序。

PriorityBlockingQueue是一个带优先级的 队列，而不是先进先出队列。元素按优先级顺序被移除，该队列也没有上限（看了一下源码，PriorityBlockingQueue是对 PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞 队列上put时是不会受阻的。虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元 素要具有比较能力。

最后，DelayQueue（基于PriorityQueue来实现的）是一个存放Delayed 元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素。