- 您的位置：首页>简历与面试>基础篇：Java集合，面试专用（上）
基础篇：Java集合，面试专用（上）
时间: 2021-11-04 09:43 作者: liqianqian1116 点击次数:
没啥好说的，在座的各位都是靓仔
· List 数组
· Vector 向量
· Stack 栈
· Map 映射字典
· Set 集合
· Queue 队列
· Deque 双向队列
一般队列的通用方法：
1.List 数组
· 元素按进入先后有序保存，可重复
· List有两种底层实现，一种是数组，一种是链表，而链表的实现继承了 Collection。数组和集合的区别：
- 数组大小是固定，集合是可变的
- 数组的元素可以基本类型也可以是引用类型，而集合只能是引用类型
ArrayList
· ArrayList底层是使用一个可动态扩容的数组，与普通数组的区别就是它是没有固定大小的限制，可以添加或删除元素
· 它的特点就是读速度、更新快，增删慢;内存相邻，根据Index读取的时间复杂度是O(1);可以存储重复元素，但线程不安全
· ArrayList 的扩容机制
//ArrayList openJDK 13
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length) //放不下了
elementData = grow(); // 扩容
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, // minCapacity - oldCapacity == 1
oldCapacity >> 1 ); // oldCapacity == 1/2 oldCapacity
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
如果当前元素放不下，则扩容至 1.5 倍，且大于等于 1
// ArraysSupport.newLength
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
//prefGrowth 是 oldLength 的 1/2，minGrowth 是 1。因此 newLength = 1.5 oldLength
int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) { // MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8
return newLength;
}
return hugeLength(oldLength, minGrowth);
}
LinkedList
· LinkedList的节点并不是存储真实的数据，而是存下数据的引用对象，而且节点之间使用引用相关联
· LinkedList实现了Queue、Deque接口，可作为队列使用;查找慢，增删快，可以存储重复元素，但线程不安全
· 使用 LinkedList 实现LRU
public static class LRU<T> {
//默认的缓存大小
private int CAPACITY = 0;
//引用一个双向链接表
private LinkedList<T> list;
//构造函数
public LRU(int capacity) {
this.CAPACITY = capacity;
list = new LinkedList();
}
//添加一个元素
public synＣhronized void put(T object) {
if (list != null && list.contains(object)) {
list.remove(object);
}
removeLeastVisitElement();
list.addFirst(object);
}
//移除最近访问次数最少的元素
private void removeLeastVisitElement() {
int size = list.size();
//注意，这儿必须得是CAPACITY - 1否则所获的size比原来大1
if (size > (CAPACITY - 1)) {
Object object = list.removeLast();
}
}
//获取第N个索引下面的元素
public T get(int index) {
return list.get(index);
}
}
LinkedList 的 API
public E getFirst() //获取第一个元素
public E getLast() //获取最后一个元素
public E removeFirst() // 移除第一个元素，并返回
public E removeLast() // 移除最后一个元素，并返回
public void addFirst(E e) //加入头部
public void addLast(E e) //加入尾部
public void add(E e) //加入尾部
public boolean contains(Object o) //是否包含 元素 o
public E peek() //获取头部第一个元素
public E element() // 获取头部第一个元素,不存在则报错
public E poll() //获取头部第一个元素，并移除
public boolean offer(E e) // 调用 add(E e)
public boolean offerFirst(E e) // 调用 addFirst
public boolean offerLast(E e) // 调用 addLast
public void push(E e) //在头部压入一个元素
public E pop() //弹出第一个元素，并移除。不存在则报错
ArrayList 和 LinkedList 使用场景
· 频繁访问列表中的某一个元素，或者需要在列表末尾进行添加和删除元素操作，用ArrayList
· 频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作，用LinkedList
Iterator 和 fast-fail、fail-safe机制
Java Iterator(迭代器)不是一个集合，它是一种用于访问集合的方法，可用于迭代 List 和 Set 等集合，主要有hashNext()，next()，remove()三种方法
fail-fast 是Java集合(Collection)的一种错误机制。当多个线程对同一个集合进行修改结构操作，使用集合的迭代器iterator，会首先检测是否有对集合的并发修改，进而产生ConcurrentModificationException 异常提示
fail-safe：保证在对任何集合结构的修改操作都基于 《复制-修改》 进行的，即先copy一个新的集合对象，然后对新的集合对象进行修改，最后将新的集合对象替换掉老的集合对象(老的集合对象的地址指向新的集合对象)。java.util.concurrent包下采用的是fail-safe机制。
缺点1-对集合的复制copy会产生大量的对象，造成内存空间的浪费。
缺点2-无法保证集合迭代过程中获取的集合数据是最新的内容
CopyOnWriteArrayList
CopyOnWriteArrayList 的线程安全：CopyOnWriteArrayList 在写的时候会加锁，为了保证写安全，会在写操作时复制一个新数组来操作，然后覆盖旧的数组;不会影响读的性能
public class CopyOnWriteArrayList<E>
implements List<E>, Ran domAccess, Cloneable, java.io.Serializable {
//可重入锁
final transient ReentrantLock lock = new ReentrantLock();
//数组，仅通过get和set方法操作
private transient volatile Object[] array;
....
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();//拿到当前数组
int len = elements.length;//获得长度
//拷贝当前数组
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements); //调用set方法将新数组设置为当前数组
return true;
} finally {
lock.unlock();//解锁
}
}
CopyOnWriteArrayList 的缺点
· CopyOnWrite 在进行写操作的时候，内存里会同时驻扎两个对象的内存，导致内存的浪费
· CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器，没有阻塞等待的概念
CopyOnWriteArrayList 和 Collections.synＣhronizedList 区别
· CopyOnWriteArrayList 的写操作性能较差，而多线程的读操作性能较好
· Collections.synＣhronizedList的写操作性能比CopyOnWriteArrayList在多线程操作的情况下要好很多，而读操作因为是采用了 synＣhronized关键字的方式，其读操作性能并不如CopyOnWriteArrayList
打印本页 | 加入收藏
上一篇：【51讲堂】测试开发必备框架testng 下一篇：浅谈游戏测试工程师的职业发展之路
文章检索
热门关键词: 登录