Java集合概述(上)

前言

先说说,为什么要写这么一篇博客(我总是喜欢写原因)。因为最近到年底了,正好又要准备面试,所以在做各方面的技术总结。而Java集合是Java非常重要的一部分,自己前前后后也花了不少时间学习,但是一直比较零散。所以,打算趁着这个机会,来写一个总结。

由于能力有限,这方面没有足够积累,如果有什么问题,还请指出。谢谢。

集合分类,主要分为:

  • Collection(继承Iterable接口):按照单个元素存储的集合
    • List:一种线性数据结构的主要体现。有序,可重复
    • Set:一种不允许出现重复元素的集合。无序(插入顺序与输出顺序不一致),不可重复
    • Queue:一种先进先出(FIFO)的数据结构。有序,可重复,先进先出
  • Map(无继承接口):按照K-V存储的Map
    • keySet:可以查看所有的Key。底层实现各不相同。ConcurrentHashMap则是采用的自定义实现的KeySetView内部静态类(实现了Set接口),而HashMap这样的AbstractMap子类,则是是Set接口
    • values:同上,ConcurrentHashMap采用ValueSetView,HashMap采用Set接口
    • entrySet:同上,ConcurrentHashMap采用EntrySetView,HashMap采用Set接口

原本Map是打算按照 AbstractMap;SortedMap;ConcurrentMap;来分类,但是发现这个分类属于理论价值,大于使用价值,也可能是我现在层次不够吧。最后还是学着孤尽大佬在《码处高效》中那样,通过三个视图,来观察Map。具体后面阐述,我也只是阐述其中部分的Map。

论述方面,我主要会从数据组织方式(底层数据存储方式),数据处理方式(如HashMap的put操作等),特点小结结三个方面进行阐述。但是由于内容量的问题,这里并不会非常细致地阐述代码实现。

最后,由于内容量的缘故,这部分内容,我将分为两个部分。这篇博客主要论述List与Map,而Set与Queue放在另外一篇博客。

一,List

ArrayList

数据组织方式

     transient Object[] elementData; // non-private to simplify nested class access 

ArrayList的底层是一个Object类型的数组。那么ArrayList就有着和数组一样的特点:随机查询快,但数据的插入,删除慢(因为很可能需要移动其他元素)。

数据处理方式

add
     public void add(int index, E element) {         // 校验index是否在0-size范围内,如果不是,抛出异常IndexOutOfBoundsException         rangeCheckForAdd(index);          // 这个操作后面有多个操作,总结一下,就是校验,判断是否需要扩容,扩容。         ensureCapacityInternal(size + 1);  // Increments modCount!!         // 通过System.arraycopy操作,为新添加的元素element,在elementData数组的对应index位置,腾出空间         System.arraycopy(elementData, index, elementData, index + 1,                          size - index);         // 紧跟着上面的操作elementData数组的index位置,赋值为element         elementData[index] = element;         // 数组元素数量+1         size++;     } 
grow
     // 简单来说, 就是根据所给的minCapacity,计算对应容量(2的幂次方),然后校验容量,最后扩容     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随机查询快(直接通过index定位数据中具体元素)
  • ArrayList插入与删除操作慢(涉及数组元素移动操作System.arraycopy,还可能涉及扩容操作)
  • ArrayList是容量可变的(自带扩容操作,初始化,默认为DEFAULT_CAPACITY=10)
  • ArrayList是非线程安全的(没有线程安全措施)

补充:

  • ArrayList的默认容量为10(即无参构造时)
  • 出于性能考虑,避免多次扩容,最好在初始化时设置对应size(即使后面不够了,它也可以自动扩容)

LinkedList

数据组织方式

     private static class Node<E> {         E item;         Node<E> next;         Node<E> prev;          Node(Node<E> prev, E element, Node<