Java-Collections Framework学习与总结-ArrayList

        工作中经常会用到Java的集合类,最近不忙了,把相关知识总结一下,便于理解记忆。
        打开java.util.ArrayList的源代码,首先映入眼帘的是@author  Josh Bloch(相对于源码,本人更喜欢看故事 ,每次看到一份源码,先看看作者是谁。然后搜索一下作者的百科以及一些八卦。。。以及与作者相关的人的百科和一些八卦。。。以及。。。一上午就过去了 ),这家伙是谁?。。。看过Effective Java的人一定会惊呼:这不就是。。。 没错,这位大叔就是玉树凌风,风流倜傥,人称Java之母的Josh Bloch ,Collections Framework就是他一手打造的,后来去google做了Java首席架构师。
        言归正传,不过话又说回来,有说Collections Framework是参考了Doug Lea大叔的Collections。。。有兴趣的可以去看看相关源码,总之他们都很牛逼就对了。
        继续吧,看一个类的时候首先要看看这个类能干什么,有什么特性。这些都可以在这个类实现的接口上体现了(废话。。。)。好,直接从最顶级的接口看吧。首先是接口java.lang.Iterable:
Java代码   收藏代码
  1. package java.lang;  
  2. import java.util.Iterator;  
  3.   
  4. public interface Iterable<T> {  
  5.     Iterator<T> iterator();  
  6. }  

        由于篇幅的关系,去掉了注释。注释上说明,实现了这个接口的类,可以使用"foreach"语法。

        接下来是接口java.util.Collection:
Java代码   收藏代码
  1. package java.util;  
  2. public interface Collection<E> extends Iterable<E> {  
  3.     int size();  
  4.     boolean isEmpty();  
  5.     boolean contains(Object o);  
  6.     Iterator<E> iterator();  
  7.     Object[] toArray();  
  8.     <T> T[] toArray(T[] a);  
  9.     boolean add(E e);  
  10.     boolean remove(Object o);  
  11.     boolean containsAll(Collection<?> c);  
  12.     boolean addAll(Collection<? extends E> c);  
  13.     boolean removeAll(Collection<?> c);  
  14.     boolean retainAll(Collection<?> c);  
  15.     void clear();  
  16.     boolean equals(Object o);  
  17.     int hashCode();  
  18. }  

        里面的注释很详细,反正大概意思是说(英语不太好),这是集合层次的顶级接口,代表了一组对象blablablabla,所有通用的实现应该提供两个"标准"的构造方法:无参的构造方法和拥有一个集合类型参数的构造方法blablablabla,总之这个接口对集合进行了高度滴、抽象滴定义:)

        接下来就是java.util.List接口了。
Java代码   收藏代码
  1. public interface List<E> extends Collection<E> {  
  2.     //和Collection重复的方法就不贴了,但必须知道有这些方法  
  3.     boolean addAll(int index, Collection<? extends E> c);  
  4.     E get(int index);  
  5.     E set(int index, E element);  
  6.     void add(int index, E element);  
  7.     E remove(int index);  
  8.     int indexOf(Object o);  
  9.     int lastIndexOf(Object o);  
  10.     ListIterator<E> listIterator();  
  11.     ListIterator<E> listIterator(int index);  
  12.     List<E> subList(int fromIndex, int toIndex);  
  13. }  

        list代表了一个有序的集合,可以通过index来访问和查找集合内的元素,集合内元素是可重复的,因为index(集合中的位置)不同。

        还有一个ArrayList实现的接口是java.util.RandomAccess:
Java代码   收藏代码
  1. package java.util;  
  2. public interface RandomAccess {  
  3. }  

         一看没有方法的接口,就知道这大概是个标记接口喽。实现这个接口的集合类会在随机访问元素上提供很好的性能。比如说,ArrayList实现了RandomAccess而LinkedList没有,那么当我们拿到一个集合时(假设这个集合不是ArrayList就是LinkedList),如果这个集合时ArrayList,那么我们遍历集合元素可以使用下标遍历,如果是LinkedList,就使用迭代器遍历。比如集合工具类Collections中提供的对集合中元素进行二分查找的方法,代码片段如下:
Java代码   收藏代码
  1. public static <T>  
  2.     int binarySearch(List<? extends Comparable<? super T>> list, T key) {  
  3.         if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)  
  4.             return Collections.indexedBinarySearch(list, key);  
  5.         else  
  6.             return Collections.iteratorBinarySearch(list, key);  
  7.     }  

        还有java.lang.Cloneable和java.io.Serializable两个标记接口,表示ArrayList是 可克隆的、可序列化的。

        还要看一下AbstractCollection和AbstractList,这两个抽象类里实现了一部分公共的功能,代码都还比较容易看懂。

        需要注意的地方是AbstractList中的一个属性modCount。这个属性主要由集合的迭代器来使用,对于List来说,可以调用iterator()和listIterator()等方法来生成一个迭代器,这个迭代器在生成时会将List的modCount保存起来(迭代器实现为List的内部类),在迭代过程中会去检查当前list的modCount是否发生了变化(和自己保存的进行比较),如果发生变化,那么马上抛出java.util.ConcurrentModificationException异常,这种行为就是fail-fast。

        好了,终于可以看ArrayList了,在看之前可以先思考一下,如果我们自己来实现ArrayList,要怎么实现。我们都会把ArrayList简单的看作动态数组,说明我们使用它的时候大都是当做数组来使用的,只不过它的长度是可改变的。那我们的问题就变成了一个实现长度可变化的数组的问题了。那么首先,我们会用一个数组来做底层数据存储的结构,新建的时候会提供一个默认的数组长度。当我们添加或删除元素的时候,会改变数据的长度(当默认长度不够或者其他情况下),这里涉及到数据的拷贝,我们可以使用系统提供的System.arraycopy来进行数组拷贝。如果我们每次添加或者删除元素时都会因为改变数组长度而拷贝数组,那也太2了,可以在当数组长度不够的时候,扩展一定的空间,比如可以扩展到原来的2倍,这样会提高一点性能(如果不是在数组末尾添加或删除元素的话,还是会进行数组拷贝),但同时浪费了一点空间。再看看上面的接口,比如我们要实现size方法,那么就不能直接返回数组的长度了(由于上面的原因),也没办法去遍历数组得到长度(因为可能存在null元素),我们会想到利用一个私有变量来保存长度,在添加删除等方法里面去相应修改这个变量(这里不考虑线程安全问题,因为ArrayList本身就不是线程安全的)。

        带着这些问题,来看一下ArrayList的代码。
        首先,真正存储元素的是一个数组。
Java代码   收藏代码
  1. /** 
  2.   * The array buffer into which the elements of the ArrayList are stored. 
  3.   * The capacity of the ArrayList is the length of this array buffer. 
  4.   */  
  5.  private transient Object[] elementData;  

        那么这个数组该怎么初始化呢?数组的长度该怎么确定呢?看一下构造方法。
Java代码   收藏代码
  1. /** 
  2.   * Constructs an empty list with the specified initial capacity. 
  3.   * 
  4.   * @param   initialCapacity   the initial capacity of the list 
  5.   * @exception IllegalArgumentException if the specified initial capacity 
  6.   *            is negative 
  7.   */  
  8.  public ArrayList(int initialCapacity) {  
  9.      super();  
  10.      if (initialCapacity < 0)  
  11.          throw new IllegalArgumentException("Illegal Capacity: "+  
  12.                                             initialCapacity);  
  13.      this.elementData = new Object[initialCapacity];  
  14.  }  
  15.   
  16.  /** 
  17.   * Constructs an empty list with an initial capacity of ten. 
  18.   */  
  19.  public ArrayList() {  
  20.      this(10);  
  21.  }  

        可以看到,我们可以选择使用一个参数作为ArrayList内部数组的容量来构造一个ArrayList;或者使用无参的构造方法,这样会默认使用10作为数组容量。我们在实际应用中可以根据具体情况来选择使用哪个构造方法,例如在某种特定逻辑下,我们需要存储200个元素(固定值)到一个ArrayList里,那我们就可以使用带一个int型参数的构造方法,这样就避免了在数组长度不够,进行扩容时,内部数组的拷贝。

        当然,根据接口java.util.Collection的规范(非强制),ArrayList也提供用一个集合做为参数的构造方法。
Java代码   收藏代码
  1. /** 
  2.   * Constructs a list containing the elements of the specified 
  3.   * collection, in the order they are returned by the collection's 
  4.   * iterator. 
  5.   * 
  6.   * @param c the collection whose elements are to be placed into this list 
  7.   * @throws NullPointerException if the specified collection is null 
  8.   */  
  9.  public ArrayList(Collection<? extends E> c) {  
  10.      elementData = c.toArray();  
  11.      size = elementData.length;  
  12.      // c.toArray might (incorrectly) not return Object[] (see 6260652)  
  13.      if (elementData.getClass() != Object[].class)  
  14.          elementData = Arrays.copyOf(elementData, size, Object[].class);  
  15.  }  

        上面说到说考虑用一个私有变量来存储size(集合中实际原始的个数)。在ArrayList也有这样一个变量。
Java代码   收藏代码
  1. /** 
  2.  * The size of the ArrayList (the number of elements it contains). 
  3.  * 
  4.  * @serial 
  5.  */  
  6. private int size;  

        有了这个变量,一些方法实现起来就非常简单了。
Java代码   收藏代码
  1. /** 
  2.  * Returns the number of elements in this list. 
  3.  * 
  4.  * @return the number of elements in this list 
  5.  */  
  6. public int size() {  
  7.     return size;  
  8. }  
  9.   
  10. /** 
  11.  * Returns <tt>true</tt> if this list contains no elements. 
  12.  * 
  13.  * @return <tt>true</tt> if this list contains no elements 
  14.  */  
  15. public boolean isEmpty() {  
  16.     return size == 0;  
  17. }  
  18.   
  19. /** 
  20.  * Returns <tt>true</tt> if this list contains the specified element. 
  21.  * More formally, returns <tt>true</tt> if and only if this list contains 
  22.  * at least one element <tt>e</tt> such that 
  23.  * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>. 
  24.  * 
  25.  * @param o element whose presence in this list is to be tested 
  26.  * @return <tt>true</tt> if this list contains the specified element 
  27.  */  
  28. public boolean contains(Object o) {  
  29.     return indexOf(o) >= 0;  
  30. }  
  31.   
  32. /** 
  33.  * Returns the index of the first occurrence of the specified element 
  34.  * in this list, or -1 if this list does not contain the element. 
  35.  * More formally, returns the lowest index <tt>i</tt> such that 
  36.  * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>, 
  37.  * or -1 if there is no such index. 
  38.  */  
  39. public int indexOf(Object o) {  
  40.     if (o == null) {  
  41.         for (int i = 0; i < size; i++)  
  42.      if (elementData[i]==null)  
  43.          return i;  
  44.     } else {  
  45.         for (int i = 0; i < size; i++)  
  46.      if (o.equals(elementData[i]))  
  47.          return i;  
  48.     }  
  49.     return -1;  
  50. }  
  51.   
  52. /** 
  53.  * Returns the index of the last occurrence of the specified element 
  54.  * in this list, or -1 if this list does not contain the element. 
  55.  * More formally, returns the highest index <tt>i</tt> such that 
  56.  * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>, 
  57.  * or -1 if there is no such index. 
  58.  */  
  59. public int lastIndexOf(Object o) {  
  60.     if (o == null) {  
  61.         for (int i = size-1; i >= 0; i--)  
  62.      if (elementData[i]==null)  
  63.          return i;  
  64.     } else {  
  65.         for (int i = size-1; i >= 0; i--)  
  66.      if (o.equals(elementData[i]))  
  67.          return i;  
  68.     }  
  69.     return -1;  
  70. }  

        由于内部数组的存在,一些基于下标的方法实现起来也非常简单。
Java代码   收藏代码
  1. /** 
  2.     * Returns the element at the specified position in this list. 
  3.     * 
  4.     * @param  index index of the element to return 
  5.     * @return the element at the specified position in this list 
  6.     * @throws IndexOutOfBoundsException {@inheritDoc} 
  7.     */  
  8.    public E get(int index) {  
  9.        RangeCheck(index);  
  10.   
  11.        return (E) elementData[index];  
  12.    }  
  13.   
  14.    /** 
  15.     * Replaces the element at the specified position in this list with 
  16.     * the specified element. 
  17.     * 
  18.     * @param index index of the element to replace 
  19.     * @param element element to be stored at the specified position 
  20.     * @return the element previously at the specified position 
  21.     * @throws IndexOutOfBoundsException {@inheritDoc} 
  22.     */  
  23.    public E set(int index, E element) {  
  24.        RangeCheck(index);  
  25.   
  26.        E oldValue = (E) elementData[index];  
  27.        elementData[index] = element;  
  28.        return oldValue;  
  29.    }  
  30.   
  31.    /** 
  32.     * Appends the specified element to the end of this list. 
  33.     * 
  34.     * @param e element to be appended to this list 
  35.     * @return <tt>true</tt> (as specified by {@link Collection#add}) 
  36.     */  
  37.    public boolean add(E e) {  
  38.        ensureCapacity(size + 1);  // Increments modCount!!  
  39.        elementData[size++] = e;  
  40.        return true;  
  41.    }  
  42.   
  43.    /** 
  44.     * Inserts the specified element at the specified position in this 
  45.     * list. Shifts the element currently at that position (if any) and 
  46.     * any subsequent elements to the right (adds one to their indices). 
  47.     * 
  48.     * @param index index at which the specified element is to be inserted 
  49.     * @param element element to be inserted 
  50.     * @throws IndexOutOfBoundsException {@inheritDoc} 
  51.     */  
  52.    public void add(int index, E element) {  
  53.        if (index > size || index < 0)  
  54.           throw new IndexOutOfBoundsException(  
  55.            "Index: "+index+", Size: "+size);  
  56.   
  57.        ensureCapacity(size+1);  // Increments modCount!!  
  58.        System.arraycopy(elementData, index, elementData, index + 1,  
  59.                 size - index);  
  60.        elementData[index] = element;  
  61.        size++;  
  62.    }  
  63.   
  64.    /** 
  65.     * Removes the element at the specified position in this list. 
  66.     * Shifts any subsequent elements to the left (subtracts one from their 
  67.     * indices). 
  68.     * 
  69.     * @param index the index of the element to be removed 
  70.     * @return the element that was removed from the list 
  71.     * @throws IndexOutOfBoundsException {@inheritDoc} 
  72.     */  
  73.    public E remove(int index) {  
  74.        RangeCheck(index);  
  75.   
  76.        modCount++;  
  77.        E oldValue = (E) elementData[index];  
  78.   
  79.        int numMoved = size - index - 1;  
  80.        if (numMoved > 0)  
  81.            System.arraycopy(elementData, index+1, elementData, index,  
  82.                     numMoved);  
  83.        elementData[--size] = null// Let gc do its work  
  84.   
  85.        return oldValue;  
  86.    }  

        有几个要注意的地方,首先是RangeCheck方法,顾名思义是做边界检查的,看看方法实现。
Java代码   收藏代码
  1. /** 
  2.   * Checks if the given index is in range.  If not, throws an appropriate 
  3.   * runtime exception.  This method does *not* check if the index is 
  4.   * negative: It is always used immediately prior to an array access, 
  5.   * which throws an ArrayIndexOutOfBoundsException if index is negative. 
  6.   */  
  7.  private void RangeCheck(int index) {  
  8.      if (index >= size)  
  9.          throw new IndexOutOfBoundsException(  
  10.       "Index: "+index+", Size: "+size);  
  11.  }  

         异常信息是不是很眼熟,呵呵。

         还有就是在"添加"方法中的ensureCapacity方法,上面也考虑到扩容的问题,这个方法其实就干了这件事情。
Java代码   收藏代码
  1. /** 
  2.  * Increases the capacity of this <tt>ArrayList</tt> instance, if 
  3.  * necessary, to ensure that it can hold at least the number of elements 
  4.  * specified by the minimum capacity argument. 
  5.  * 
  6.  * @param   minCapacity   the desired minimum capacity 
  7.  */  
  8. public void ensureCapacity(int minCapacity) {  
  9.     modCount++;  
  10.     int oldCapacity = elementData.length;  
  11.     if (minCapacity > oldCapacity) {  
  12.         Object oldData[] = elementData;  
  13.         int newCapacity = (oldCapacity * 3)/2 + 1;  
  14.         if (newCapacity < minCapacity)  
  15.                newCapacity = minCapacity;  
  16.         // minCapacity is usually close to size, so this is a win:  
  17.         elementData = Arrays.copyOf(elementData, newCapacity);  
  18.     }  
  19. }  

        注意当数组长度不够的时候,会进行数组的扩展,扩展到原来长度的1.5倍(注意整型的除法)加1,比如原来是2,会扩展到4,原来是30,会扩展到46。当数组的长度大到算出的新容量超出了整型最大范围,那么新容量就等于传入的"最小容量"。

        最后再看一下另一个删除方法。
Java代码   收藏代码
  1. /** 
  2.  * Removes the first occurrence of the specified element from this list, 
  3.  * if it is present.  If the list does not contain the element, it is 
  4.  * unchanged.  More formally, removes the element with the lowest index 
  5.  * <tt>i</tt> such that 
  6.  * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt> 
  7.  * (if such an element exists).  Returns <tt>true</tt> if this list 
  8.  * contained the specified element (or equivalently, if this list 
  9.  * changed as a result of the call). 
  10.  * 
  11.  * @param o element to be removed from this list, if present 
  12.  * @return <tt>true</tt> if this list contained the specified element 
  13.  */  
  14. public boolean remove(Object o) {  
  15.     if (o == null) {  
  16.                for (int index = 0; index < size; index++)  
  17.      if (elementData[index] == null) {  
  18.          fastRemove(index);  
  19.          return true;  
  20.      }  
  21.     } else {  
  22.         for (int index = 0; index < size; index++)  
  23.      if (o.equals(elementData[index])) {  
  24.          fastRemove(index);  
  25.          return true;  
  26.      }  
  27.            }  
  28.     return false;  
  29. }  
  30.   
  31. /* 
  32.  * Private remove method that skips bounds checking and does not 
  33.  * return the value removed. 
  34.  */  
  35. private void fastRemove(int index) {  
  36.     modCount++;  
  37.     int numMoved = size - index - 1;  
  38.     if (numMoved > 0)  
  39.         System.arraycopy(elementData, index+1, elementData, index,  
  40.                   numMoved);  
  41.     elementData[--size] = null// Let gc do its work  
  42. }  

        可以看到,像size、isEmpty、get、set这样的方法时间复杂度为O(1),而像indexOf、add、remove等方法,最坏的情况下(如添加元素到第一个位置,删除第一个位置的元素,找最后一个元素的下标等)时间复杂度为O(n)。

        一般情况下内部数组的长度总是大于集合中元素总个数的,ArrayList也提供了一个释放多余空间的方法,我们可以适时调用此方法来减少内存占用。
Java代码   收藏代码
  1. /** 
  2.  * Trims the capacity of this <tt>ArrayList</tt> instance to be the 
  3.  * list's current size.  An application can use this operation to minimize 
  4.  * the storage of an <tt>ArrayList</tt> instance. 
  5.  */  
  6. public void trimToSize() {  
  7.     modCount++;  
  8.     int oldCapacity = elementData.length;  
  9.     if (size < oldCapacity) {  
  10.                elementData = Arrays.copyOf(elementData, size);  
  11.     }  
  12. }  


        基本上ArrayList的内容总结的差不多啦。最后,别忘了它是线程不安全的。
内容概要:2025年大宗商品市场展望报告由世界银行发布,分析了能源、农业、金属和矿物、贵金属以及化肥等多个主要商品类别的市场发展前景。报告指出,由于全球经济增长放缓和贸易紧张加剧,2025年大宗商品价格预计总体下降12%,2026年进一步下降5%,达到六年来的最低点。油价预计2025年平均为每桶64美元,2026年降至60美元,主要受全球石油消费放缓和供应增加的影响。农业商品价格预计2025年基本稳定,2026年下降3%,其中粮食和原材料价格分别下降7%和2%,但饮料价格上涨20%。金属价格预计2025年下降10%,2026年再降3%,特别是铜和铝价格将显著下跌。贵金属如黄金和白银因避险需求强劲,预计价格将继续上涨。报告还特别关注了疫情后大宗商品周期的变化,指出周期变得更短、更剧烈,主要受到宏观经济冲击、极端天气事件和地缘政治冲突的影响。 适用人群:对全球经济趋势、大宗商品市场动态及其对不同经济体影响感兴趣的政策制定者、投资者、分析师及研究机构。 使用场景及目标:①帮助政策制定者评估全球经济增长放缓对大宗商品市场的影响,从而调整经济政策;②为投资者提供有关未来大宗商品价格走势的风险提示,以便进行投资决策;③协助分析师和研究机构深入理解疫情后大宗商品市场的周期特征,识别潜在的投资机会和风险。 其他说明:报告强调,全球经济增长放缓、贸易紧张加剧以及地缘政治不确定性是影响大宗商品价格的主要因素。此外,极端天气事件和能源转型也对农业和能源商品市场产生了深远影响。报告呼吁各方关注这些结构性变化,并采取相应的风险管理措施。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值