Vector、ArrayList、LinkedList的理解

最近感悟：天将降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为，所以动心忍性，曾益其所不能。

问题：

对比Vector、ArrayList、LinkedList有何区别？

知识点补充

  1. 集合框架的整体设计（并发包这里没有添加进来）
    image
  • [x] List：也就是我们介绍的有序集合，它提供了方便的访问、插入、删除操作。
  • [x] Set：Set是不允许重复元素的，也就是不存在两个对象equals返回true。我们日常开发中很多需要保证元素唯一性的场合。
  • [x] Queue/Deque：Java提供的标准队列实现，支持FIFO、LIL等特定行为。
  1. Set基本特征和典型使用场景。
  • [x] TreeSet：TreeSet代码里实现实际默认是利用TreeMap实现的,所有插入的元素以键的形式插入到TreeMap里面，支持自然排序访问，但是插入、删除、包含等操作相对低效（Log(n)时间）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
    * Constructs a new, empty tree set, sorted according to the
    * natural ordering of its elements.  All elements inserted into
    * the set must implement the {@link Comparable} interface.
    * Furthermore, all such elements must be <i>mutually
    * comparable</i>: {@code e1.compareTo(e2)} must not throw a
    * {@code ClassCastException} for any elements {@code e1} and
    * {@code e2} in the set.  If the user attempts to add an element
    * to the set that violates this constraint (for example, the user
    * attempts to add a string element to a set whose elements are
    * integers), the {@code add} call will throw a
    * {@code ClassCastException}.
    */
   public TreeSet() {
       this(new TreeMap<E,Object>());
   }

这里有一个典型的例子，在开发相关支付请求参数进行签名的时候会对请求参数进行进行自然排序，如支付宝支付：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static Map<String, String> getSortedMap(RequestParametersHolder requestHolder) {
        Map<String, String> sortedParams = new TreeMap<String, String>();
        AlipayHashMap appParams = requestHolder.getApplicationParams();
        if (appParams != null && appParams.size() > 0) {
            sortedParams.putAll(appParams);
        }
        AlipayHashMap protocalMustParams = requestHolder.getProtocalMustParams();
        if (protocalMustParams != null && protocalMustParams.size() > 0) {
            sortedParams.putAll(protocalMustParams);
        }
        AlipayHashMap protocalOptParams = requestHolder.getProtocalOptParams();
        if (protocalOptParams != null && protocalOptParams.size() > 0) {
            sortedParams.putAll(protocalOptParams);
        }
        return sortedParams;
    }

  1. HashSet通过Hash算法，理想情况下，如果哈希散列正常，可以提供常数时间的添加、删除、包含等操作，但是它不保证有序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@ReactMethod
    public void setPushTime(ReadableMap map) {
        try {
            mContext = getCurrentActivity();
            ReadableArray array = map.getArray("days");
            Set<Integer> days = new HashSet<Integer>();
            for (int i=0; i < array.size(); i++) {
                days.add(array.getInt(i));
            }
            int startHour = map.getInt("startHour");
            int endHour = map.getInt("endHour");
            JPushInterface.setPushTime(mContext, days, startHour, endHour);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
  1. LinkedHashSet：内部构建了一个记录插入顺序的双向链表，因此提供了按照插入顺序遍历的能力，与此同时，也提供了常数时间的添加、插入、删除、包含操作。性能略低于HashSet，因为需要维护链表的开销。
1
2
3
4
5
6
/**
  * Constructs a new empty instance of {@code LinkedHashSet}.
  */
 public LinkedHashSet() {
     super(new LinkedHashMap<E, HashSet<E>>());
 }

从源码中可以看出，HashSet其实以HashMap为基础实现的。

  1. 在遍历元素的时候，HashSet性能受自身容量影响，所以初始化的时候，除非有必要，不然不要将其背后的HashMap容量设置过大。而对于LinkedHashMap遍历性能只和元素个数有关系。

  2. 上面所说的集合都是线程不安全的，除了并发包中线程安全容器，在Collections也提供了一些线程安全工具类（简单粗暴的synchronized保证）来保证线程安全。如：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    static class SynchronizedCollection<E> implements Collection<E>, Serializable {
            private static final long serialVersionUID = 3053995032091335093L;
            final Collection<E> c;
            final Object mutex;
            SynchronizedCollection(Collection<E> var1) {
                this.c = (Collection)Objects.requireNonNull(var1);
                this.mutex = this;
            }
            SynchronizedCollection(Collection<E> var1, Object var2) {
                this.c = (Collection)Objects.requireNonNull(var1);
                this.mutex = Objects.requireNonNull(var2);
            }
            public int size() {
                Object var1 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.size();
                }
            }
            public boolean isEmpty() {
                Object var1 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.isEmpty();
                }
            }
            public boolean contains(Object var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.contains(var1);
                }
            }
            public Object[] toArray() {
                Object var1 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.toArray();
                }
            }
            public <T> T[] toArray(T[] var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.toArray(var1);
                }
            }
            public Iterator<E> iterator() {
                return this.c.iterator();
            }
            public boolean add(E var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.add(var1);
                }
            }
            public boolean remove(Object var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.remove(var1);
                }
            }
            public boolean containsAll(Collection<?> var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.containsAll(var1);
                }
            }
            public boolean addAll(Collection<? extends E> var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.addAll(var1);
                }
            }
            public boolean removeAll(Collection<?> var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.removeAll(var1);
                }
            }
            public boolean retainAll(Collection<?> var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.retainAll(var1);
                }
            }
            public void clear() {
                Object var1 = this.mutex;
                synchronized(this.mutex) {
                    this.c.clear();
                }
            }
            public String toString() {
                Object var1 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.toString();
                }
            }
            public void forEach(Consumer<? super E> var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    this.c.forEach(var1);
                }
            }
            public boolean removeIf(Predicate<? super E> var1) {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    return this.c.removeIf(var1);
                }
            }
            public Spliterator<E> spliterator() {
                return this.c.spliterator();
            }
            public Stream<E> stream() {
                return this.c.stream();
            }
            public Stream<E> parallelStream() {
                return this.c.parallelStream();
            }
            private void writeObject(ObjectOutputStream var1) throws IOException {
                Object var2 = this.mutex;
                synchronized(this.mutex) {
                    var1.defaultWriteObject();
                }
            }
        }

  3. 集合中提供的默认排序算法，具体是什么排序方式和设计思路。（这个在后续讲解算法的时候会详细介绍）

  4. Java9中标准类库中提供了一系列静态工厂方法。比如List.of()、Set.of()，大大简化了构建小的容器实例的代码量。
1
List<String> simpleList = List.of("hello","world");

回答问题

这三者都是实现集合框架中的List,也就是所谓的有序集合，具体功能上基本类似，比如：都能按照位置进行定位、都能插入和删除，都提供迭代器以遍历内容。但是在具体行为、性能、线程安全又有很大的差别。
Vector是Java早期提供的线程安全的动态数组，如果不需要线程安全，并不建议使用，毕竟同步是消耗性能的。Vector使用动态数组来保存数据，可以根据需要自动增加容量，当数组已经满的时候，会创建新的数组，并拷贝原有的数组数据。
ArrayList是应用更加广泛的集合，内部使用动态数组实现，线程不安全，所以效率会比较高。同样，根据需要自动增加容量，但是和Vector不一样，扩容的时候增加50%，而Vector是增加一倍。
LinkedList内部使用双向链表实现，便于插入和删除，不利于查询，也是线程不安全的。

参考：

  • 集合中部分源码
  • 极客时间APP核心技术第七讲| List simpleList = List.of(“hello”,”world”);
  • 自己写的Demo中部分代码

声明：此为原创，转载请联系作者

作者：微信公众号添加公众号-遛狗的程序员 ，或者可以扫描以下二维码关注相关技术文章。

qrcode_for_gh_1ba0785324d6_430.jpg

当然喜爱技术，乐于分享的你也可以可以添加作者微信号：

WXCD.jpeg

本文标题:Vector、ArrayList、LinkedList的理解

文章作者:黄尘

发布时间:2017-09-21, 23:04:44

最后更新:2018-08-21, 15:31:01

原始链接:https://huangchen0.github.io/2017/09/21/Vector、ArrayList、LinkedList的理解/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 问题：
  2. 2. 知识点补充
  3. 3. 回答问题
|