必威体育Betway必威体育官网
当前位置:首页 > IT技术

Java基础--List

时间:2019-10-29 19:14:33来源:IT技术作者:seo实验室小编阅读:89次「手机版」
 

javalist

List是集合容器的一种,在分析List之前,我们先来了解一下集合体系的架构

这里写图片描述

Why–为什么需要集合

首先java是一门面向对象的语言,奉承一切皆对象的思想,在实际开发过程中,免不了要经常操作对象,而且会同时操作多个甚至大量对象,这时就需要一个专门存储这些对象的容器,这样就可以利用容器对象的特性来方便的进行操作。

其次,在Java中还有数组,也是一种容器,但和集合相比,数组长度不可变,只能存储同一种类型元素。

所以,Java提供了集合的概念,相比于数组,集合长度可变,可存储多种类型元素,只能存储引用类型元素;同时不同的集合容器,有不同的实现方法和特性,可以更加方便的对对象进行操作。

What–什么是List

List是一个继承了Collection的接口,里面有一些方法,如size()、isempty()等,代表一个元素有序,可重复的集合,集合中每个元素都有其对应的索引。

为什么元素“有序”、“可重复”呢?

首先,List的数据结构就是一个序列,存储内容时直接在内存中开辟一块连续的空间,然后将空间地址与索引对应

其次,List接口的实现类在实现插入元素时,都会根据索引进行排列,如ArrayList,本质是一个数组,插入时元素互不干扰,自然可以重复。

由于List继承了Collection,所以就具有了Collection的方法:

int size();//集合中元素个数
isEmpty();//是否为空
boolean contains(Object o);//比较地址是否相等
Iterator<E> iterator();//迭代器方法,可用于遍历
Object[] toArray();//转成数组
boolean add(E e);//向list尾部添加新元素
boolean remove(Object o);//删除元素
boolean containsAll(Collection<?> c);//集合A是否包含集合B(A为调用者)
boolean addAll(Collection<? extends E> c);//将集合B中元素添加到集合A中尾部(A为调用者)
boolean removeAll(Collection<?> c);//将两集合中的交集元素删除
int hashCode();//求哈希值

同时,也具有自己独特的方法(对索引的操作):

E get(int index);//取出对应索引的元素
E set(int index, E element);//往指定索引中插入指定元素,并将原元素覆盖
void add(int index, E element);//往指定索引插入指定元素,其他元素依次后移一位
E remove(int index);//删除索引位置的元素,此位置后的元素前移一位
int indexof(Object o);//获取元素的索引,若有重复元素,则取最靠前的
int lastIndexOf(Object o);//从后往前数,第一个元素的索引
ListIterator<E> listIterator();//list独有迭代器,迭代式可以add元素
List<E> subList(int fromIndex, int toIndex);//截取原集合元素生成新的集合,值域为[fromIndex,toIndex)

List的三种实现:ArrayListLinkedListvector。三者都实现了List接口,区别在于实现机制不同,对不同的操作有不同的效率。

ArrayList是一个可以改变大小的数组,当更多的元素加入数组中时其大小将会动态的增长,内部元素可通过索引直接get或set

LinkedList是一个双向链表,在添加和删除元素时有比ArrayList更好的性能,但查询某个元素时性能不如ArrayList。性能对比的前提是数据量很大或操作很频繁,否则对比也没意义了

ArrayList与LinkedList相比,查询快,是因为索引可以直接定位到元素,而增删慢是因为当操作中间某个索引上的元素时,此位置空余出来,则其他相对靠后的元素会都往前顺移一位,可以想象,当数据量很大并且频繁操作时,只是操作其中的一个小元素,则牵一发而动全身;LinkedList是双向链表结构,查询慢,当查询某个元素时它会从头节点逐步查询(若index<链表长度的1/2,从前往后找,反之亦然),直到找到为止,而增删时只需改变其前后元素的指向即可

Vector和ArrayList都是基于数组实现的,区别在于Vector的方法都是同步的(Synchronized),是线程安全的,而ArrayList不是,因此ArrayList性能要好于Vector;其次,当元素容量超过它们的初始容量时,Vector会扩容翻倍,而ArrayList只会扩充50%,有利于节省内存空间。

注意ArrayList默认初始容量非常小,若可预估容量大小,可设置初始容量,这样可减少调整大小的开销,属于最佳实践。

How–ArrayList是如何实现的

由于ArrayList使用频率最高,所以让我们看下ArrayList是如何实现扩充的。  

类关系和成员变量
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, cloneable, java.io.serializable
{
    private static final long serialversionuid = 8683452581122892189L;

    /**
     * Default initial capacity.  默认初始化容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};  
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * ArrayList基于数组实现
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList元素个数
     */
    private int size;
构造函数
 /**
     * 调用无参构造,会将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值于elementData,然后个数与当前size比较,
     * 不停用Arrays.copyOf()方法扩展数组大小
     */
 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    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);
        }
    }
add()
/**
     * 首先看到不管是尾部add还是操作索引add,都会确认当前的数组空间是否够插入数据,并且从grow()方法中,
     * ArrayList默认每次自增50%大小再和minCapacity比较,如果还是不够,就把当前size扩充至minCapacity。
     * 如果是队尾插入,就把数组向后移动一位,然后赋值,若中间插入,则用到System.arraycopy,把index开始所有
     * 数据向后移动一位,然后插入
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    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);
    }
    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);
    }

Set

作为同样继承了Collecton的Set,不允许有重复对象,无序排列元素、只允许一个null元素。使用频率较高的实现类有HashSet、LinkedHashSet和treeset

fail-fast机制:(HashMap,Vector,ArrayList,HashSet)

在遍历一个集合时,集合结构被修改(增、删、改),会抛出Concurrent Modification Exception:

情况一:单线程环境。集合创建后,在遍历的过程中修改了结构。注意:remove()方法会让expectModcount和modcount 相等,所以是不会抛出这个异常。

情况二:多线程环境。一个线程在遍历,另一个线程对集合结构进行修改。注意:迭代器的快速失败无法得到保证。

fail-fast机制是如何检测的?

迭代器在遍历过程中是直接访问内部数据的,因此内部数据再遍历过程中无法被修改,为了保证不被修改,迭代器内部维护了一个标记“mode”,当集合结构发生改变(添加删除或者修改),标记”mode”会被修改,而迭代器的每次的hasNext()和next()方法都会检查该”mode”是否被改变,当检测到被修改时,抛出Concurrent Modification Exception。

private class Itr implements Iterator<E> {
        int cursor;
        int lastRet = -1;
        int expectedModCount = ArrayList.this.modCount;

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

        public E next() {
            checkForComodification();
            /** 省略此处代码 */
        }

        public void remove() {
            if (this.lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            /** 省略此处代码 */
        }

        final void checkForComodification() {
            if (ArrayList.this.modCount == this.expectedModCount)
                return;
            throw new ConcurrentModificationException();
        }
    }

fail-safe机制:(CopyOnWriteArrayList,ConcurrentHashMap)

任何对集合结构的修改都会在一个复制的集合是修改,因此不会抛出ConcurrentModificationException。

问题一:需要复制集合,产生大量的无效对象,开销大

问题二:无法保证读取的数据是目前原始结构中的数据

When–什么时候会用到List

如果涉及到“栈”、“队列”、“链表”等操作,应该考虑用List,具体用哪个具体分析:需要快速插入或删除,用LinkedList;需要快速访问,用ArrayList;多线程环境,且List可能同时被多个线程操作,用vector。

当然,对于线程安全的List,也可以用CopyOnWriteArrayList,基于数组实现的线程安全(ReentrantLock加锁)的写时复制集合,性能比vector高,适合高并发的读多写少的场景

CopyOnWrite容器,是一个写时复制容器,当我们往一个容器添加元素时,不是直接往当前容器添加,而是先将容器copy一份,复制出新的容器,然后对新的容器里的元素进行操作,最后将原容器的引用指向新的容器。所以,这是一种读写分离的思想,读和写不同的容器。缺点:若写操作频繁,会频繁复制容器,从而影响性能。

Other–使用List可能出现的问题

1.NullPointException和IndexOutOfBoundsException问题。List是一个容器对象,在业务逻辑中经常定义List容器,盛放多个业务对象,当容器中没有任何元素时,调用容器操作索引方法,则出现索引越界异常;当作为返参容器时,并没有查到数据,会返回null,此时就容易出现空指针异常。

2.Arrays.asList方法。我们经常用此API将数组转成List对象,但稍不注意就会报异常。

情况一:方法调用的入参为基本数据(byte、short、int、long、char、double、float、boolean)类型的数组时,结果会返回一个元素数量为1的集合,和原数据的元素个数无关,这样是因为此方法接收泛型参数,而基本类型不支持泛型化,而数组支持,所以那为1的元素是整个数组,实质存的是此数组的引用地址

情况二生成新的List集合后,调用add()方法,会出现UnsupportedOperationException异常。抽象类AbstractList定义了对List操作的方法如add等,但用此方法生成的list集合并没有实现它们,所以会报异常。解决:用new关键字创建一个List容器对象,而Arrays.asList作为构造参数入参传入。

文章最后发布于: 2018-08-29 18:16:00

相关阅读

java反射获取参数名,idea如何开启-parameters

在8以前的jdk版本的时候,我们利用反射只能获取到参数类型,然后参数名字都是利用arg0,arg1,arg2......所以在使用一些反射编程方面上

网络基础薄弱的企业如何开展网络营销

有个朋友,他们公司是传统行业的生产商,之前的客户主要都是来源于线下,线上部分基本为0。他们团队成员也都没有涉及过网络营销,对网络

JavaWeb——B/S,C/S结构,HTTP协议

B/S: 开发基于B/S结构项目:目前主要采用三种服务器端语言:JSP,PHP,ASP.NET。 这三种语言构成三种常用应用开发组合:JSP+Oracle组合、P

java-多线程-CountDownLatch(闭锁) CyclicBarrier(栅

(代码来源网络共享) 这几个工具类其实说白了就是为了能够更好控制线程之间的通讯问题~ CountDownLatch  是一个同步的辅助类,允许

2019最新java面试葵花宝典

[转] 15年毕业到现在也近四年了,最近面试了阿里集团(菜鸟网络,蚂蚁金服),网易,滴滴,点我达,最终收到点我达,网易offer,蚂蚁金服二面挂掉,菜

分享到:

栏目导航

推荐阅读

热门阅读