你的位置:首页 > Java教程

[Java教程]给jdk写注释系列之jdk1.6容器


工作中经常听到别人讲“容器”,各种各样的容器,话说到底什么是容器,通俗的讲“容器就是用来装东西的器皿,比如:水桶就是用来盛水的,水桶就是一个容器。”
ok,在我们写程序的时候常常要对大量的对象进行管理,比如查询,遍历,修改等。jdk为我们提供的容器位于java.util包,也是我们平时用的最多的包之一。
但是为什么不用数组(其实也不是不用,只是不直接用)呢,因为数组的长度需要提前确定,而且不能改变大小,用起来手脚受限嘛。
 
下面步入正题,首先我们想,一个对象管理容器需要哪些功能?增加,删除,修改,查询(crud对不对?)还有呢?遍历,容量,是否包含某个元素。。。
功能是有了,如果让你自己实现一个这样的容器该怎么实现呢?
 
我们看看ArrayList是怎么实现这些功能的。
 
1.底层存储
  顾名思义哈,ArrayList就是用数组实现的List容器,既然是用数组实现,当然底层用数组来保存数据啦。。。
1 private transient Object[] elementData;2 private int size;

  可以看到用一个Object数组来存储数据,用一个int值来计数,记录当前容器的数据大小。


 
  另外,细心的人会发现elementData数组是使用transient修饰的,关于transient关键字的作用简单说就是java自带默认机制进行序列化的时候,被其修饰的属性不需要维持。会不会产生一点疑问?elementData不需要维持,那么怎么进行反序列化,又怎么保证序列化和反序列化数据的正确性?难道不需要存储?用大腿想一下那当然是不可以的嘛,既然需要存储,它是怎么实现的呢?注意上面红色加粗的地方,默认序列化机制,嗯哼想明白了ArrayList一定是使用了自定义的序列化方式,到底是不是这样的呢?看下面两个方法:
 1   /** 2    * Save the state of the <tt>ArrayList</tt> instance to a stream (that 3    * is, serialize it). 4    * 5    * @serialData The length of the array backing the <tt>ArrayList </tt> 6    *       instance is emitted (int), followed by all of its elements 7    *       (each an <tt>Object</tt> ) in the proper order. 8   */ 9   private void writeObject(java.io.ObjectOutputStream s)10     throws java.io.IOException{11     // Write out element count, and any hidden stuff12     int expectedModCount = modCount ;13     s.defaultWriteObject();14 15     // Write out array length16     s.writeInt( elementData.length );17 18     // Write out all elements in the proper order.19     for (int i=0; i<size; i++)20       s.writeObject( elementData[i]);21 22     if (modCount != expectedModCount) {23       throw new ConcurrentModificationException();24     }25 26   }27 28   /**29    * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,30    * deserialize it).31   */32   private void readObject(java.io.ObjectInputStream s)33     throws java.io.IOException, ClassNotFoundException {34     // Read in size, and any hidden stuff35     s.defaultReadObject();36 37     // Read in array length and allocate array38     int arrayLength = s.readInt();39     Object[] a = elementData = new Object[arrayLength];40 41     // Read in all elements in the proper order.42     for (int i=0; i<size; i++)43       a[i] = s.readObject();44   }

  英语注释很详细,也很容易读懂,就不进行翻译了。那么想一下为什么要这样设计呢,岂不是很麻烦。下面简单进行解释下:


  elementData 是一个数据存储数组,而数组是定长的,它会初始化一个容量,等容量不足时再扩充容量(扩容方式为数据拷贝,后面会详细解释),再通俗一点说就是比如elementData 的长度是10,而里面只保存了3个对象,那么数组中其余的7个元素(null)是没有意义的,所以也就不需要保存,以节省序列化后的内存容量,好了到这里就明白了这样设计的初衷和好处,顺便好像也明白了长度单独用一个int变量保存,而不是直接使用elementData.length的原因。
 
2.构造方法  
 1   /** 2    * 构造一个具有指定容量的list 3   */ 4   public ArrayList( int initialCapacity) { 5     super(); 6     if (initialCapacity < 0) 7       throw new IllegalArgumentException( "Illegal Capacity: " + 8                         initialCapacity); 9     this.elementData = new Object[initialCapacity];10   }11 12   /**13    * 构造一个初始容量为10的list14   */15   public ArrayList() {16     this(10);17   }18 19   /**20    * 构造一个包含指定元素的list,这些元素的是按照Collection的迭代器返回的顺序排列的21   */22   public ArrayList(Collection<? extends E> c) {23     elementData = c.toArray();24     size = elementData .length;25     // c.toArray might (incorrectly) not return Object[] (see 6260652)26     if (elementData .getClass() != Object[].class)27      elementData = Arrays.copyOf( elementData, size , Object[].class);28   }


  构造方法看完了,想一下指定容量的构造方法的意义,既然默认为10就可以那么为什么还要提供一个可以指定容量大小的构造方法呢?在这里说好像有点太早,那就卖个关子,下面再说。。。
 
3.增加
 1   /** 2    * 添加一个元素 3   */ 4   public boolean add(E e) { 5    // 进行扩容检查 6    ensureCapacity( size + 1); // Increments modCount 7    // 将e增加至list的数据尾部,容量+1 8     elementData[size ++] = e; 9     return true;10   }11 12   /**13    * 在指定位置添加一个元素14   */15   public void add(int index, E element) {16     // 判断索引是否越界,这里会抛出多么熟悉的异常。。。17     if (index > size || index < 0)18      throw new IndexOutOfBoundsException(19        "Index: "+index+", Size: " +size);20 21    // 进行扩容检查22    ensureCapacity( size+1); // Increments modCount 23    // 对数组进行复制处理,目的就是空出index的位置插入element,并将index后的元素位移一个位置24    System. arraycopy(elementData, index, elementData, index + 1,25            size - index);26    // 将指定的index位置赋值为element27     elementData[index] = element;28    // list容量+129     size++;30   }31   /**32    * 增加一个集合元素33   */34   public boolean addAll(Collection<? extends E> c) {35    //将c转换为数组36    Object[] a = c.toArray();37     int numNew = a.length ;38    //扩容检查39    ensureCapacity( size + numNew); // Increments modCount40    //将c添加至list的数据尾部41     System. arraycopy(a, 0, elementData, size, numNew);42    //更新当前容器大小43     size += numNew;44     return numNew != 0;45   }46   /**47    * 在指定位置,增加一个集合元素48   */49   public boolean addAll(int index, Collection<? extends E> c) {50     if (index > size || index < 0)51      throw new IndexOutOfBoundsException(52        "Index: " + index + ", Size: " + size);53 54    Object[] a = c.toArray();55     int numNew = a.length ;56    ensureCapacity( size + numNew); // Increments modCount57 58    // 计算需要移动的长度59     int numMoved = size - index;60    // 数组复制,空出第index到index+numNum个位置61     if (numMoved > 0)62      System. arraycopy(elementData, index, elementData, index + numNew,63              numMoved);64 65    // 将要插入的集合元素复制到数组空出的位置中66     System. arraycopy(a, 0, elementData, index, numNew);67     size += numNew;68     return numNew != 0;69   }70 71   /**72    * 数组容量检查,不够时则进行扩容73   */74  public void ensureCapacity( int minCapacity) {75     modCount++;76    // 当前数组的长度77     int oldCapacity = elementData .length;78    // 最小需要的容量大于当前数组的长度则进行扩容79     if (minCapacity > oldCapacity) {80      Object oldData[] = elementData;81      // 新扩容的数组长度为旧容量的1.5倍+182      int newCapacity = (oldCapacity * 3)/2 + 1;83      // 如果新扩容的数组长度还是比最小需要的容量小,则以最小需要的容量为长度进行扩容84      if (newCapacity < minCapacity)85        newCapacity = minCapacity;86       // minCapacity is usually close to size, so this is a win:87       // 进行数据拷贝,Arrays.copyOf底层实现是System.arrayCopy()88       elementData = Arrays.copyOf( elementData, newCapacity);89     }90   }

 


4.删除
 1   /** 2    * 根据索引位置删除元素 3   */ 4   public E remove( int index) { 5    // 数组越界检查 6     RangeCheck(index); 7  8     modCount++; 9    // 取出要删除位置的元素,供返回使用10    E oldValue = (E) elementData[index];11    // 计算数组要复制的数量12     int numMoved = size - index - 1;13    // 数组复制,就是将index之后的元素往前移动一个位置14     if (numMoved > 0)15      System. arraycopy(elementData, index+1, elementData, index,16              numMoved);17    // 将数组最后一个元素置空(因为删除了一个元素,然后index后面的元素都向前移动了,所以最后一个就没用了),好让gc尽快回收18    // 不要忘了size减一19     elementData[--size ] = null; // Let gc do its work20 21     return oldValue;22   }23 24   /**25    * 根据元素内容删除,只删除匹配的第一个26   */27   public boolean remove(Object o) {28    // 对要删除的元素进行null判断29    // 对数据元素进行遍历查找,知道找到第一个要删除的元素,删除后进行返回,如果要删除的元素正好是最后一个那就惨了,时间复杂度可达O(n) 。。。30     if (o == null) {31       for (int index = 0; index < size; index++)32        // null值要用==比较33        if (elementData [index] == null) {34          fastRemove(index);35          return true;36        }37    } else {38      for (int index = 0; index < size; index++)39        // 非null当然是用equals比较了40        if (o.equals(elementData [index])) {41          fastRemove(index);42          return true;43        }44     }45     return false;46   }47 48   /*49    * Private remove method that skips bounds checking and does not50    * return the value removed.51   */52   private void fastRemove(int index) {53     modCount++;54    // 原理和之前的add一样,还是进行数组复制,将index后的元素向前移动一个位置,不细解释了,55     int numMoved = size - index - 1;56     if (numMoved > 0)57       System. arraycopy(elementData, index+1, elementData, index,58                numMoved);59     elementData[--size ] = null; // Let gc do its work60   }61 62   /**63    * 数组越界检查64   */65   private void RangeCheck(int index) {66     if (index >= size )67      throw new IndexOutOfBoundsException(68        "Index: "+index+", Size: " +size);69   }

  PS:看到了这个方法,便可jdk源码有些地方写的也不是那么精巧,比如这里remove时将数组越界检查封装成了一个单独方法,可是往前翻一下add方法中的数组越界就没有进行封装,需要检查的时候都是写一遍一样的代码,why啊。。。


 
  增加和删除方法到这里就解释完了,代码是很简单,主要需要特别关心的就两个地方:1.数组扩容,2.数组复制,这两个操作都是极费效率的,最惨的情况下(添加到list第一个位置,删除list最后一个元素或删除list第一个索引位置的元素)时间复杂度可达O(n)。
  还记得上面那个坑吗(为什么提供一个可以指定容量大小的构造方法 )?看到这里是不是有点明白了呢,简单解释下:如果数组初试容量过小,假设默认的10个大小,而我们使用ArrayList的主要操作时增加元素,不断的增加,一直增加,不停的增加,会出现上面后果?那就是数组容量不断的受挑衅,数组需要不断的进行扩容,扩容的过程就是数组拷贝System.arraycopy的过程,每一次扩容就会开辟一块新的内存空间和数据的复制移动,这样势必对性能造成影响。那么在这种以写为主(写会扩容,删不会缩容)场景下,提前预知性的设置一个大容量,便可减少扩容的次数,提高了性能。
 
 待续。。。