第8讲 | 对比Vector、ArrayList、LinkedList有何区别？

精选留言(51)

• 

  雷霹雳的爸爸 置顶

  在这个题目下，自然就会想到优先级队列了，但还需要额外考虑vip再分级，即同等级vip的平权的问题，所以应该考虑除了直接的和vip等级相关的优先级队列优先级规则问题，还得考虑同等级多个客户互相不被单一客户大量任务阻塞的问题，数据结构确实是基础，即便这个思考题考虑的这个场景，待调度数据估计会放在redis里面吧

  作者回复: 赞

  2018-05-22

   1

   64
• 

  孙晓刚 置顶

  精选第一个对于读写效率问题，我觉得表述有问欠缺，或者说不能那么绝对。
  1、并不是所有的增删都会开辟新内存，没有开辟新内存的尾部增，效率也是杠杠的。
  2、尾部删除也不需要开辟新内存，只是移出最后一个对象。
  之前我也是接收了ArrayList的特性随机访问快，增删效率差。直到看到源码才知道，没那么绝对。
  直接导致结果就是本身适合使用ArrayList的场景会因为这个笼统的说法而选LinkedList

  作者回复: 嗯，我文中特意强调了不包括尾部

  2018-05-22

  

   23
• 

  L.B.Q.Y 置顶

  请教老师个问题，Collection接口的声明是带范型的，其中定义的Object[ ] toArray()方法为什么不是范型方式的？有什么原因吗？

  作者回复: 按照javadoc，我觉得这个方法设计目的，就是让调用者精确控制类型；里面声明了，toArray(new Object[0])等同于toArray()

  2018-05-23

  

   7
• 

  公号-代码荣耀

  Vector、ArrayList、LinkedList均为线型的数据结构，但是从实现方式与应用场景中又存在差别。
  
  1 底层实现方式
  ArrayList内部用数组来实现；LinkedList内部采用双向链表实现；Vector内部用数组实现。
  
  2 读写机制
  ArrayList在执行插入元素是超过当前数组预定义的最大值时，数组需要扩容，扩容过程需要调用底层System.arraycopy()方法进行大量的数组复制操作；在删除元素时并不会减少数组的容量（如果需要缩小数组容量，可以调用trimToSize()方法）；在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。
  
  LinkedList在插入元素时，须创建一个新的Entry对象，并更新相应元素的前后元素的引用；在查找元素时，需遍历链表；在删除元素时，要遍历链表，找到要删除的元素，然后从链表上将此元素删除即可。
  Vector与ArrayList仅在插入元素时容量扩充机制不一致。对于Vector，默认创建一个大小为10的Object数组，并将capacityIncrement设置为0；当插入元素数组大小不够时，如果capacityIncrement大于0，则将Object数组的大小扩大为现有size+capacityIncrement；如果capacityIncrement<=0,则将Object数组的大小扩大为现有大小的2倍。
  
  3 读写效率
  
  ArrayList对元素的增加和删除都会引起数组的内存分配空间动态发生变化。因此，对其进行插入和删除速度较慢，但检索速度很快。
  
  LinkedList由于基于链表方式存放数据，增加和删除元素的速度较快，但是检索速度较慢。
  
  4 线程安全性
  
  ArrayList、LinkedList为非线程安全；Vector是基于synchronized实现的线程安全的ArrayList。
  
  需要注意的是：单线程应尽量使用ArrayList，Vector因为同步会有性能损耗；即使在多线程环境下，我们可以利用Collections这个类中为我们提供的synchronizedList(List list)方法返回一个线程安全的同步列表对象。
  
  问题回答
  
  利用PriorityBlockingQueue或Disruptor可实现基于任务优先级为调度策略的执行调度系统。

  2018-05-22

   1

   140
• 

  约书亚

  既然是Java的主题，那就用PriorityBlockingQueue吧。
  如果是真实场景肯定会考虑高可用能持久化的方案。
  其实我觉得应该参考银行窗口，同时三个窗口，就是三个队列，银台就是消费者线程，某一个窗口vip优先，没有vip时也为普通客户服务。要实现，要么有个dispatcher，要么保持vip通道不许普通进入，vip柜台闲时从其他队列偷

  作者回复: 有道理

  2018-05-22

  

   49
• 

  linco_66

  由于要处理的任务有前后顺序关系，所以首先想到使用优先队列。使用 PriorityQueue，将VIP用户的优先级设置为最高，优先处理。借鉴操作系统中的调度算法，对于其他用户，我们还可以设计各种公平的优先级选择算法（基于排队先后顺序，基于调度任务所需的时间长短（操作系统中的短作业优先算法）排序、高响应比（（所用时间+等待时间）/等待时间）优先进行排序），与 PriorityQueue 结合使用。
  类似场景大多就是基于队列的数据结构了。实际工具的话，消息队列（MQ）就是很直接的例子了。可以使用消息队列对用户请求进行削锋操作，前台快速响应，后台私下进行处理操作。
  除此之外可以想到优化：利用分布式系统的优点，将VIP用户的请求分发到运算力更高的服务器上进行处理。达到高可用的特点！

  作者回复: 非常不错的总结

  2019-01-07

  

   18
• 

  jackyz

  集合：就像是一种容器。用于存储、获取、操作对象的容器。
  
  1. 数组的弊端
  ①数组的长度不可变 ②数组没有提供可以查看有效元素个数的方法
  
  2. 集合的特点
  ①集合的长度是可变的
  ②集合可以存储任意类型的对象
  ③集合只能存储对象
  
  3. 集合框架
  java.util.Collection : 集合层次的根接口
      |--- java.util.List: 有序的，可以重复的。
          |--- ArrayList: 采用数组结构存储元素。 查询操作多时选择
          |--- LinkedList: 采用链表结构存储元素。 增删操作多时选择
          |--- Vector:
      |--- java.util.Set: 无序的，不允许重复。
          |--- HashSet : 是 Set 接口的典型实现类。
              判断元素是否存在的依据是：先比较 hashCode 值，若 hashCode 存在，再通过 equals() 比较内容
                                       若 hashCode 值不存在，则直接存储
  
              注意：重写 hashCode 和 equals 二者需要保持一致！
              |--- LinkedHashSet: 相较于 HashSet 多了链表维护元素的顺序。遍历效率高于 HashSet ， 增删效率低于 HashSet
          |--- TreeSet : 拥有自己排序方式
              |-- 自然排序（Comparable）：
                  ①需要添加 TreeSet 集合中对象的类实现 Comparable 接口
                  ②实现 compareTo(Object o) 方法
              |-- 定制排序（Comparator）
                  ①创建一个类实现 Comparator 接口
                  ②实现 compare(Object o1, Object o2) 方法
                  ③将该实现类的实例作为参数传递给 TreeSet 的构造器

  2018-11-20

  

   14
• 

  zjh

  比较片面的说，java集合类底层基本上就是基于数组或者链表来实现的，数组的地址连续性决定了其随机存取速度较快，但是涉及到扩容则比较耗时，而链表则不存在扩容的性能消耗，但随机访问需要遍历地址因此相对数组要慢，所以判断一个集合的特点可以先判断是基于数组还是链表。

  2018-05-26

  

   11
• 

  Miaozhe

  今天看了一下PriorityQueue的源码，发现其是使用最小堆结构(二叉堆)，存放在数组中(数组索引对应树的从上到下，从左到右)。采用上面最小，每插入一个数据，就先与根节点比较，如果小于根节，依次换位置；大于根节点，就放在最后一个位置。

  2018-05-28

  

   6
• 

  Miaozhe

  杨老师，问个问题，Collection接口下面已细化了List,Set和Queue子接口，未什么又定义了AbstractCollection这个抽象类？具体是什么考虑？以为我发现3个接口的子类都是集成这个抽象类。

  作者回复: 三个都是Collection，总还是有共同行为的

  2018-05-26

  

   4
• 

  王宁

  面试的重点HashMap,实现原理，扩展什么的，1.7和1.8的区别。还有和hashtable的异同。还有juc下面集合的熟悉程度。
  

  作者回复: 下两篇就是

  2018-05-22

  

   4
• 

  我奋斗去了

  可以使用priority queue ，维护两个队列 一个VIP队列 一个普通用户队列 。当VIP队列有人的情况优先处理

  作者回复: 为什么用两个队列，PriorityQueue不是有优先级了

  2018-05-22

  

   3
• 

  呵呵

  阅读速度太快了

  2018-05-23

  

   2
• 

  码上Java

  对比 Vector、ArrayList、LinkedList有何区别？
  Vector是Java早期提供的线程安全的动态数组，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数据已满时，会创建新的数组，并拷贝原有数组数据。
  ArrayList是应用更加广泛的动态数组实现，它本身不是线程安全的，所以性能要好很多，与Vector近似，ArrayList也是可以根据需要调整容量，不过两者的调整逻辑有所区别，Vector在扩容时会提高1倍，而ArrayList则是增加50%。
  LinkedList顾名思义是Java提供的双向链表，所以它不需要像上面那样调整容量，它也不是线程安全的。
  -Vector和ArrrayList作为动态数组，其内部元素以数组形式顺序存储的，所以非常适合随机访问的场合。除了尾部插入和删除元素，往往性能会相对较差，比如我们在中间位置插入一个元素，需要移动后续所有元素。
  -而ArrayList进行结点插入、删除却要高效很多，但是随机访问性能则要比动态数组慢。
  

  2019-05-03

  

   1
• 

  郑泽洲

  杨老师，请教2个一直困扰我的问题：
  1.ArrayList是继承了AbstractArrayList，其中AbstractArrayList已经实现了List接口，ArrayList自然隐含实现了List接口。可是为什么ArrayList还显式声明实现了List接口？
  2. Arrays.asList返回的是List类型，其内部是Arrays.ArrayList为什么不直接用java.util.ArrayList
  

  2019-04-17

  

   1
• 

  小笨蛋

  招聘时我更倾向于考察面试者自身最擅长的东西，免得招到纯面试高手?这个你一般会怎么面试？纯面试感受是一个什么样的表现？

  作者回复: 例如，介绍项目过程中，随机问某些细节方面，可能就比较陌生，判断下是忘了还是就参与有限

  2018-10-04

  

   1
• 

  且以深情共白头

  之前一直以为Verctor不属于集合，只是数组。学习了。针对VIP客户任务优先处理场景，认为采用SortSet进行，按照默认排序即可，数值越小优先级越高，和线程的优先级级别一致

  作者回复: 和优先队列相比，不那么紧凑，例如treeset用的树比堆要多了节点开销

  2018-07-09

  

   1
• 

  Miaozhe

  杨老师，有个问题，TreeSet为什么不支持正序，只支持倒序(DescendingIteractor)？Tree本身支持正序列.

  2018-05-28

  

   1
• 

  Leo

  使用优先级队列实现堆，可以根据优先级进行操作

  2018-05-22

  

   1
• 

  webwombat

  那个问题，应该是priority queue吧？操作系统的进程调度一般都是基于优先级队列来实现的。

  作者回复: yes，人家可能进一步提出更多场景继续考

  2018-05-22

  

   1