本文作者:包子也沉默

【Java基础】谈谈集合.List

包子也沉默 3年前 (2019-10-23) ( 10-23 ) 694 0条评论
摘要: x);EoldValue=elementData(index);elementData[index]=element;returnoldValue;}1.3remove方法常用的删除方法有如下,这些方法的功能根据方法名很容易就看懂,这边就不贴源代码了。publicEremove(intindex);publicbooleanremove(Objecto);publicbooleanremoveAl

在Java中,集合框架的使用频率非常高。在平时开发中,集合常常被用来装盛其他数据,或者用来实现常见的数据结构比如数组、队列和栈等。Java中集合主要可以分为Collection和Map两个大类。Collection又分为List、Queue和Set(见下图)。本篇博客主要来介绍下List集合。

nbsp;处理完 LogRequest 事件的所有事件处理程序后发生。仅在 IIS 7.0 处于集成模式并且 .NETFramework&n

图片. Java集合体系

ntlastIndexOf;publicEget(intindex)。通过下面的代码可以看出,判断相等的标准是两个元素通过equals方法比较相等。publicbooleancontains(Obje

关于List集合,主要掌握ArrayList和LinkedList。同时需要注意是这两个类都不是线程安全的。

阅资料的时候保存下来了,出处已经找不到,如果有知道可以留个言。   当请求到达应用程序之后,第一站就是路由模块,MVC会根据RouteTable(一般都在RouteCon


1. ArrayList

ArrayList是开发过程中使用的最多的List接口的实现类。这个类底层用数组实现,可以动态调整数组大小。ArrayList集合中可以盛放任意类型的元素,包括null。这个类还提供了操作数组大小的方法用于store列表。ArrayList和Vector类似,最大的区别就是ArrayList是非线程安全的而Vector是线程安全的。

态数据。 PostReleaseRequestState 在 ASP.NET 已完成所有请求事件处理程序的执行并且请求状态数据已存储时发生。 Upda

1.1 ArrayList的构造

创建ArrayList的常见方式有下面两种

 ASP.NET 完成缓存模块的更新并存储了用于从缓存中为后续请求提供服务的响应后,发生此事件。仅在 IIS 7.0 处于集成模式并且 .N

    //创建一个空的数组,当我们向这个ArrayList中添加第一个元素时,会创建一个默认容量为10的数组 
    List<String> strList = new ArrayList<String>();
    //创建指定长度为16的数组 
    List<String> strList2 = new ArrayList<String>(16); 

对于ArrayList的创建,需要提下capacity和size这两个概念。capacity是指ArrayList底层实现数组的长度,而size是指数组中已经存放的元素的个数。

dex);publicbooleanremoveIf(Predicate<?superE>filter);publicvoidclear()。1.4查询方法查询方法用来查询ArrayLis

另外ArrayList还有一个通过Collection创建的构造函数,通过这个构造函数产生的ArrayList中的元素的顺序是Collection通过迭代器返回的元素的顺序。

}//判断的标准也是equals方法publicintindexOf(Objecto){intindex=0;if(o==null){for(Node<E>x=first;x!=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;  
        }
 }

在使用创建ArrayList的时候,最好能对ArrayList的大小做一个判断,这样有一下几个好处:

HttpApplication。如果创建了ASP.Global.asax类型,那就对ASP.Global.asax进行实例化。     五、请求到达M

  • 节省内存空间(eg.我们只需要放置两个元素到数组,new ArrayList(2));
  • 避免数组扩容,引起的效率下降;

1.2 add方法

向ArrayList中添加元素常用的两个方法是:

rvices)前发生。 PostRequestHandlerExecute在 ASP.NET 事件处理程序(例如,某页或某个 XMLWebservice)执行完

  • add(E e);
  • addAll(Collection<? extends E> c);
  • set(int index, E e);
  1. add(E e)方法
public boolean add(E e) {
    ensureCapacity(size + 1);//确保对象数组elementData有足够的容量,可以将新加入的元素e加进去
    elementData[size++] = e;//加入新元素e,size加1
    return true;
}
//扩容的逻辑
 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);
}

ArrayList的add(E e)的添加逻辑比较简单,就不把源码全部贴出来了,大家可以自己去看下。大致的添加过程是:首先判断当前数组是不是空数组,如果还是空数组,就创建一个长度是10的默认长度的数组,再将元素添加进去;如果当前的ArrayList不是空数组,判断当前的数组是否已经满了,如果满了就进行扩容(扩容的逻辑是oldCapa+oldCapacity/2,如果这个长度还比所需要的最小长度小,就使用所需的最小长度,如果这个最小值大于了数组的最大长度,就是用Integer.MAX_VALUE作为数组长度),再将元素添加进去。在扩容过程中,ArrayList其实是重新创建了一个长度是newCapacity的数组,创建的代码如下:

ata,index,elementData,index+numNew,numMoved);System.arraycopy(a,0,elementData,index,numNew);size+=nu

//这段代码效率较高,我们开发过程中可以借鉴使用
elementData = Arrays.copyOf(elementData, newCapacity); 
  1. addAll(Collection<? extends E> c)方法
//将集合c中的元素全部添加到ArrayList的尾部
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;
}

//在ArrayList的指定位置添加元素,同时将ArrayList中其他元素右移
//这个方法在使用时需要特别注意index的范围
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}
  1. set(int index,E e)
//将下标位置的元素替换成新的元素,并且返回原来位置上的元素
public E set(int index, E element) {
    rangeCheck(index);

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

1.3 remove方法

常用的删除方法有如下,这些方法的功能根据方法名很容易就看懂,这边就不贴源代码了。

but://-helpsagenerationalGCifthediscardednodesinhabit//morethanonegeneration//-issuretofreememoryeve

  • public E remove(int index);
  • public boolean remove(Object o);
  • public boolean removeAll(Collection<?> c);
  • protected void removeRange(int fromIndex, int toIndex);
  • public boolean removeIf(Predicate<? super E> filter);
  • public void clear()。

1.4 查询方法

查询方法用来查询ArrayList中是否包含某个元素,常用的查询方法有如下几个:

ureAppStartCalled(context) 创建特定的HttpApplication实例,触发ApplicationOnStart事件,执行ASP.Global.asax中的App

  • public boolean contains(Object o);
  • public int indexOf(Object o);
  • public int lastIndexOf;
  • public E get(int index)。

通过下面的代码可以看出,判断相等的标准是两个元素通过equals方法比较相等。

或 XMLWebservices)的执行PostResolveRequestCache在 ASP.NET 跳过当前事件处理程序的执行并允许缓存模块满足来自缓存的请求时发生

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    if (o == null) {//返回第一个null的索引
        for (int i = 0; i < size; i++)
            if (elementData[i] == null)
                return i;
    } else {//返回第一个o的索引
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;//若不包含,返回-1
}

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size - 1; i >= 0; i--)
            if (elementData[i] == null)
                return i;
    } else {
        for (int i = size - 1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

1.5 一些其他常用方法

  • public List subList(int fromIndex, int toIndex); //构造子数组,调用这个方法前,做好调用下subListRangeCheck这个方法判断下参数的正确性
  • public Spliterator spliterator(); //获得ArrayListSpliterator可分割迭代器,Spliterator是JDK8中添加的可以并行迭代器,可用于多线程迭代,增加效率
  • public void sort(Comparator<? super E> c); //将集合元素根据某种规则排序
  • public Iterator iterator(); //获取普通的迭代器,也可以通过for循环迭代
  • public Object[] toArray(); //将ArrayList集合中的元素转换成数组;
  • public T[] toArray(T[] a)

1.6 ArrayList小结

  • ArrayList基于数组方式实现,无容量的限制(最大值是Integer.MAX_VALUE);
  • 添加元素时可能要扩容(所以最好预判一下),删除元素时不会减少容量(若希望减少容量,trimToSize()),删除元素时,将删除掉的位置元素置为null,下次gc就会回收这些元素所占的内存空间;
  • 线程不安全;
  • add(int index, E element):添加元素到数组中指定位置的时候,需要将该位置及其后边所有的元素都整块向后复制一位;
  • get(int index):获取指定位置上的元素时,可以通过索引直接获取(O(1));
  • remove(Object o)需要遍历数组;
  • remove(int index)不需要遍历数组,只需判断index是否符合条件即可,效率比remove(Object o)高;
  • contains(E)需要遍历数组。

2. Vector

Vector和ArrayList非常相似,底层都是通过数组来实现集合的。Vector和ArrayList最大的区别是Vector的很多方法都是用synchronize修饰的,所以是线程安全的。下面列举下两者的主要区别:

bject[]a=c.toArray();intnumNew=a.length;ensureCapacityInternal(size+numNew);//IncrementsmodCountSyst

  • ArrayList是非线程安全的,Vector是线程安全的;
  • 在创建容器时如果不指定容量,ArrayList会先创建一个空的数组,当第一次添加元素时再将容量扩容到10;Vertor在创建时如果没指定容量会默认创建一个容量为10的数组;
  • ArrayL在扩容时是1.5倍的扩容,Vector是2倍的扩容;
  • ArrayList支持序列化,Vector不支持。

3. LinkedList

LinkedList的内部维护的是一个双向链表,定义了如下节点(JDK1.8中的代码,其他版本的会有不同),同时还定义了头尾指针:

层使用链表,所以LinkedList不会有扩容机制。每次add过后,LinkedList的结构如下:3.4remove操作publicEremove(intindex){checkElementInd

...
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
... 
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;
    }
}

3.1 LinkedList的构造

 //构造一个空的List
 public LinkedList() {
 }
 //通过Collection集合构造LinkedList
 public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
 }

3.2 链表的常见操作

由于LinkedList底层是有链表实现的,所以LinkedList提供了很多链表的常见操作:

icaFactory工厂类创建HttpApplication(HttpApplication实现了IHttpHandler),HttpApplicationFactory.GetApplication

  • private void linkFirst(E e); //头插法;
  • void linkLast(E e); //尾插法;
  • void linkBefore(E e, Node succ); //在某个节点前插入元素e
  • private E unlinkFirst(Node f); //删除头部元素
  • private E unlinkLast(Node l); //删除尾部元素
  • E unlink(Node x); // 删除非空元素x

3.3 add操作

  • public boolean add(E e); //在链表尾部添加元素;
  • public void add(int index, E element); //在指定位置插入元素element,下标也是从0开始计算的
  • public boolean addAll(Collection<? extends E> c); 添加整个集合
  • public boolean addAll(int index, Collection<? extends E> c); //在指定位置添加集合,下标从0开始计算
  • public E set(int index, E element); //将指定位置的元素设置为element,注意和add的区别,set操作List的size不会增加
public void add(int index, E element) {
    //检查下标合法性
    checkPositionIndex(index);

    if (index == size)
        //在尾部插入
        linkLast(element);
    else
        //在指定位置插入
        linkBefore(element, node(index));
}

由于底层使用链表,所以LinkedList不会有扩容机制。每次add过后,LinkedList的结构如下:

licationFactory.Init()进行初始化。在Init()中,先获取Global.asax文件的完整路径,然后调用CompileApplication()对Global.asax进行编译。

3.4 remove操作

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

//判断相等的标准也是两个对象通过equals方法比较相等
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;
}

//清空链表
public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

3.5 查询操作

查询方法用来查询LinkedList中是否包含某个元素,常用的查询方法有如下几个(和ArrayList中的一致):

代码效率较高,我们开发过程中可以借鉴使用elementData=Arrays.copyOf(elementData,newCapacity);addAll(Collection<?extends

  • public boolean contains(Object o);
  • public int indexOf(Object o);
  • public int lastIndexOf;
  • public E get(int index)。
public boolean contains(Object o) {
    return indexOf(o) != -1;
}
//判断的标准也是equals方法
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;
}

3.6 其他方法

由于LinkedList还实现了Deque这个接口,所以这个类还包含了许多其他方法。这些方法在介绍Queue时在整理。

t,注意和add的区别,set操作List的size不会增加publicvoidadd(intindex,Eelement){//检查下标合法性checkPositionIndex(index);if

3.7 LinkedList小结

  • LinkedList基于环形双向链表方式实现,无容量的限制;
  • 添加元素时不用扩容(直接创建新节点,调整插入节点的前后节点的指针属性的指向即可);
  • 线程不安全;
  • get(int index):需要遍历链表;
  • remove(Object o)需要遍历链表;
  • remove(int index)需要遍历链表;
  • contains(E)需要遍历链表。

4. 线程安全的List

上面提到的ArrayList和LinkedList都是非线程安全的,如果想要得到线程安全的类,可以通过线面的操作进行包装。

链接。      四、请求到达应用程序      惯例,先上图。HTTPRunt

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

以上代码返回的是一个SynchronizedList。这个类和Vector一样,也是线程安全的。Vector是java.util包中的一个类,而SynchronizedList是java.util.Collections中的一个静态内部类。这两个类都是List的子类,而且都是线程安全的。这两个类有如下的区别:

订 AuthenticateRequest 事件可确保在处理附加的模块或事件处理程序之前对请求进行身份验证 PostAuthenticateRequest当安全模块已建立

  • 他们实现同步的方式不一样,Vector使用同步方法来实现同步,SynchronizedList使用同步代码块来实现同步,只是用同步代码块将ArrayList的方法封装了下;
  • 两个扩容的机制不一样,Vector扩容成原来的2倍,但是SynchronizedList扩容成原来的1.5倍;
  • SynchronizedList有很好的扩展和兼容功能,他可以将所有的List的子类转成线程安全的类;
  • SynchronizedList中的方法不全都是同步的,获取迭代器方法listIterator()就不是同步的,所以在使用迭代器进行遍历时要手动进行同步处理(或者使用for循环,再调用get方法)。

这边需要注意的是虽然上述两个类是线程安全的,但是如果我们在迭代时进行增减元素操作,仍然会有fast-fail异常。也就是说线程安全和快速失败机制是无关的,快速失败机制的目的是为了防止在迭代元素的过程中有其他线程改变了当前集合的元素。线程安全是为了解决数据脏读等问题。

ity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//minCapacityisusuallyclosetosize,soth

5. 一个注意点

为了将数组转换为ArrayList,开发者经常会这样做:

的常见操作:privatevoidlinkFirst(Ee);//头插法;voidlinkLast(Ee);//尾插法;voidlinkBefore(Ee,Nodesucc);//在某个节点前插入元素

List<String> list = Arrays.asList(arr);

使用Arrays.asList()方法可以得到一个ArrayList,但是得到这个ArrayList其实是定义在Arrays类中的一个私有的静态内部类。这个类虽然和java.util.ArrayList同名,但是并不是同一个类。java.util.Arrays.ArrayList类中实现了set(), get(), contains()等方法,但是并没有定义向其中增加元素的方法。也就是说通过Arrays.asList()得到的ArrayList的大小是固定的。

介绍,今天就来详细的说一下这个。二、到达IIS之前    请看下面这个流程图。从用户打开浏览器到请求到达服务器,这些都是需要我们去配置就行了,这里面有一些知识点

如果在开发过程中,想得到一个真正的ArrayList对象(java.util.ArrayList的实例),可以通过以下方式:

Webform和RazorViewEngines.Engines.Clear();//注册你自己的View引擎ViewEngines.Engines.Add(newCustomViewEngine()

ArrayList<String> arrayList = new ArrayList<String>(Arrays.asList(arr));

java.util.ArrayList中包含一个可以接受集合类型参数的构造函数。因为java.util.Arrays.ArrayList这个内部类继承了AbstractList类,所以,该类也是Collection的子类。

,newArrayList(2));避免数组扩容,引起的效率下降;1.2add方法向ArrayList中添加元素常用的两个方法是:add(Ee);addAll(Collection<?exten

6. 总结

学东西的最终目的是为了能够理解、使用它。下面先概括的说明一下各个List的使用场景。如果涉及到可变长度的“数组”,应该首先考虑用List,具体的选择哪个List,根据下面的标准来取舍。

点(JDK1.8中的代码,其他版本的会有不同),同时还定义了头尾指针:...transientintsize=0;transientNode<E>first;transientNode&l

(01) 对于需要快速插入,删除元素,应该使用LinkedList。

。如果在开发过程中,想得到一个真正的ArrayList对象(java.util.ArrayList的实例),可以通过以下方式:ArrayList<String>arrayList=newA

(02) 对于需要快速随机访问元素,应该使用ArrayList。
(03) 对于“单线程环境” 或者 “多线程环境,但List仅仅只会被单个线程操作”,此时应该使用非同步的类(如ArrayList)。对于“多线程环境,且List可能同时被多个线程操作”,此时,应该使用同步的类(如Vector),或者通过Collections工具类将ArrayList和LinkedList包装成线程安全的类再使用。

r执行,目的是对访问用户的认证。在MVC5之前,认证和授权都是通过AuthorizationFilter来实现的。然后是AuthorizationFilter这个主要是验证授权的,授权验证通过后执行的

7. 参考

文章版权声明:除非注明,否则均为本站原创文章,转载或复制请以超链接形式并注明出处。
分享到:
赞 (0

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

发表评论

快捷回复:

评论列表 (有 0条评论, 694人围观) 参与讨论