ArrayList

1.数组实现:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private transient Object[] elementData;
}

为什么不写成 private transient E[] elementData;??

默认大小

public ArrayList() {
    this(10);
}

扩容策略

在add操作中会进行扩容. 扩容策略是:新的大小是原始容量的1.5倍,如果还是不足,就参数指定的大小:

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

Arrays

排序

包含了一些操作数组的方法,如排序搜索等; 基本类型的数据排序采用快速排序,其中对于long,int,byte等整形直接调用sort1,float和double调用sort2. 一段有趣的代码,通过这个可以知道NaN和-0.0特殊性.

private static void sort2(double a[], int fromIndex, int toIndex) {
        final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
        /*
         * 排序过程分为三个阶段,目的是为了在排序的主流乘避免出现NaN和-0.0
         */

        /*
         * 阶段1 预处理过程 : 将NaN移到数组尾部,计算-0.0的数目,并将-0.0变为0.0
         */
        int numNegZeros = 0;    //-0.0的数目
        int i = fromIndex, n = toIndex;
        while(i < n) {
            if (a[i] != a[i]) {     //a[i] != a[i]表示NaN
        double swap = a[i];
                a[i] = a[--n];
                a[n] = swap;
            } else {
                //表示-0.0
                if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) {
                    a[i] = 0.0d;
                    numNegZeros++;
                }
                i++;
            }
        }

        // 阶段2 : 排序主流程: quicksort
    sort1(a, fromIndex, n-fromIndex);

        // 阶段3: 将原始的-0.0变回去(numNegZeros个)
        if (numNegZeros != 0) {
            int j = binarySearch0(a, fromIndex, n, 0.0d); // posn of ANY zero
            do {
                j--;
            } while (j>=0 && a[j]==0.0d);

            // j is now one less than the index of the FIRST zero
            for (int k=0; k<numNegZeros; k++)
                a[++j] = -0.0d;
        }
    }

quicksort流程:

private static void sort1(int x[], int off, int len) {
    // 小数组直接插入排序
    if (len < 7) {
        for (int i=off; i<len+off; i++)
        for (int j=i; j>off && x[j-1]>x[j]; j--)
            swap(x, j, j-1);
        return;
    }

    // 选择划分元素 v, 
    int m = off + (len >> 1);       // 中间元素
    if (len > 7) {
        int l = off;
        int n = off + len - 1;
        if (len > 40) {        // 大数组, 9取中
        int s = len/8;
        l = med3(x, l,     l+s, l+2*s);
        m = med3(x, m-s,   m,   m+s);
        n = med3(x, n-2*s, n-s, n);
        }
        m = med3(x, l, m, n); // 中等大小的划分元素 : 三取中
    }
    int v = x[m];

    // 最后结构 : v* (<v)* (>v)* v* ,即头部和尾部均为若干个v, //中间分为三部分:小于v的部分,v,大于v的部分
    int a = off, b = a, c = off + len - 1, d = c;
    while(true) {
        while (b <= c && x[b] <= v) {
        if (x[b] == v)
            swap(x, a++, b);
        b++;
        }
        while (c >= b && x[c] >= v) {
        if (x[c] == v)
            swap(x, c, d--);
        c--;
        }
        if (b > c)
        break;
        swap(x, b++, c--);
    }

    // 将划分元素换回到中间位置
    int s, n = off + len;
    s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
    s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

    // 递归完成子数组的排序
    if ((s = b-a) > 1)
        sort1(x, off, s);
    if ((s = d-c) > 1)
        sort1(x, n-s, s);
    }

对象数组的排序采用mergesort:

private static void mergeSort(Object[] src,
                  Object[] dest,
                  int low,
                  int high,
                  int off) {
    int length = high - low;

    // 小数组插入排序
        if (length < INSERTIONSORT_THRESHOLD) { //INSERTIONSORT_THRESHOLD = 7
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
             ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // 递归排序左右子数组
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // 已序(左边最大元素小于等于右边最小元素)
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // merge
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

二分搜索

对于long,int,byte等整形:
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                     long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

double和float,对于==的处理,采用的是Double.doubleToLongBits值:

private static int binarySearch0(double[] a, int fromIndex, int toIndex,
                     double key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        double midVal = a[mid];

            int cmp;
            if (midVal < key) {
                cmp = -1;   // Neither val is NaN, thisVal is smaller
            } else if (midVal > key) {
                cmp = 1;    // Neither val is NaN, thisVal is larger
            } else {
                long midBits = Double.doubleToLongBits(midVal);
                long keyBits = Double.doubleToLongBits(key);
                cmp = (midBits == keyBits ?  0 : // Values are equal
                       (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
                        1));                     // (0.0, -0.0) or (NaN, !NaN)
            }

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

数组判等equals

其中对double和float元素的判等用Double.doubleToLongBits(Float.floatToIntBits)

数组填充fill

数组拷贝copyOf,copyOfRange

调用System.arraycopy这个native方法

数组hashCode

数组转List方法asList

参数为可变长度数组

数组toString

LinkedList

双向循环链表注意其中取第i个元素,并不是我们通常想的那样从头开始往下便利,而是根据i偏向于头部还是偏向于尾部来决定从头开始往后找还是从尾开始往前找:

private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {  //前半部分
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {    //后半部分
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
}

Vector

数组实现

是一种RandomAccess,数组实现:

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    protected Object[] elementData;
}
###默认容量

java public Vector() { this(10); }

###扩容策略
成倍增长(2倍原始容量)

java private void ensureCapacityHelper(int minCapacity) { int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object[] oldData = elementData; int newCapacity = (capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2); if (newCapacity < minCapacity) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); } }

###同步策略
每个方法都加了synchronized关键字,导致性能不高.
#Stack
用vector实现

java public class Stack extends Vector { } ```

xiaobaoqiu Blog

Think More, Code Less

Java List