Java 集合框架浅析

摘要：是非，而是，这意味着是线程安全的，多个线程可以共享一个而如果没有正确的同步的话，多个线程是不能共享的。另一个区别是的迭代器是迭代器，而的迭代器不

这里只解析一些常用的、比较重要的一些集合类，并且作者水平有限，有些地方可能解析不到位或者解析错误，还望各位读者指出错误。

Collection
     List
          ArrayList
          LinkedList
          Vector
               Stack
     Queue
          Deque
               LinkedList
     Set
          SortedSet
          HashSet
          TreeSet
Map
     HashMap
     HashTable
     TreeMap
     WeakHashMap

Java集合的一个大体框架，针对常用的方法来对集合类进行解析(JDK1.8)

List
List就是一个接口，继承了接口Iterator，是为了获得迭代器(Iterator)，用于遍历集合中的数据
定义了一些集合常用的方法add(0)、remove()等等

List--ArrayList
ArrayList底层数据结构是数组实现，非线程安全
成员变量：

transient Object[] elementData;  //这就是ArrayList类中存放数据的数组
private int size;  //记录的是当前在数组中可插入的索引值，表示的是当前数组的元素个数，并不表示当前数组的实际大小

常用方法解析：

1.construct
  public ArrayList();     //没有指定大小的集合,elementData = {}，在第一次执行add()方法的时候，就会设置数组的大小为10(DEFAULT_CAPACITY)
  public ArrayList(Collection c);  //参数一个集合，然后将参数复制到elementData上
  public ArrayList(int initialCapacity);  //参数集合大小，创建对象的时候就将数组的大小通过参数传进来，创建数组：elementData = new Object[initialCapacity];

2.add
  public boolean add(E e);  
  //添加element之前，先调用ensureCapacityInternal(size+1)，比较数组空间大小和当前的索引值，如果当前要插入的索引值大于数组的大小，就要执行grow(minCapacity)方法，
  //就是加大数组空间grow(minCapacity)是这样实现的，将得到oldCapacity=elementData.length，然后newCapacity=oldCapacity+(oldCapacity>>1)，也就是在原来数组空间的大小之上再   
  //加上原来的一半，具体还是得看代码   

  public void add(int index,E element);
  //在指定的索引出插入值，首先要判断索引是否越界，条件是(index>size || index<0)，符合任意条件，就抛出索引越界异常，因为这里是跟size比较，size是当前要插入到数组中的索引值，并非
  //数组的实际大小，这么做是为了防止这个浪费空间，如果size=10，index=100(假如数组实际大小超过100)，那这样就会导致index为10~99之间的空间浪费了

  public boolean addAll(Collection c);
  public void addAll(int index,Collection c);
  //这两个方法与上面类似，不再赘述

3.remove
  public E remove(inde index);
  //index >= size，抛出数组索引越界异常
  //否则：E oldValue=elementData[index],将该索引位置后面的元素（直到index=size-1）都往前移动，并且elementData[--size]=null,然后返回oldValue
  
  public boolean remove(Object o);
  //首先遍历elementData，判断o是否在elementData中，没有则返回false
  //否则：记录当前的index，然后调用fastRemove()方法

  private void fastRemove(int index);
  //这个跟remove(index)方法有些类似，也是将当前索引位置后面的元素往前移动，并且elementData[--size]=null;

List--LinkedList
LinkedList，顾名思义，其实就是一个双向链表，这也表明了LinkedList可以存储无数个元素，只要空间允许（因为地址不连续，只要有空间，就可以用来开辟节点，然后连上链表），非线程安全，非线程安全
成员变量：

transient int size = 0;   //当前链表中的元素个数
transient Node first;  //表头节点,Node是内部类，之后三个属性，E item(值)，Node next(下一个节点),Node prev(前一个节点);
transient Node last;   //表尾节点

常用方法解析：

1.construct
  public LinkedList();    //空实现
  public LinkedList(Collection c);  //执行上面的空方法，然后addAll(c),将c添加到链表中

2.add
  public boolean add(E e);
  //直接调用linkLast(e) 方法，然后返回true
  //看一下linkLast(E e)方法，这个方法实现的就是在双向链表的表尾添加一个元素，这个具体可以去搜索一下双向链表

  public void add(int index,E e);
  //首先判断index是否越界，判断标准就是index>=0 && index<=size
  //如果index=size，相当于在表尾添加节点，直接调用linkLast(e);
  //否则：调用linkBefore(e,node(index))函数,node(index)函数的作用是为了获取到当前所在索引的节点，因为链表每个节点的地址不是连续的，所以无法使用索引，这里的index只是标识了在这个
  //链表中的第几个
  //再看一下linkBefore(e,nodex(index))函数，通过node(index)获取当前索引的节点，接下来要新增的节点就处在当前节点的前面，具体实现搜索双向链表插入节点

  public boolean addAll(Collection c);
  public void addAll(int index,Collection c);
  //类似

  public void linkFirst(E e);
  //从表头添加节点
  public void linkLast(E e);
 //从表尾添加节点

3.remove
  public E remove();
  //调用removeFirst();

  public E remove(int index);
  //判断index的合法性
  //定位到index所在的节点，然后删除该节点

  public boolean remove(Object o);
  //判断o是否在链表中，如在链表中，即可删除

  public E removeFirst();
  //删除链表的头节点

  public E removeLast();
  //删除链表的尾节点

List--Vector
Vector与ArrayList类似，底层数据结构也是数组，但是Vector是线程安全的
成员变量：

protected Object[] elementData;   //存放数据的数组  //被protectd修饰的成员变量，子类可以使用，例如Stack
protected int elementCount;       //数组中的实际元素个数
protected int capacityIncrement;  //数组容量的每次增量大小

常用方法解析；

1.construct
  public Vector();   --> 调用this(10);
  public Vector(int initialCapacity);  --> 调用this(initialCapacity,0)，数组容量的增量没有指定的话，就为0，在每次给数组重新设置容量的时候，容量为原来的2倍
  public Vector(int initialCapacity,int capacityIncrement);  每次给数组重设容量的时候，新容量=旧容量+增量
  public Vector(Collection c);   //将集合c中的数据复制到elementData
  
2.add
  //与ArrayList除了线程安全，其余大同小异
  public synchronized boolean add(E e);

  public void add(int index,E element);
  //调用了synchronized void insertElement(E obj,int index)

  public synchronized void addElement(E obj);

3.remove
  public synchronized void removeElementAt(inde index);
  public synchronized boolean removeElement(Object obj);
  public synchronized E remove(int index);

List--Vector--Stack
Stack继承自Vector，是一个栈，进栈元素添加在数组最后面，出栈将最后一个元素弹出，push()和pop()方法体内调用的都是父类Vector的方法，所以也是线程安全的
常用方法解析：

1.construct
  public Stack();  //空方法实现

2.public E push(E item); 
  //实际上调用的是父类的addElement(E e)方法，并返回item

  public synchronized E pop();
  //调用peek()方法获取栈顶元素，然后调用父类的removeElement(int index)方法删除栈顶元素，并返回栈顶元素

  public synchronized E peek();
  //返回栈顶元素

Queue
Queue是一个接口，队列

Queue--Deque
Deque也是一个接口，继承了Queue接口，并定义相当多的方法

Queue--Deque--LinkedList
LinkedList实现了Deque接口，非线程安全，要创建一个队列，就让一个Queue引用指向LinkedList对象，队列的特点就是先进先出，跟排队买东西时一样的，
LinkedList在上面已经说过了，不再赘述

Set
Set是一个不包含重复元素的Collection接口，Set最多只能有一个null元素

Set--SortedSet
也是一个接口

Set--HashSet
底层数据结构居然是用HashMap实现的，也就造成了元素是无序的，也就无法通过索引来获取值，不包含重复数据，非线程安全
每次调用add(E e)方法的时候，都是直接把参数e当作数据容器map的key(从这可以看出来为什么HashSet不能包含重复值了)，PRESENT当作value
并且要遍历HashSet只能通过获取迭代器来讲HashSet中的元素迭代出来
成员变量：

HashMap map;   //存放数据的容器
private static final Object PRESENT = new Object();   //就是为了填充map的value的那个位置，没有其他任何作用

常用方法解析：

1.construct
  public HashSet(){
     map = new HashMap<>();  }   //hashmap没有指定容量 
  public HashSet(int initialCapacity){
     map = new HashMap<>(initialCapacity);  }   //指定初始化容量
  public HashSet(int initialCapacity,float loadFactor){
     map = new HashMap<>(initialCapacity,loadFactor);  }   //指定初始化容量，并
  public HashSet(int initialCapacity,float loadFactor,boolean dummy){
     map = new LinkedHashMap<>(initialCapacity,loadFactor);  }
  public HashSet(Collection c){
     map = new HashMap<>(Math.max((int)(c.size()/.75f)+1,16));  }

2.add
  public boolean add(E e){
     return map.put(e,PRESENT) == null;
  }
  //很简单，就是把要插入的元素当作HashMap的key，而HashMap的key是不能重复的，所以HashSet是不能包含重复值的

3.remove
  public boolean remove(Object o){
     return map.remove(o) == PRESENT;
  }

4.iterator
  public Iterator iterator(){
     return map.keySet.iterator();
  }
  //通过迭代器遍历HashSet中的元素

Map
Map是一个Key-Value的数据存储结构，是一个接口，定义了大量的接口方法

Map--HashMap
HashMap是Map的实现类，可以看到HashMap的底层也是使用数组实现的，但不同的是，数组的每个元素又是一个链表的头节点，所以HashMap的底层数据结构是数组+单向链表(如果链表的节点数量过多，则使用红黑树)来实现的，非线程安全
成员变量：

transient int size;   //当前数组中的元素个数   (transient关键字)
transient Node[] table;  //存放数据的容器，是一个散列表(数组+单向链表)，数组中的每个元素都是一个链表的头节点，
transient Set> entrySet;  //
final float loadFactor;  //负载因子，定义为：散列表的实际数目/散列表的容量，如果size > loadFactor*capacity，那就需要扩容了，默认是0.75，
                         //负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(n),
                         //因此，如果负载因子越大，对空间的利用率很高，然后后果就是查找效率的降低，集中表现就是对链表的迭代遍历会变慢；如果负载因子太小，那么散列表的数据过于稀疏，对空间造成
                         //严重浪费
transient int modCount;  //修改次数，由于HashMap是非线程安全的，所以如果在使用迭代器的过程中，如果有其他线程修改了map，那么将抛出ConcurrentModificationException，
                         //这就是所谓的fail-fast策略，这一实现就是在内部类迭代器中添加成员变量expectedModCount来记录当前的modCount，然后再迭代的过程中判断modCount和expectedModCount    
                         //是否相等，不相等就表明有其他线程修改了该map

常用方法解析

1.construct
public HashMap();  //构建一个初始容量为16，负载因子为0.75的HashMap
public HashMap(int initialCapacity);  //构建一个初始容量为initialCapacity，负载因子为0.75的HashMap
public HashMap(int innitialCapacity,floadloadFactor);  //指定初始容量和负载因子创建一个HashMap

2.put
  public V put(K key,V value){
    return putVal(hash(key),key,value,false,true);  //调用putVal方法
  }

  public V putVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict);
  //1.若table是否为空或者长度为0，则调用resize()方法，则给数组(table)重设大小
  //2.否则获取table的长度n，并(n-1)&hash获得该元素在table中的索引，并获取当前索引位置的元素p，若该元素为空，则直接将新元素放在table上
      并且如果(++size > threshold) = true，那么调用resize()方法，重置数组大小，并返回null(因为该索引处没有节点，所以为null)，方法结束
  //3.否则的话，若(p.hash == hash && ((k=p.key)==key || (key!=null && key.equals(k))))，这个判断语句是在判断原索引上的key和要插入的key是否是同一个key，
      如果是的话，则赋值为临时变量e
  //4.否则说明要遍历以p为链表头节点的链表，遍历过程中每个节点的key都要判断和新增的key是否一样，若一样，赋值给临时变量e
  //5.否则，将当前的key和value构造成一个Node对象，然后从这个链表的头节点前插入
  //6.注意还没结束，e!=null为true(e相当于是旧值)，则返回e.value
  //7.否则 如果(++size > threshold) = true，那么调用resize()方法，重置数组大小，并返回null(因为该索引处没有节点，所以为null)，方法结束
  //注意：1)这里获取key所在table中的索引值算法，请看这个：http://pengranxiang.iteye.com/blog/543893
          2)如果链表过长，会将链表转换成红黑树

3.final Node[] resize();
  //1.若oldCap(原来数组的大小)大于MAXIMUM_CAPACITY,也就是超过最大值，那就没办法了，随你去碰撞了
  //2.否则：newCap = oldCap<<1，扩大2倍

4.remove
  public V remove(Object key){
     Node e;
     reutrn (e = removeNode(hash(key),key,null,false,true)) == null ? null : e.value;
  }

  final Node removeNode(int hash,Object key,Object value,boolean matchValue,movable);
  //1.若table==null || table.length<=0，则直接返回null，方法结束
  //2.否则：通过((n=table.length-1) & hash)获取到该key所在数组中的索引，并将该索引处的元素赋值给p，
      若(p.hash=hash && ((k=p.key)==key || (key !=null && key.equals(k)))) = true，说明该索引所在的位置正在是要删除的节点，然后将该节点赋值给临时变量node
  //3.否则：遍历以p为头节点的链表，找到对应的节点，然后赋值给临时变量node，将node的前一个节点赋值给p
  //注意：node是要删除的节点，p是node的前一个节点(如果node是链表的头节点，那么p=null)，链表的具体操作可以看这个方法

Map--HashTable
HashTable也是Map的实现类，跟HashMap差不多，线程安全的
HashMap和HashTable的区别

1.HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。

2.HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了
  ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。

3.另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出
  ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和
  Iterator的区别。

4.由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。

5.HashMap不能保证随着时间的推移Map中的元素次序是不变的。

小总结：

参考：HashMap
HashMap底层算法解析
HashMap
HashTable的区别