文档章节

集合中关于表

laohng1995
 laohng1995
发布于 2017/02/25 21:48
字数 3177
阅读 4
收藏 0

1.Java Collections API

  1.1Collection接口

    源码解析:Collection接口继承Interable接口

public interface Collection<E> extends Iterable<E>

 

int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray()
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }
    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();

  
    @Override
    default Spliterator<E> spliterator() {       #Java为了并行便利数据源中的元素设计
        return Spliterators.spliterator(this, 0);
    }

    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

 

1.2  Iterator接口


boolean hasNext();
E next();
default void remove() {
    throw new UnsupportedOperationException("remove");
}

Iterator,通过iterator方法,使每个集合均可以创建并返回给客户一个实现IT二胺投入接口的对象,其中hasnext告诉是否存在下一项而next调用给出集合的下一项。

 

2.ArrayList类

ArrayList类使用的是数组结构的列表。这个结构的类优点在于查找速度快,可以自动真加长度。

源码分析:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList继承AbstractList,标准的List类

ArrayList是实现List接口,能对他进行队列操作

ArrayList给可以提供随机访问的List实现去标识一下,这样使用这个List的程序在遍历这种类型的List的时候可以有更高效率。

ArrayList可以对文件进行复制

ArrayList可以实现序列化,可以进行远程的传输

ArrayList是非同步的,线程不安全的

 

构造器分析:

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

如果没有参数,就创建一个Object类型的数组。

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}

如果填入的参数是一个int行变量,就创建一个大小为int形变量的数组

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

如果传入参数是父类Collection的一个对象,则首先转化为数组类型,获取去尺寸,赋予对象的地址,如果尺寸为0,则创建一个对象。

方法使用:

  添加:

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

添加数据,首先进行扩容,然后把对象赋予elementData的下一个值

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

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}

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

在扩容的过程中首先判断是否需要创建数组,如果需要则进行创建。接着增加操作数,接下来进行扩容操作,首先获取之前数组中的长度,进行数组长度1.5倍扩容,判断如果1.5倍长度小于最小长度时候,这最小长度付给新长度。

 

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

首先判断是否数组越界,然后扩容,复制elementData中index处以后对象复制到index+1处,size-index代表复制长度。最后把element写入到elementData的index处。

 

/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the
 * specified collection's Iterator.  The behavior of this operation is
 * undefined if the specified collection is modified while the operation
 * is in progress.  (This implies that the behavior of this call is
 * undefined if the specified collection is this list, and this
 * list is nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return <tt>true</tt> if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

添加一个集合,首先把集合元素转化为数组,扩容,复制

替换:

/**
 * Replaces the element at the specified position in this list with
 * the specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

 

判断是否越界,获取旧的数据,添加新的数据

 

/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

 

得到新的数据

 

移除:

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
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);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

检查是否越界,增加操作数,获取旧值,确定删除的长度,把需要删除的后一个位置的数据移到所删除的位置,elementData的最后一个位置设为空,让GC堆回收。

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns <tt>true</tt> if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

 

判断对象是否为空,对象为空,查找数组中对象为空的元素。如果对象不为空,判断对象的值是否等于数组中的值,如果等于,添加操作数,利用System.arraycopy函数把该对象所在的位置后面的元素copy到删除元素的位置。把最后一项引用回收。

/**
 * Removes from this list all of the elements whose index is between
 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 * Shifts any succeeding elements to the left (reduces their index).
 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 * (If {@code toIndex==fromIndex}, this operation has no effect.)
 *
 * @throws IndexOutOfBoundsException if {@code fromIndex} or
 *         {@code toIndex} is out of range
 *         ({@code fromIndex < 0 ||
 *          fromIndex >= size() ||
 *          toIndex > size() ||
 *          toIndex < fromIndex})
 */
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}

移除范围fromIndex,toIndex之间

复制后面元素到需要移除的部分,最后把length-(toIndex-fromIndex)部分设为空等待回收。

清空:

/**
 * Removes all of the elements from this list.  The list will
 * be empty after this call returns.
 */
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

 

所有对象引用都为空,GC堆会自动回收

 

使用迭代器:

 

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

获取当前索引值,获取ArrayList.this.elementData的长度和内容,判断是否越界。

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

调用ArrayList.this.remove(lastRet); 的方法



    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

 

 

3.LinkedList类的实现:

LinkedList底层是有双链表实现,而且还需要保留到该表双端引用。

    代码分析:

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

LinkedList是一个继承AbstractSequentialList的双向链表,可以被当做堆栈,队列和双端队列

LinkedList实现List方法,实现基础的List接口,可以进行队列使用

LinkedList实现Deque接口,可以作为双端队列

LinkedList实现Cloneable接口,可以覆盖Clone函数,克隆

LinkedList支持序列化,线程不安全。

AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)等函数,降低List接口的复杂程度。

 

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

 

这是LinkedList作为一个双端链表中的一个基本的对象,这个对象有一个头结点和尾结点,还有一个存储对象数据的部分。

 

构造方法:

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

 

这里提供了一个空的默认构造方法。

第二个构造方法接收一个Collection参数c,调用第一个构造方法构造一个空的链表,之后通过addAll将c中的元素全部添加到链表中。

 

 

添加元素:

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
public void addLast(E e) {
    linkLast(e);
}

添加头尾对象

这里我们与添加头结点为例子

/**
 * Links e as first element.
 */
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++;
}

将头结点与first相引用,创建一个新的结点,将头连接到创建结点的next,新对象赋予头结点,增加尺寸和操作数。

/**
 * Returns the (non-null) Node at the specified element 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;
    }
}

 

public boolean addAll(int index, Collection<? extends E> c) {
    //判断越界
    checkPositionIndex(index);
    //转化为数组对象
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    //索引值等于尺寸,则说明在尾部添加,否则判断添加的位置
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    //添加对象
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    //添加尾部,如果succ为空的话,代表插入位置为默认,把尾部添加到刚才新添加元素的位置。
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

 

 

添加一个节点:

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
/**
 * Links e as last element.
 */
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++;
}

获取到尾结点,创建一个新结点,新节点头部连接尾结点,内容e,把该节点设为尾结点。

删除一个节点:

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

 

/**
 * Unlinks non-null node x.
 */
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;
}

 

© 著作权归作者所有

共有 人打赏支持
laohng1995
粉丝 11
博文 36
码字总数 29266
作品 0
南岸
程序员
利用线性表的顺序结构求集合的并、交、差、补(C语言实现)

昨天用数据结构中的线性表的顺序结构实现了关于集合的并、交、差、补的集合运算,做个记录,希望也能帮助到其他人。 一、算法分析   (1)用数组A,B,C,E表示集合。假定A={1,3,4,5,6...

Tim_JX
2014/03/24
0
0
JEPLUS子功能集合配置——JEPLUS软件快速开发平台

子功能集合配置 关于子功能配置在我们的项目中其实也是经常使用的,下面我们来进行一下简单的配置。 首先我们先创建一个主表和一个子表 表的编码注意不能有重复的, 选择表辅助是要在子表上选...

JEPLUS
07/11
0
0
Java 数据结构

Java 数据结构 Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类: 枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 字典(Dictionary) 哈希...

xjt2016
2016/11/20
83
0
ConcurrentSkipListMap/ConcurrentSkipListSet

转关于ConcurrentSkipListMap 和 ConcurrentSkipListSet 的深度好文, 终于明白了skip List (跳表)的含义 http://www.cnblogs.com/skywang12345/p/3498634.html http://www.cnblogs.com/sk......

Faye_Cai
2016/07/06
29
0
@OneToMany、@ManyToOne以及@ManyToMany讲解

一、一对多(@OneToMany) 1、单向一对多模型 假设通过一个客户实体可以获得多个地址信息。 对于一对多的实体关系而言,表结构有两种设计策略,分别是外键关联和表关联。 (1) 映射策略---外键...

gxchan
2015/12/23
249
0

没有更多内容

加载失败,请刷新页面

加载更多

day96-20180923-英语流利阅读-待学习

英国王子也不看好人工智能,理由却和霍金不同 Daniel 2018-09-23 1.今日导读 2016 年 3 月 9 日至 15 日,世界围棋冠军李世石与谷歌研发的计算机围棋程序 AlphaGo 进行人机大战并以 1 比 4 ...

飞鱼说编程
4分钟前
0
0
今天在码云遇到一个很有意思的人 for Per.js

今天在码云遇到一个很有意思的人,他在我的Per.js项目下面评论了一句,大意为“你试试这句代码,看看速度到底是你快还是Vue快”【当然,这个评论被我手残不小心删掉了...】。 然后我就试了,...

Skyogo
9分钟前
3
0
Java -------- 首字母相关排序总结

Java 字符串数组首字母排序 字符串数组按首字母排序:(区分大小写) String[] strings = new String[]{"ba","aa","CC","Ba","DD","ee","dd"}; Arrays.sort(strings); for (int i ...

切切歆语
11分钟前
0
0
还在用 Git 的 -f 参数强推仓库,你这是在作死!

最近,美国一个程序员因为同事不写注释,代码不规范,最严重的是天天使用 git push -f 参数强行覆盖仓库,该程序员忍无可忍向四名同事开抢,其中一人情况危急!!! 不写注释、代码不规范是一...

红薯
24分钟前
200
0
NPM报错终极大法

所有的错误基本上都跟node的版本相关 直接删除系统中的node 重新安装 sudo rm -rf /usr/local/{bin/{node,npm},lib/node_modules/npm,lib/node,share/man/*/node.*} 重新安装 $ n lts$ npm...

lilugirl
28分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部