现在的位置: 首页 > 综合 > 正文

JDK源代码分析聚集篇——-Collection(文明人应该排队)

2018年03月29日 ⁄ 综合 ⁄ 共 8686字 ⁄ 字号 评论关闭
Java中Collection一直都是一个庞大的家族,他们错综复杂,而又功能强大,在什么时候采用什么样的类型也是一个十分讲究的问题,现在我们先来看看Collection家族的族谱

URD的操作委托给了Iteartor接口,这就是大名鼎鼎的迭代器模式;

ArrayList是首先开始着手细节实现的,我们从他开始看:

private transient Object[] elementData;
可见在聚集内部是利用数组实现的,数组和聚集的区别就在于,我们对于数组必须在初始化的时候就开始

指定其容量,而我们对于聚集则可以不必,为什么可以不用呢?

  1. private int size;
  2.     public ArrayList(int initialCapacity) {
  3.     super();
  4.         if (initialCapacity < 0)
  5.             throw new IllegalArgumentException("Illegal Capacity: "+
  6.                                                initialCapacity);
  7.     this.elementData = new Object[initialCapacity];
  8.     }

实例化的时候初始化容积;

  1.     public ArrayList() {
  2.     this(10);
  3.     }

不指定初始化容积的时候为10,可见如果我们的元素自认为是小于10的话,那么我们可以指定不指定容积

,否则的话,最好指定,不然会带来性能上的损耗;

  1.  public void trimToSize() {
  2.     modCount++;
  3.     int oldCapacity = elementData.length;
  4.     if (size < oldCapacity) {
  5.             elementData = Arrays.copyOf(elementData, size);
  6.     }
  7.     }

modCount为修改次数;减去一些不存在的值;

  1.  public void ensureCapacity(int minCapacity) {
  2.     modCount++;
  3.     int oldCapacity = elementData.length;
  4.     if (minCapacity > oldCapacity) {
  5.         Object oldData[] = elementData;
  6.         int newCapacity = (oldCapacity * 3)/2 + 1;
  7.             if (newCapacity < minCapacity)
  8.         newCapacity = minCapacity;
  9.             // minCapacity is usually close to size, so this is a win:
  10.             elementData = Arrays.copyOf(elementData, newCapacity);
  11.     }
  12.     }

指定一个最小容积,如果当前容量小于最小容积,则试着扩大1.5倍(扩展因子)如果扩展侯还小于最小容积,那么就扩大容积到该最小容积,并且多出来的值会使用默认值填充;

  1.  public Object clone() {
  2.     try {
  3.         ArrayList<E> v = (ArrayList<E>) super.clone();
  4.         v.elementData = Arrays.copyOf(elementData, size);
  5.         v.modCount = 0;
  6.         return v;
  7.     } catch (CloneNotSupportedException e) {
  8.         // this shouldn't happen, since we are Cloneable
  9.         throw new InternalError();
  10.     }
  11.     }

克隆唯一的不同就是把修改次数给重置了;

  1.     public Object[] toArray() {
  2.         return Arrays.copyOf(elementData, size);
  3.     }

copyOf是1.6新增的方法,他返回的是一个新的深层次的拷贝;

他的查找方法和赋值方法都是数组的实现,关键的在于其的增加和删除等等方法,如果自动的扩展容量;

  1.     public boolean add(E e) {
  2.     ensureCapacity(size + 1);  // Increments modCount!!
  3.     elementData[size++] = e;
  4.     return true;
  5.     }

首先得保证容量没有溢出:

  1.     public void ensureCapacity(int minCapacity) {
  2.     modCount++;
  3.     int oldCapacity = elementData.length;
  4.     if (minCapacity > oldCapacity) {
  5.         Object oldData[] = elementData;
  6.         int newCapacity = (oldCapacity * 3)/2 + 1;
  7.             if (newCapacity < minCapacity)
  8.         newCapacity = minCapacity;
  9.             // minCapacity is usually close to size, so this is a win:
  10.             elementData = Arrays.copyOf(elementData, newCapacity);
  11.     }
  12.     }

一般来说当容量不够的时候会扩展1.5倍;

从这里我们可以看出容量和Size的不同
elementData[size++] = e;
上面增加容量的时候,容量已经扩展到了原来的1.5倍,但是我们的size没有变,size变化的条件是增加或者删除一个元素的时候+1或者-1,用户无法指定的,他是该聚集中实实在在存在的元素的个数;刚才是从末尾增加一个元素,下面是从中间增加一个元素,那么这个元素以后的其他元素应该往后挪动一位;

  1.    public void add(int index, E element) {
  2.     if (index > size || index < 0)
  3.         throw new IndexOutOfBoundsException(
  4.         "Index: "+index+", Size: "+size);
  5.     ensureCapacity(size+1);  // Increments modCount!!
  6.     System.arraycopy(elementData, index, elementData, index + 1,
  7.              size - index); //挪动一位;
  8.     elementData[index] = element;   //插入一个新的元素;
  9.     size++;                         //增加当前元素的个数;
  10.     }

下面是修改的方法:

  1.  public E remove(int index) {
  2.     RangeCheck(index);   //判断索引位置是否溢出;
  3.     modCount++;          //增加修改次数
  4.     E oldValue = (E) elementData[index];   //保存被删除的元素,以待返回而不被垃圾回收
  5.     int numMoved = size - index - 1;
  6.     if (numMoved > 0)
  7.         System.arraycopy(elementData, index+1, elementData, index,
  8.                  numMoved);  //往前挪动
  9.     elementData[--size] = null// Let gc do its work  //那么最后的元素不能还存在,那么
  10. 置成空的等待回收
  11.     return oldValue;
  12.     }

Vector和ArrayList最大的不同就是:
1)vector是线程安全的,其操作基本上都带这Synchronized的表示哦
2)

  1.    public synchronized void setSize(int newSize) {
  2.     modCount++;
  3.     if (newSize > elementCount) {
  4.         ensureCapacityHelper(newSize);
  5.     } else {
  6.         for (int i = newSize ; i < elementCount ; i++) {
  7.         elementData[i] = null;
  8.         }
  9.     }
  10.     elementCount = newSize;
  11.     }

我们开始在ArrayList中说了size不是用户能自定义的,那么在Vector中就可以;如果size比当前elementCount大,那么就会扩展这个数组,并且用null来填充;可以理解为一次性加多个null元素;

  1.     public synchronized int capacity() {
  2.     return elementData.length;
  3.     }

capacity还是和ArrayList一样,是容量;但是vector暴露出来了

  1.     public synchronized int size() {
  2.     return elementCount;
  3.     }

当前的元素个数,其中包括setSize的null值元素;我想在ArrayList中不把setSize和capacity暴露出来,主要也是为了考虑线程安全;

3)其含有一个Enumeration操作,能够返回一个遍历的枚举
 

  1. public Enumeration<E> elements() {
  2.     return new Enumeration<E>() {
  3.         int count = 0;
  4.         public boolean hasMoreElements() {
  5.         return count < elementCount;
  6.         }
  7.         public E nextElement() {
  8.         synchronized (Vector.this) {
  9.             if (count < elementCount) {
  10.             return (E)elementData[count++];
  11.             }
  12.         }
  13.         throw new NoSuchElementException("Vector Enumeration");
  14.         }
  15.     };
  16.     }

枚举和开始的迭代器区别主要在于枚举是线程安全的;

4)可以指定capacityIncrement,当增加元素时不够。则增加这么空间,如果不指定,那么是增加两倍,而不是1.5

  1.  private void ensureCapacityHelper(int minCapacity) {
  2.     int oldCapacity = elementData.length;
  3.     if (minCapacity > oldCapacity) {
  4.         Object[] oldData = elementData;
  5.         int newCapacity = (capacityIncrement > 0) ?
  6.         (oldCapacity + capacityIncrement) : (oldCapacity * 2);
  7.             if (newCapacity < minCapacity) {
  8.         newCapacity = minCapacity;
  9.         }
  10.             elementData = Arrays.copyOf(elementData, newCapacity);
  11.     }
  12.     }

当setSize的时候,最先是增加capacityIncrement或者两倍,如果不够的话,那么就增加到新的size,就一位这下一次就算再添加一个元素,也会再加上capacityIncrement或者两倍;'

接下来我们来看LinkedList,以上两种List都是根据数组来实现的,我们知道数组最大的好处就是随机访问,在内存中,我们可以根据数组起始位置和索引能够很快的定位到一个元素,而我们增删元素,尤其是在中间增删的时候,我们不得不把元素挪动,这个工程是十分巨大的;

下面我们来看下LinkedList的实现,首先他定义了节点:

  1.  private static class Entry<E> {
  2.     E element;
  3.     Entry<E> next;
  4.     Entry<E> previous;
  5.     Entry(E element, Entry<E> next, Entry<E> previous) {
  6.         this.element = element;
  7.         this.next = next;
  8.         this.previous = previous;
  9.     }
  10.     }

这个节点是一个双向节点,既有头也有尾;

  1.  private transient Entry<E> header = new Entry<E>(nullnullnull);
  2.     private transient int size = 0;

初始化的时候就只有一个空的头;

  1.   public LinkedList() {
  2.         header.next = header.previous = header;
  3.     }

都指向其本身,形成一个环;

  1.  public E getFirst() {
  2.     if (size==0)
  3.         throw new NoSuchElementException();
  4.     return header.next.element;
  5.     }

拿到第一个元素,可见初始化的那个头是一个标记,是不含元素的;

  1.   public E getLast()  {
  2.     if (size==0)
  3.         throw new NoSuchElementException();
  4.     return header.previous.element;
  5.     }

用这个空的Entry连接了头和尾,这样我们就可以轻松的从两头开始遍历,而这个header的引用成为了这个环的分界点;
下面是对表头表尾的操作:
插入节点:

  1.     private Entry<E> addBefore(E e, Entry<E> entry) {
  2.     Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
  3.     newEntry.previous.next = newEntry;
  4.     newEntry.next.previous = newEntry;
  5.     size++;
  6.     modCount++;
  7.     return newEntry;
  8.     }

  1. public E removeFirst() {
  2.     return remove(header.next);
  3.     }
  4.     
  5.     public E removeLast() {
  6.     return remove(header.previous);
  7.     }
  8.    aram e the element to add
  9.      */
  10.     public void addFirst(E e) {
  11.     addBefore(e, header.next);
  12.     }
  13.   
  14.     public void addLast(E e) {
  15.     addBefore(e, header);
  16.     }

有了header的双向连接,十分方便;

  1.  public boolean add(E e) {
  2.     addBefore(e, header);
  3.         return true;
  4.     }

相当于在链表末尾添加节点,和addLast一样;
移除节点:

  1. private E remove(Entry<E> e) {
  2.     if (e == header)
  3.         throw new NoSuchElementException();   //头肯定是不能移除的
  4.         E result = e.element;
  5.     e.previous.next = e.next;
  6.     e.next.previous = e.previous;
  7.         e.next = e.previous = null;         //方便垃圾回收啦;
  8.         e.element = null;                   //这样的移除我们可以不用挪动整个队列了
  9.     size--;
  10.     modCount++;
  11.         return result;
  12.     }

克隆方法:

  1.     public Object clone() {
  2.         LinkedList<E> clone = null;
  3.     try {
  4.         clone = (LinkedList<E>) super.clone();
  5.     } catch (CloneNotSupportedException e) {
  6.         throw new InternalError();
  7.     }
  8.         // Put clone into "virgin" state
  9.         clone.header = new Entry<E>(nullnullnull);
  10.         clone.header.next = clone.header.previous = clone.header;
  11.         clone.size = 0;
  12.         clone.modCount = 0;
  13.         // Initialize clone with our elements
  14.         for (Entry<E> e = header.next; e != header; e = e.next)
  15.             clone.add(e.element);
  16.         return clone;
  17.     }

注意,是浅克隆;
clone.add(e.element):其中,element没有变化;

  1. package org.corey.demo;
  2. public class Person {
  3.     private String name;
  4.     public Person(String name) {
  5.         super();
  6.         this.name = name;
  7.     }
  8.     public String getName() {
  9.         return name;
  10.     }
  11.     public void setName(String name) {
  12.         this.name = name;
  13.     }
  14. }
  15. public class Test {
  16.     /**
  17.      * @param args
  18.      */
  19.     public static void main(String[] args) {
  20.       Person p1=new Person("corey");
  21.       LinkedList l=new  LinkedList();
  22.       l.add(p1);
  23.       LinkedList l2=(LinkedList)l.clone();
  24.       ((Person)l.get(0)).setName("syna");
  25.       System.out.println(((Person)l2.get(0)).getName());
  26.     }
  27. }

打印syna;

这一点倒是list都是相同的;ArrayList等也一样;这一下,我们对List是不是有一定的了解,这些主要涉及到数据结构,是很好的学习材料;

抱歉!评论已关闭.