关于android:Java深入研究Collection集合框架

61次阅读

共计 8538 个字符,预计需要花费 22 分钟才能阅读完成。

Java 汇合框架位于 java.util 包下, 次要蕴含 List、Set、Map、Iterator 和 Arrays、Collections 汇合工具类, 波及的数据结构有数组、链表、队列、键值映射等,Collection 是一个形象接口, 对应 List、Set 两类子接口,Map 是 key-value 模式的键值映射接口,Iterator 是汇合遍历的迭代器, 上面是整体框架图

汇合框架整体框架图

在 util 包下还波及 SortedMap、SortedSet 接口, 别离对应 Map、Set 接口, 在 concurrent 包下有常见的
ArrayBlockingQueue、ConcurrentHashMap、CopyOnWriteArrayList 等实现类对 Queue、Map、List 接口的扩大实现, 上面别离从 List\Queue\Set\Map 接口罕用实现类一探到底

ArrayList 实现

咱们先来看看初始化形式,

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;

public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

从源码中定义的两个 Object 数组可知 ArrayList 采纳数组作为根本存储形式, 在 String 字节码中也有定义数组, 不过是 private final char[] value,transient 关键字次要是序列化时疏忽以后定义的变量; 在 ArrayList 无参函数中给定默认数组长度为 10, 在理论开发中, 个别如果能预知数组长度则会调用带有长度阈值的构造函数,

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);
    }
}

源码办法中会间接依照指定长度创立 Object 数组并赋值给 this.elementData, 接下来持续看看没有指定数组长度时, 数组是如何扩容从而满足可变长度? 此时 ArrayList 中的 add 办法退场

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

size 为 ArrayList 中定义的 int 类型变量, 默认为 0, 当调用 ensureCapacityInternal(1), 持续往下看

private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

该办法会判断底层数组 elementData 与长期数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是否相等, 如果是就取两个阈值中的最大值,minCapacity 为 1,DEFAULT_CAPACITY 为 10(默认值), 而后持续走 ensureExplicitCapacity(10),

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

modCount 用于记录操作次数, 如果 minCapacity 大于底层数组长度, 开始调用扩容办法 grow

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

oldCapacity 为默认底层数组长度,newCapacity = oldCapacity + (oldCapacity >> 1)等价于
newCapacity = oldCapacity + (oldCapacity / 2); 在 Java 位运算中,oldCapacity << 1 相当于 oldCapacity 乘以 2;oldCapacity >> 1 相当于 oldCapacity 除以 2 , 此时新的长度为原始长度的 1.5 倍, 如果扩容后的长度小于 minCapacity, 则间接赋值为 minCapacity, 再往下的 if 判断中是对 int 最大值的边界断定, 能够看到最初通过 Arrays.copyOf 进行数组的 copy 操作, 这是 Arrays 工具类中的办法, 该办法最终调用如下

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {@SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
    return copy;
}

通过 System.arraycopy 进行数组复制并 return this,System.arraycopy 办法为 native 办法, 对应办法如下

                                    // 原始数组      // 地位     // 指标数组   // 地位
 public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos,
                                    int length);//copy 长度

调用一连串办法最终也只是 copy 一个默认长度为 10 的空数组, 咱们持续看 add 办法中的
elementData[size++] = e;// 把以后对象搁置在 elementData[0] 上, 在 ArrayList 中 size()办法是间接返回定义的 size 值, 即为返回数组元素长度, 而非底层数组长度(默认 10), 所以 ArrayList 在初始时就占用肯定空间, 上面咱们看下 ArrayList 中的查询方法

public E get(int index) {if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    return (E) elementData[index];
}

如果要查找 List 中某个对象, 如果已知对象在数组中的地位, 则间接 return (E) elementData[index]返回, 在计算算法效率中以 O 示意工夫, 此时能够以 O(1)示意查问到指定对象的工夫复杂度, 因为通过下标查找咱们只须要执行一次, 如果咱们无奈得悉具体下标, 通常是 for 循环查找地位直到返回对象, 假如数组长度为 n, 此时的工夫复杂度为 O(n), 这种形式实则取的是查找到该对象所耗费的工夫的最大值, 有可能在 for 循环中第一个或是两头一个地位就曾经查找到了, 则可记为 O(1)或者 O(n/2)

LinkedList 实现

LinkedList 基于双向链表 + 外部类 Node<> 泛型汇合实现, 初始化没有默认空间大小, 依据头尾节点查找元素, 上面先看下双向链表的数据结构图

链表中 elem 为以后元素,prev 为以后元素的上一个节点,next 为下一个节点,LinkedList 初始化时链表是空的, 所以 firs 头节点、last 尾节点都是 null, 上面看下初始化源码,

transient int size = 0;  //transient 标记序列化时疏忽
transient Node<E> first; // 头节点
transient Node<E> last; // 尾节点

public LinkedList() {}

public LinkedList(Collection<? extends E> c) {this();
    addAll(c);
}

有参函数对应退出整个汇合, 上面先看下外部类 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;
    }
}

E 示意泛型元素类型,prev 记录以后元素的上一个节点,next 记录下一个节点, 当咱们往 LinkedList 中 add 一个元素时, 看下源码是怎么解决 Node 节点,

public boolean add(E e) {linkLast(e);
    return true;
}
    
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

在进行增加操作时默认是追加至 last 节点,linkLast 办法中首先将以后数组中 last 节点赋值长期变量, 而后调用 Node<> 构造函数将以后增加元素与 last 关联, 此时 l 赋值给 Node<> 中的 perv 节点, 接着判断 l 是否为 null, 如果是示意数组中没有元素, 就间接赋值给 first 作为第一个, 否则就追加至原数组最初一个元素的 next 节点, 从而实现 add 操作, 上面咱们看下指定插入地位 add 办法,

public void add(int index, E element) {checkPositionIndex(index);   // 校验 index 边界 >=0 && <=size
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
Node<E> node(int index) {// assert isElementIndex(index);
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

linkBefore 办法中首先会调用 node(int index)节点生成办法, 该办法中首先通过二分法的形式断定元素插入地位, 而后别离对 first、last 节点中的 next、prev 节点进行赋值操作, 最初返回插入的节点元素, 传递给 linkBefore 办法, 该办法会判断传入的节点元素的上一个节点是否为 null, 对节点进行相应赋值操作, 从而实现指定下标插入元素, 上面持续看下 LinkedList 删除元素办法 remove(int index),

public E remove(int index) {checkElementIndex(index);  //index 边界断定 >=0 && <size
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {first = next;} else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {last = prev;} else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

删除元素办法根本都会调用 unlink(Node<E> x), 原理就是把 x 元素的前后节点指向关系进行替换, 而后将以后 x 元素所有属性置空, 达到删除元素目标同时期待 GC 回收, 顺带看下 LinkedList 查询方法

public E get(int index) {checkElementIndex(index);
    return node(index).item;
}

外围是通过相似二分法定位下标对应的元素并返回该对象的 element 值, 能够看到 LinkedList 在增删元素时, 只是批改以后下标所在元素的前后节点指向关系, 绝对于 ArrayList 的 copy 数组效率要高, 而查问元素时虽采纳二分法进步查问效率, 但其工夫复杂度还是 O(logN), 二分法找一次就排除一半的可能,log 是以 2 作为底数, 绝对于 ArrayList 间接索引查问要慢得多

Queue、Deque 的实现

PriorityQueue 是基于优先堆的一个无界队列,该优先队列中的元素默认以天然排序形式或者通过传入可比拟的 Comparator 比拟器进行排序, 上面看下 PriorityQueue 的 add 办法源码

private static final int DEFAULT_INITIAL_CAPACITY = 11;   // 队列默认大小
transient Object[] queue;                                 // 队列底层数组存储构造
int size;                                                 

public boolean add(E e) {return offer(e);
}
public boolean offer(E e) {if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

在 offer 办法中如果插入的元素为 null 则会间接抛出异样, 当队列长度大于等于容量值时开始主动扩容,grow 办法与 ArrayList 的扩容办法相似, 最初都调用了 Arrays.copyOf 办法, 惟一区别在于扩容长度不一样, 可自行查看此处源码,offer 办法中 i = 0 时标记为队列第一个元素, 间接赋值 queue[0], 如果不是第一个, 则开始调用 siftUp()上浮办法,

private void siftUp(int k, E x) {        // k != 0
    if (comparator != null)
        siftUpUsingComparator(k, x);    // 指定排序比拟器
    else
        siftUpComparable(k, x);         // 应用默认天然程序比拟器
}
private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable,<? super E>) x;
    while (k > 0) {int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

在 siftUpComparable 办法中, 将传入的可比拟的对象转换为 Comparable, 如果 k 下标大于 0, 计算父节点的下标 int parent = (k – 1) >>> 1 等价于 int parent = (k – 1)/2; 而后取出父一级的节点对象, 通过 compareTo 办法对插入的对象于以后对象比拟是否 >=0, 如果不大于则把以后对象赋值给 k 地位, 再把 parent 地位赋值给 k 做替换, 最初通过 queue[k] = key 实现元素上浮排序, 持续看下 remove 办法

public boolean remove(Object o) {int i = indexOf(o);               // 遍历数组找到第一个满足 o.equals(queue[i])元素的下标
    if (i == -1)               
        return false;
    else {removeAt(i);
        return true;
    }
}
E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i)                         // removed last element
        queue[i] = null;
    else {E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);             // 调整程序
        if (queue[i] == moved) {siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

删除元素时下标是从后往前, 当 i = s 是最初一个元素下标时间接置空, 否则从队列数组中取出要删除的元素, 调用一次 siftDown 下沉办法对最小堆节点地位进行调整, 以不指定比拟器的办法源码剖析

private void siftDownComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;                          // loop while a non-leaf
    while (k < half) {int child = (k << 1) + 1;                   // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&                         // 比照左右节点大小
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;                               // 将子节点 c 上移
        k = child;
    }
    queue[k] = key;                                 //key 向下挪动到 k 地位
}

依据 int half = size/2 找到非叶子节点的最初一个节点下标并与以后 k 的地位作比拟, 从 k 的地位开始,将 x 逐层向下与以后节点的左右节点中较小的那个替换,直到 x 小于或等于左右节点中的任何一个为止, 从而达到删除非最初一个元素的节点排序, 相应的工夫复杂度也是 O(logN), 通过此处的办法也能够得悉在数组下标从 0 开始状况下, 节点下标计算形式为

left = k 2 + 1 ,right = k 2 + 2, parent = (k -1) / 2, 当然 PriorityQueue 还有一些其它 Queue 接口的实现办法, 如 poll、peek 办法, 包含在 concurrent 包下的 PriorityBlockingQueue,DelayQueue,ConcurrentLinkedDeque 等实现 Queue、Deque 接口的扩大类, 可自行去看下 jdk 1.8 源码实现, 加深二叉队列排序原理的了解

HashSet、HashMap、ConcurrentHashMap 的实现

HashSet 底层是基于 HashMap 实现, 限于本文篇幅过长, 残余源码剖析参见下篇

《Java 深入研究 HashMap 实现原理》

以上波及 JDK 源码局部均来自 JDK 1.8

正文完
 0