黑马程序员技术交流社区

标题: 【成都校区】集合框架深入理解 [打印本页]

---

作者: 逍遥来了    时间: 2018-12-19 22:53
标题: 【成都校区】集合框架深入理解
最近准备把集合框架再深入了解一下，目前看到ArrayList和LinkedList，根据网上资料摘抄做的部分笔记：
关于ArrayList：
顺序容器，底层是Object数组，以便容纳任意类型的对象。区别容量(Capactiy)和当前存储元素个数。没有实现同步。size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比，其余方法大都是线性时间。
方法解析
初始容量大小：private static final int DEFAULT_CAPACITY = 10;
扩容大小：int newCapacity = oldCapacity + (oldCapacity >> 1);即原来的1.5倍
方法和操作数组类似，注意如add()方法中需要扩容时，使用Arrays.copyOf()进行旧数组的扩容，以下是扩容操作：
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //以1.5倍原长度进行扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //使用Arrays.copyOf()进行扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}
如remove()方法删除元素后，为了让GC起作用，必须显式的为最后一个位置赋null值。因为如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。使用System.arraycopy()进行移位操作，以下是remove()方法
public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //清除该位置的引用，让GC起作用
    elementData[--size] = null;
    return oldValue;
}
其余方法主要是对数组的操作，可以直接参考JDK源码。

关于LinkedList:
LinkedList同时实现了List和Deque接口，既可以看做顺序容器，也可以看做队列，以及栈，不过关于栈和队列，现在首选是ArrayDeque(在该方面有更好的性能)。LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首尾操作元素只需要常数时间。为追求效率LinkedList没有实现同步，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。
底层：双向链表，每个节点用内部类Node表示
//Node内部类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
方法解析
关键在于正确操作节点内的next和prev两个引用。具体方法可以直接查看JDK源码。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2