java集合框架使用原理分析

2019-08-09 00:00:00 集合 原理 框架

      集合是我们日常编程中可能用的很多的技术之一 使用频率极高 可能平时就会知道怎么去用 但是集合之间的关系与不同之处都不是很清楚 对它们的底层原理更甚 所以写词文章 让自己有一个更深的认识

集合是一个庞大的家族 今天先来说说这几个 ArrayList、LinkedList、Vector 

《java集合框架使用原理分析》

 

        ArrayList  由于它的底层是数组 数组我们都知道它的查询修改都是效率很高的 ArrayList也是如此 但是为什么查询修改效率高 插入和删除效率低较低呢 这就跟它的数据结构有关系呢 接下啦我们来看看ArrayList数据结构模型

 插入、删除:如果我们要想集合中插入一个数100 它的操作步骤是 先在集合中把要插入的位置的数32复制一份 然后再把后面的数往后移  我们不仅要复制数据 而且还要将数据往后移 如果这个集合的数据很多的话 那效率就会很低  进行删除的话后面的数据复制一份 同时数据都要像前面移动 效率也很低

 查询、修改: 修改如果进行查询 我们只需要通过数组下标就可以定位到数据 所以效率高 实际开发中 我们大部分是进行查询数据 所以ArrayList使用很广泛

任何事物都有两面性 不管是生活中 还是工作中 在编程也是同样适用的(因为编程也是人发明出来的嘛) 为了解决ArrayList的这一短板 聪明的程序员就使用另一个集合

 

 

《java集合框架使用原理分析》

 ArrayList 增删改查的源码

      从源码我们可以看出 不管是插入和删除元素的时候 ArrayList都会复制数组操作 这也就导致了它的效率不高

 

 1 //查询元素
 2  public E get(int index) {
 3 //检查元素是否越界
 4         rangeCheck(index);
 5 
 6         return elementData(index);
 7     }
 8 
 9 
10 //按顺序添加元素
11  public boolean add(E e) {
12        //确认开启扩容机制 
13         ensureCapacityInternal(size + 1);  // Increments modCount!!
14         elementData[size++] = e;
15         return true;
16     }
17 
18 //在指定位置插入元素
19  public void add(int index, E element) { 
20        //检查索引是否越界
21         rangeCheckForAdd(index);
22        //确认开启扩容机制
23          ensureCapacityInternal(size + 1);  // Increments modCount!!
24        //复制数组
25         System.arraycopy(elementData, index, elementData, index + 1,
26                          size - index);
27       //替换元素
28         elementData[index] = element;
29         size++;
30     }
31 
32 
33 
34 
35 //移除某个元素
36  public E remove(int index) {
37         rangeCheck(index);
38 
39         modCount++;
40         E oldValue = elementData(index);
41 
42         int numMoved = size - index - 1;
43         if (numMoved > 0)
//复制数组 44 System.arraycopy(elementData, index+1, elementData, index, 45 numMoved); 46 elementData[--size] = null; // clear to let GC do its work 47 48 return oldValue; 49 } 50 51 52

  LinkedList 

       LinkedList它的底层是双向链表实现的非线程安全的集合,它是一个链表结构,不能像数组一样随机访问,必须是每个元素依次遍历直到找到元素为止。其结构的特殊性导致它查询数据慢。 接下来我们来看看它的结构模型

插入、删除 :因为是链表结构 所以它的插入效率很高 (如果在14 和 18之间插入一个33 的话,链表直接会将连接到18的链子断开 然后连接上33所在的前节点  数据18的前节点再连接上33的后节点  如图2所示) 也就是说 插入一个数字我们只需要将(14 和 18 之间的)链表断开 再将14和33之间的链表连上即可  比ArrayList的数组复制效率高

查询、修改 :LinkedList 查询速度慢 因为它要遍历整个整个集合 直到找到元素为止 如果集合数组多的话 消耗的资源就多 而ArrayList是通过数组下标定位速度快 同样他也是线程不安全的

《java集合框架使用原理分析》

   《java集合框架使用原理分析》

linkedList

      在执行查询时 先判断元素是靠近头部还是尾部 如果是头部 若靠近头部,则从头部开始依次查询判断 

      执行插入时 判断是插入到中间还是尾部 如果插入到尾部 直接将尾节点的下一个指针指向新增节点。如果插入到中间 获取到当前节点的上一个节点(D) 并将D节点的后指针指向新的节点头指针 然后新增节点的下一个指针指向当前节点。

 1   //查询元素   
 2   public E get(int index) {
 3       //检查所引是否越界
 4       checkElementIndex(index);
 5          return node(index).item;
 6      }
 7 
 8 // 返回指定索引处的节点
 9 Node<E> node(int index) {
10   // 指定的索引值与链表大小右移一位,及除以 2 进行比较
11    if (index < (size >> 1)) { // 索引小,则从首节点向后扫描,直到索引值处
12    Node<E> x = first;
13     for (int i = 0; i < index; i++)
14      x = x.next;
15     return x;
16     } else { // 索引大,则从尾节点向前扫描,直到索引值处
17     Node<E> x = last;
18      for (int i = size - 1; i > index; i--)
19     x = x.prev;
20     return x;
21   }
22 }
23 
24 
25   //移除指定元素
26    public E remove(int index) {
27          checkElementIndex(index);
28          return unlink(node(index));
29     }
30  
31  //在指定位置添加元素
32    public void add(int index, E element) {
33        //检查所引是否越界  
34        checkPositionIndex(index);
35        // 在链表末尾天添加
36          if (index == size)
37              linkLast(element);
38          else
39              linkBefore(element, node(index));
40     }
41  
42    private static class Node<E> {
43          E item;
44          //头节点
45          Node<E> next;
46        //尾节点
47          Node<E> prev;
48          Node(Node<E> prev, E element, Node<E> next) {
49             this.item = element;
50              this.next = next;
51              this.prev = prev;
52          }
53      }
54  
55   /**
56       * Links e as last element.
57       */
58      void linkLast(E e) {
59          //用l来临时保存未插入前的last节点
60          final Node<E> l = last;
61         //创建一个值为e的新节点 添加第一个元素时 l = null
62          final Node<E> newNode = new Node<>(l, e, null);
63          //将新节点赋值的last
64         last = newNode;
65         if (l == null)
66              first = newNode;
67          else
68             l.next = newNode;
69          size++;
70          modCount++;
71      }

  Vector 

       Vector的数据结构和使用方法 跟ArrayList相同 不同之处在于Vector是线程安全的 几乎所有的对数据操作的方法都被synchronized关键字修饰  synchronized是线程同步的 当一个线程获得Vector对象锁的时候 其它的线程必须等到它执行完毕之后(锁被释放)才能执行  

《java集合框架使用原理分析》

总结

1.ArrayList 它的底层是一个数组 查询修改数据快(通过下标定位) 但是插入删除数据比较慢 (插入数据慢是因为复制数组耗时)  为了改进这个缺点 于是就有了LinkedList数组 它是一个链表结构 插入和删除数据很快(只需要修改指针引用) 但是查询和修改数效率低(他要查询到整个链表从第一个开始寻找 一直找到为止)

2.ArrayList 和LinkedList都是线程不安全的

3.Vector是线程安全的 但是效率低 当我们执行单个线程的时候ArrayList的效率高于Vector 

 

相关文章