红泥小火炉


java集合常见实现类分析

Nathaniel 480浏览 0条评论
首页/正文
分享到: / / / /

java集合是开发中常用的库类,也是最能看出开发层次的一个内容,在集合层面常常有很多值得探究的源码技巧,在本文中将自顶向下介绍java中的集合。

日常所说的集合类,其实指的是Collection接口类及其实现类;由于在面试中常常会和Map放在一起,所以后面的文章中也会介绍Map的相关内容。

一、Conllection实现上下文

Collection接口继承Iterable接口类,查看Iterable接口源码,可以发现:

实现此接口允许对象成为“for-each loop”语句的目标。for-each loop特就是增强for循环。

// 返回类型为 T元素的迭代器
Iterator<T> iterator();
// 对 Iterable的每个元素执行给定的操作,直到所有元素都被处理或动作引发异常,如果给定了顺序,按照顺序执行动作。该过程中发生的异常将返回给调用者。
default void forEach(Consumer<? super T> action);
/*
for (T t : this) {
    action.accept(t);
}
*/
// 在Iterable描述的元素上创建一个Spliterator.
default Spliterator<T> spliterator();

总结:实现Iterable接口,可以让实现类可以使用增强For循环以及迭代器。

Collection接口介绍:

  • 集合层次结构中的顶层接口 。 集合表示一组元素的对象。 一些集合允许重复元素,而其他集合不允许。 有些有序,有些无序。 JDK不提供此接口的任何直接实现:它提供了更具体的子接口的实现,如Set和List 。 该接口通常用于传递集合,并在需要最大的通用性的情况下对其进行操作。
  • 所有通用的Collection实现类(或者通过子接口实现)应该提供两个标准的构造方法:一个无参的构造函数,一个通过另一个集合创建。后一个构造函数允许用户复制任何集合,生成所需实现类型的等效集合。
// 返回此集合中的元素数。 如果此收藏包含超过Integer.MAX_VALUE个元素,则返回Integer.MAX_VALUE 
int size();
// 集合中没有元素返回true;
boolean isEmpty();
// 集合中包含o,返回true;
boolean contains(Object o);
// 返回此集合中的元素的迭代器.
Iterator<E> iterator();
// 返回一个包含此集合中所有元素的数组,返回的数组将是“安全的”,因为该集合不保留对它的引用。 (换句话说,这个方法必须分配一个新的数组,即使这个集合是由数组支持的)。 因此,调用者可以自由地修改返回的数组。
// 此方法充当基于array和基于collection的API之间的桥梁
Object[] toArray();
// 返回包含此集合中所有元素的数组,如果该数组具有比此集合更多的元素,多余的元素则被置为null;
// 该方法允许精确地控制输出array的运行时类型,并且在某些情况下可以用于节省分配成本。
T> T[] toArray(T[] a);
// String[] y = x.toArray(String[]::new); 支持lamble表达式;
default <T> T[] toArray(IntFunction<T[]> generator);
// 插入元素
boolean add(E e);
boolean addAll(Collection<? extends E> c);
// 删除元素
boolean remove(Object o);
boolean removeAll(Collection<?> c);
// 包含指定集合中的元素,返回true
boolean containsAll(Collection<?> c);

二、List接口

// 返回此列表中指定位置的元素
E get(int index);
// 用指定的元素(可选操作)替换此列表中指定位置的元素
E set(int index, E element);
// 将指定的元素插入此列表中的指定位置(可选操作)。  
void add(int index, E element);
// 将指定的元素追加到此列表的末尾
boolean add(E e);
// 删除该列表中指定位置的元素(可选操作)。 
E remove(int index);
// 返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回-1。
int indexOf(Object o);
// 返回此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则返回-1。
int lastIndexOf(Object o);
// 返回列表中指定的fromIndex (含)和toIndex之间的部分视图
List<E> subList(int fromIndex, int toIndex);

ArrayList

// RandomAccess:List实现使用的标记接口,表明它们支持快速(通常为恒定时间)随机访问。 此接口的主要目的是允许通用算法更改其行为,以便在应用于随机访问列表或顺序访问列表时提供良好的性能。
class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList继承自AbstractList;

重要的常量

// 默认的初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList最大的元素个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

重要的变量

// ArrayList元素存储到的数组缓冲区
transient Object[] elementData; 
// ArrayList中的元素个数
private int size;

构造方法

// 使用初始化的容量进行构造,object[];
public ArrayList(int initialCapacity) ;
// 使用默认的容量10进行构造。
public ArrayList();
// 利用指定的集合构造
public ArrayList(Collection<? extends E> c);

主要方法源码分析

add(E e):

// 加入元素
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

// 可以看到使用新的数组容量进行复制;
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}
// 返回至少等于给定最小容量的容量。 如果满足,返回当前容量增加50%的结果。 除非给定的最小容量大于MAX_ARRAY_SIZE,否则不会返回大于MAX_ARRAY_SIZE的容量
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新数组容量为原数组的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 扩容之后的量少于最小的数组容量,以最小的数组容量为准。
        return minCapacity;
    }
    // 扩容之后的数组容量和最大限值进行比较;如果超过最大限值,则以最大值为准,否则为扩容之后的容量;
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

add(int index, E element):

public void add(int index, E element) {
    // 检查要插入的位置时候超过原有的容量下标
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    // 当前的容量即为元素个数,则进行扩容
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
   	// 将原来在index位置的元素及以后元素往后移动s - index。
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

get(int index):

public E get(int index) {
    Objects.checkIndex(index, size);
    // 直接按照索引index在数组中获取元素
    return elementData(index);
}

remove(int index):

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        // 移除index位置的元素,并将后面的元素往前挪移
        System.arraycopy(es, i + 1, es, i, newSize - i);
    // 将最后一个元素置为null
    es[size = newSize] = null;
}

LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList实现了AbstractSequentialList接口,双链表实现了List和Deque接口;LinkedList没有同步,线程不安全,通常在自然封装列表的对象上进行同步来实现,如果没有这样的对象,链表应该使用Collections.synchronizedList方法来包装,最好在创建时就完成,以防止意外的不同步访问列表:

List list = Collections.synchronizedList(new LinkedList(...));

节点:

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;
    }
}

重要变量

// 指向第一个节点的指针
transient Node<E> first;
// 指向最后一个节点的指针
transient Node<E> last;
// 链表的节点个数
transient int size = 0;

构造方法

// 默认空的构造
public LinkedList();
// 根据指定的集合创建链表
public LinkedList(Collection<? extends E> c);

重要方法

// 获取到头节点
public E getFirst();
// 获取到尾节点
public E getLast();
// 删除头节点
public E removeFirst();
// 删除尾节点
public E removeLast();
// 增加头节点
public void addFirst(E e);
// 增加尾节点
public void addLast(E e);

以上增加或删除节点均依靠类似的操作:

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC ,这一步在自定义时很容易漏了
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

contains(Object o):此方法使用了遍历链表,比较耗时。

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

删除某一节点:boolean remove(Object o)

// 内部主要调用了这样的操作逻辑
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节点
            first = next;
        } else {
            // 当前节点不为头节点,则前序节点的next指向next,并将当前节点的接续节点置为null,便于GC
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            // 当前节点为尾节点,将last直接赋值为前序节点即可。
            last = prev;
        } else {
            // 否则的话,将后序节点的前序节点变为当前节点的前序,跨过了当前节点,并将当前节点的后续节点指针置为null.
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

get(int index):获取到当前index位置的节点

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}
// 利用下标做一次二分法应用,节省了一半的时间。
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;
    }
}

queue操作,deque操作和queue操作类似,最下层方法均为上面描述的方法操作。

// 检索但不删除此列表的头(第一个元素),如果list为空,返回null
public E peek();
// 检索但不删除此列表的头(第一个元素),如果list为空,NPE
public E element();
// 检索并删除此列表的头(第一个元素),如果list为空,返回null
public E poll();
// 检索并删除此列表的头(第一个元素),如果list为空,NPE
public E remove();
// 将指定元素添加为此列表的尾部(最后一个元素)
public boolean offer(E e);

三、Set

Set接口中约定的方法和List中的大同小异,在此不做赘述。

HashSet

hashSet是Set的直接实现类;底层为HashMap;对元素顺序不做保证,这个类允许null;

hashSet没有实现同步,是线程不安全的,在多并发情况下,必须在外部进行同步,通常通过在自然封装集合的一些对象上进行同步来实现,如果没有这样的对象,则应该使用Collections.synchronizedSet方法包装。最好在创建时完成,以防止对该集合的意外不同步访问:

Set s = Collections.synchronizedSet(new HashSet(...));

继承上下文如下:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

重要的变量

// 用于常规操作的hashMap
private transient HashMap<E,Object> map;
// 虚拟的值用于关联map中的元素
private static final Object PRESENT = new Object();

构造方法

// 使用默认容量16.默认的负载因子0.75的hashMap
public HashSet();
// 使用指定的集合来初始化hashMap(获取c.size()/.75f+1和16中的最小值做为初始化容量,负载因子为0.75),构造hashSet
public HashSet(Collection<? extends E> c);
// 使用指定的初始化容量和负载因子
public HashSet(int initialCapacity, float loadFactor);
// 使用初始化容量大小和默认的负载因子0.75
public HashSet(int initialCapacity); 

常见方法,比如iterator(),size(),isEmpty(),contains(Object o),add(E e),remove(Object o)等均调用底层hashMap的操作逻辑。

LinkedHashSet

继承了HashSet。维护了一个双向链表来保证元素的有序,迭代和集合的大小成比较,无论其容量如何。没有实现同步,线程不安全,和HashSet一致。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

构造方法:

// 指定容量,负载因子
public LinkedHashSet(int initialCapacity, float loadFactor);
// 指定容量,负载因子默认.75
public LinkedHashSet(int initialCapacity);
// 默认容量16.默认负载因子.75
public LinkedHashSet();
// 使用指定的集合来构造,容量为从2*c.size()和11中的最大值,负载因子为.75
public LinkedHashSet(Collection<? extends E> c)

没有特殊重写的方法。

TreeSet

为Set的间接实现子类,实现为NavigableMap(继承SortedMap),通过比较器或者自然顺序来实现有序。

add(),remove(),contains()为O(logN)的时间复杂度。同样没有实现同步,为线程不安全的。具体的办法和LinkedHashSet以及HashSet一致。

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
最后修改: © 著作权归作者所有
上一篇

评论列表

还没有人评论哦~赶快抢占沙发吧~

博客信息

  • 文章数目 12
  • 标签数目 7
  • 运行天数
  • 最后活动

广告