Java面试中关于容器类List,Set是必问题目。但在我的面试经历中很难遇到满意的答复。大部分只能了解其大概使用方法,对其内部结构缺乏了解,错误的使用方式会导致性能大幅下降。
首先介绍ArrayList,顾名思义内部数据结构是数组
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity){
}
在增加元素时,若容量不足进行扩充
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
新数组大小为之前数组大小*1.5+1 ,加上1保证oldCapacity为1的情况也能扩充为2
(类似分页时总页数=(总记录数+ (每页记录数-1))/每页记录数算法)
删除元素时通过 System.arraycopy把删除位置后的所有元素前移一个位置实现
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
LinkedList大家都知道是通过链表实现,内部是一个双向链表
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
}
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
}
插入和删除都只要改动前后节点的next和previous实现
总结特点如下:
类型 | 内部结构 | 顺序遍历速度 | 随机遍历速度 | 追加代价 | 插入代价 | 删除代价 | 占用内存 |
ArrayList | 数组 | 高 | 高 | 中 | 高 | 高 | 低 |
LinkedList | 双向链表 | 高 | 低 | 低 | 低 | 低 | 中 |
所以:
- 一般顺序遍历情况下使用ArrayList,但注意构造函数中设置初始大小
- 尽量不对ArrayList进行插入或删除操作(删除尾部除外),若有多次删除/插入操作又有随机遍历的需求,可以再构建一个ArrayList,把复合条件的对象放入新ArrayList,而不要频繁操作原ArrayList
- 经常有删除/插入操作而顺序遍历列表的情况下最适合使用LinkedList
分享到:
相关推荐
开篇词讲怎样才能做好性能调优02讲如何制定性能调优策略04讲慎重使用正则表达式05讲ArrayList还是LinkedList使用不当性能差千倍07讲深入浅出HashMap的设计与优化08讲网络通信优化之IO模型:如何解决高并发下IO瓶颈09...
比方,相同作为List的实现,LinkedList和ArrayList在随机訪问上的性能却差了好几个量级;比方相同是文件读写的实现,使用Stream方式和使用JAVA NIO的方式,其系能可能又会是还有一个数量级. 因此,尽管与设计优化相比,...
ArrayList Vector LinkedList 类Stack HashSet TreeSet LinkedHashSet 类 PriorityQueue HashMap TreeMap 类 LinkedHashMap 类 Hashtable 类IdentityHashMap 类WeakHashMap 类 Collections 类集合实现类特征图 泛形 ...
ArrayList 和 LinkedList 底层 . HashMap 及线程安全的 ConcurrentHashMap,以及各自优劣势 . Java 如何实现线程安全 . Synchronized 和 Lock 哪个更好? . HashMap 中的 get()方法是如何实现的? . HashMap 可以用...
16.使用LinkedList删除元素的步骤 17.HashMap、Hashtable、ConcurrentHashMap底层实现原理及区别 18.HashMap底层数据结构 19.说说HashMap如何处理碰撞的,或者说说它的扩容? 20.jdk7/8中对HashMap做了哪些改变? 21...
3.3.3 ArrayList和LinkedList的性能分析和适用场景 3.4 Iterator迭代器 迭代时删除指定元素 3.5 小结 第4课 Java的内存回收 4.1 Java引用的种类 4.1.1 对象在内存中状态 4.1.2 强引用 4.1.3 软引用 4.1.4 ...
│ Java面试题10.ArrayList LinkedList.mp4 │ Java面试题11.HashMap和HashTable的区别.mp4 │ Java面试题12.实现一个拷贝文件的类使用字节流还是字符串.mp4 │ Java面试题13.线程的实现方式 怎么启动线程怎么区分...
25.ArrayList 和 LinkedList 的区别是什么? 26.如何实现数组和 List 之间的转换? 27.ArrayList 和 Vector 的区别是什么? 28.Array 和 ArrayList 有何区别? 29.在 Queue 中 poll()和 remove()有什么区别? 30....
【集合】LinkedList的实现原理 63 【集合】HashMap的结构,get(),put()是如何实现的? 64 put()方法-向HashMap存储键值对,Value> 65 get()方法-根据Key从HashMap中取Value 66 HashMap的特点总结: 66 【集合】...