百木园-与人分享,
就是让自己快乐。

Java集合解析

 

一、什么是集合?

  顾名思义集合就相当于一个容器,容器就可以存储,只不过在java中存储的是对象,而对象本身是在堆内存中的,所以集合中存放的是一个个对象的引用。

二、集合和数组的区别?

  问:我们都知道数组也可以存储元素,为什么还需要集合?

  答:首先数组是一个线性的序列(线性序列指线性结构中所有节点按其关系可以排成一个序列,例1、2、3........100),所以可以快速的访问其中的元素,而数组被创建的时候,容量是不变的。

  那么集合具体和数组有哪些区别?

  1、创建数组必须声明它容纳元素的类型,而集合不需要声明

 1 package collection;
 2 
 3 import java.util.ArrayList;
 4 
 5 /**
 6  * 创建数组和创建集合
 7  */
 8 public class Demo1 {
 9 
10     public static void main(String[] args) {
11         //第一种方式,数组长度为6
12         int[] arr1 = new int[6];
13 
14         //第二种方式,数组长度为5
15         int[] arr2 = {2,3,4,5,6};
16 
17         //第三种方式,数组长度为6
18         int[] arr3 = new int[]{1,2,3,4,5,6};
19         
20         //创建集合
21         ArrayList list = new ArrayList();
22     }
23 
24 
25 }

  2、由上代码可以看出,一个数组的实例具有固定的大小,一旦创建就无法改变容量了,而集合可以动态的扩展容量,可以根据需要动态改变大小,非常灵活,能够满足我们更多的需求。

    集合动态扩展容量代码示例:

 1 package collection;
 2 
 3 import java.util.ArrayList;
 4 
 5 /**
 6  * 创建数组和创建集合
 7  */
 8 public class Demo1 {
 9 
10     public static void main(String[] args) {
11         //创建集合
12         ArrayList list = new ArrayList();
13         list.add(\"张三\");
14         System.out.println(list.size());
15         list.add(\"李四\");
16         System.out.println(list.size());
17     }
18 
19 
20 }

代码输出结果:

 由此证明,集合是可以随着添加对象的多少,大小也随之改变。

  3、当我们创建一个数组,那么这个数组只能存放自定义的类型,但是集合存放的类型可以是多种(不加泛型时添加的类型是Object)

  集合代码示例:

 1 package collection;
 2 
 3 import java.util.ArrayList;
 4 
 5 public class Demo1 {
 6 
 7     public static void main(String[] args) {
 8         
 9         ArrayList list = new ArrayList();
10         list.add(\"张三\");
11         list.add(1);
12         System.out.println(list);
13     }
14 
15 
16 }

  代码输出结果:

   数组代码示例:

由此得出,当我们声明了数组是什么类型,那么就只能存放什么类型的元素。

  4、集合以类的形式存在,具有封装、继承、多态、等类的特性,通过简单的方法和属性调用即可实现各种复杂操作。

 三、集合的体系结构

  下图所示:

 

   1、集合Collection

    问:什么是Collection集合?

    答:Collection是集合的顶级接口,它没有具体的实现类,具有两个子接口List和Set

  2、Collection具有两个子接口,那么这两个子接口具体的区别是什么?

    首先list和set都继承自Collection这个顶级接口

    list特点是元素有放入顺序,可以重复

    set特点是元素无放入顺序,不可重复

    list支持for循环,可以通过下标来遍历,也可以用迭代器来遍历

    set只能用迭代器,因为无序,故无法使用下标

  3、ArrayList原理

    特点:查询快,增删慢,线程非安全

    原因:底层是数组,数组里的元素都有相对应的下标,根据下标去查询效率高

    原因:底层是数组,数组中的元素进行增加或者删除的时候,就需要对数组进行扩容或缩容的操作,又因数组创建出来时容量大小是固定的,要进行扩容或缩容的操作那么就要重新创建一个新

        的数组,然后把旧数组中的元素拷贝到新数组中,若原数组中的数据量非常大的时候那么效率就非常低下。

    原因:ArrayList默认数组大小为10,假设现在已经添加进去了9个元素,即size=9,现在有两个线程,线程A和线程B要往这个数组中添加元素,

       当线程A开始进入了add方法,它获取到的size值为9,在进行容量判断的时候,发现需求大小为10,而elementDate的大小也为10,可以容纳,于是不再扩容,

       同时,线程B也进入到了add方法,获取到的size值和线程A一样,判断容量的时候,发现也可以容纳,也无需扩容,

       这时线程A开始了设置值的操作,此时size的值变为了10,线程B也开始了设置值的操作,但是elementDate并没有进行扩容,下标最大为9,这时就会报出一个数组越界的异常。

    线程不安全代码实现:

 1 package collection;
 2 
 3 import java.util.ArrayList;
 4 
 5 public class Demo3 {
 6     public static void main(String[] args) {
 7         ArrayList<Integer> list = new ArrayList<Integer>();
 8         //线程A将0-1000添加到list
 9         new Thread(new Runnable() {
10             @Override
11             public void run() {
12                 for (int i = 0; i <1000 ; i++) {
13                     list.add(i);
14                     try {
15                         Thread.sleep(1);
16                     } catch (InterruptedException e) {
17                         e.printStackTrace();
18                     }
19                 }
20             }
21         }).start();
22         //线程B将1000-2000添加到列表
23         new Thread(new Runnable() {
24             @Override
25             public void run() {
26                 for (int i = 1000; i <2000 ; i++) {
27                     list.add(i);
28                     try {
29                         Thread.sleep(1);
30                     } catch (InterruptedException e) {
31                         e.printStackTrace();
32                     }
33                 }
34             }
35         }).start();
36 
37         // 打印所有结果
38         for (int i = 0; i < list.size(); i++) {
39             System.out.println(\"第\" + (i + 1) + \"个元素为:\" + list.get(i));
40         }
41     }
42 }

    结论:

      1、ArrayList中维护了一个Object类型的数组elementDate,类型是Object类型

      2、当创建ArrayList对象时,如果使用的是无参构造器,则初始容量为0,第一次添加,则扩容elementDate为10,如需再次扩容,则扩容elementDate为1.5倍

      3、如果使用有参构造器,则初始容量为指定大小,如果需要扩容,则直接扩容elementDate为1.5倍

  4、LinkedList原理

    底层是一个带头/尾指针的双向链表,可以快速的对头/尾节点进行操作,双向链表,头节点均指first,尾节点均指last

    特点:1、查询慢,增删快、非线程安全的

    linkedList本质是一个双向链表,由一个个的node对象组成

    

    原理:

      linkedlist由一个个node节点组成,每一个node持有前后节点的引用,也叫做指针,Node中有三个属性:元素对象、前一个节点指针、后一个节点指针、构造函数也由这三个属性去组成,

      在linkedlist的添加方法中,会创建一个Node对象,持有前后节点的信息,添加到最后节点之后。

    LinkedList添加实现:

 1 package collection;
 2 
 3 public class Demo4 {
 4     private static class Node<E>{
 5         E item;//当前元素对象
 6         Node<E> next;//下一个
 7         Node<E> prev;//前一个
 8 
 9         Node(Node<E> prev, E element, Node<E> next) {
10             this.item = element;
11             this.next = next;
12             this.prev = prev;
13         }
14 
15         protected transient int modCount = 0;
16         transient int size = 0;
17         transient Node<E> first;
18         transient Node<E> last;
19 
20         public boolean add(E e) {
21             linkLast(e);
22             return true;
23         }
24         void linkLast(E e) {
25             final Node<E> l = last;//把最后一个节点的last作为当前节点
26             final Node<E> newNode = new Node<>(l, e, null);
27             last = newNode;//把最后一个节点设置为last
28             if (l == null)//如果最后一个节点为空,添加的这个节点即是最后一个节点也是第一个节点
29                 first = newNode;
30             else
31                 l.next = newNode;
32             size++;
33             modCount++;
34         }
35     }
36 
37 }

    从上面源码可以看出,当linkedlist添加一个元素时,会默认往linkedlist最后一个节点添加,把最后一个节点作为当前节点,用当前节点添加参数e、null作为一个新的Node对象,将当前节点设置为last,如果最后一个节点为空,那么当前添加的这个节点即使last也是first,当前linkedlist的size+1,表示结构改变次数的对象也+1。

 

 1 E unlink(Node<E> x) {//unlink删除连接
 2             // assert x != null;
 3             final E element = x.item;
 4             final Node<E> next = x.next;
 5             final Node<E> prev = x.prev;
 6 
 7             if (prev == null) {//首先判断上一个节点的引用是否为null,如果为null,那么说明当前节点就是第一个节点
 8                 first = next;
 9             } else {//如果不为null,说明当前节点不是第一个节点,则将当前的next赋值给prev.next,x.prew变为null
10                 prev.next = next;
11                 x.prev = null;
12             }
13 
14             if (next == null) {//如果下一个节点next为null,即为最后一个元素,则链表last就是x的前一个节点
15                 last = prev;
16             } else {//如果不为null,即不为最后一个元素,则将当前节点的prew赋值给next.prew
17                 next.prev = prev;
18                 x.next = null;
19             }
20             x.item = null;
21             size--;
22             modCount++;
23             return element;
24         }

    由上分析而来linkedlist的删除中,也是改变节点之间的引用关系去实现的。

    如果前一个节点为null,那么当前节点就为第一个元素,则first= x的下一个节点,

    如果前一个节点不为null,即当前节点就不是第一个元素,则将当前节点的next赋值给上一个节点的next,当前节点的前一个节点设置为null

    如果下一个节点为null,那么当前节点就是最后一个元素,则last=x的前一个节点

    如果下一个节点不为null,那么当前节点就不是最后一个元素,则将当前节点的prev赋值给下一个节点的prev

 1 public E get(int index) {
 2     checkElementIndex(index);
 3     return node(index).item;
 4 }
 5 private void checkElementIndex(int index) {
 6     if (!isElementIndex(index))//如果当前传入的index不是linkedlist中的元素,那么抛出异常
 7         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 8 }
 9 private boolean isElementIndex(int index) {
10     return index >= 0 && index < size;//判断下标是否在0~size之间
11 }
12 Node<E> node(int index) {
13     // assert isElementIndex(index);
14 
15     if (index < (size >> 1)) {
16         Node<E> x = first;
17         for (int i = 0; i < index; i++)
18             x = x.next;
19         return x;
20     } else {
21         Node<E> x = last;
22         for (int i = size - 1; i > index; i--)
23             x = x.prev;
24         return x;
25     }
26 }

    查询是根据传入的index下标去判断是否为linkedList中的元素,

    调用node(index)方法,将size向右移一位,即size/2,判断size在linkedlist的前半部分还是后半部分

    如果在前半部分,即index下标小于size/2,从first节点开始遍历

    如果在后半部分,即index下标大于size/2,从last节点开始遍历

    由此得出,链表越长,遍历时间越长,对应查询时间也就越长

  5、使用场景:

    ArrayList使用在查询比较多,增加和删除比较少的情况下

    LinkedList使用在查询比较少,增加和删除比较多的情况下

  6、什么是Vector?

    Vector是矢量队列,是JDK1.0版本添加的类,

    Vector继承于AbstractList,实现了List,所以支持相关的添加、删除、更改、遍历等功能

    Vector实现了RandomAccess接口,提供了随机访问的功能

    Vector实现了Cloneable接口,它能被克隆。

    特点:线程安全,执行效率低,顺序存储,增删较慢。

  7、Vector和ArrayList的区别?

    1、Vector中的操作是线程安全的,因为Vector中所有的方法都是被synchronized关键字修饰的,ArrayList是线程不安全的

    2、Vector可以指定增长因子,如果不指定,每次扩容为原数组的2倍,如果指定,那就是原数组大小+增长因子

    3、ArrayList支持序列化,而Vecor不支持

  8、List遍历方式

 1 package collection;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Iterator;
 5 
 6 public class Dem6 {
 7     public static void main(String[] args) {
 8         ArrayList<Integer> arrayList = new ArrayList<>();
 9         for (int i = 0; i <100 ; i++) {
10             arrayList.add(i);
11         }
12         //第一种遍历方式,转换成数组
13         Object[] arrays = arrayList.toArray();
14         for (Object array: arrays) {
15             System.out.print(array);
16         }
17         //第二种遍历方式,使用foreach
18         for (Integer array:arrayList) {
19             System.out.println(array);
20         }
21         //第三种遍历方式,使用for循环
22         for (int i = 0; i <arrayList.size() ; i++) {
23             System.out.println(arrayList.get(i));
24         }
25         //第四种,迭代器
26         Iterator iterator = arrayList.iterator();
27         while (iterator.hasNext()){//这里相当于一个标尺,开始时指向为0的地方,判断是否有下一个元素
28             System.out.println(iterator.next());
29         }
30     }
31 }

   9、CopyOnWriteArrayList简介

    简称COW,根据名字来看就是写入时复制,意思是大家共同去访问这个资源,如果有人想要去修改这个资源的时候,那么需要复制一个副本,去修改这个副本,对于其他人访问的资源还是原来的不影响。

    CopyOnWriteArrayList底层也是数组实现的,删除修改和添加元素操作时都需要加锁,只有读取的操作不会加锁。那么CopyOnWriteArrayList也就是线程安全的。

    问:为什么线程安全的List推荐用CopyOnWriteArrayList,而不是Vector?

    答:Vector和CopyOnWriteArrayList都是线程安全的list,底层都是数组实现的,

    Vector中的所有方法都被synchronized关键字修饰,而CopyWriteArrayList其中的读操作是不加锁的,因此CopyWriteArrayList的读取性能是远高于Vector的

    而Vector每次扩容,都是原数组的两倍,CopyWriteArrayList完全不需要扩容,通过复制副本去修改或者增加,新副本的长度正好是元素的长度,不会造成冗余。

    在开发中,读取操作会远超于其他操作,因此使用CopyWriteArrayList效率更高。

    

    

 


来源:https://www.cnblogs.com/zhangbinlin/p/16415623.html
本站部分图文来源于网络,如有侵权请联系删除。

未经允许不得转载:百木园 » Java集合解析

相关推荐

  • 暂无文章