你真的了解java集合么?
程序员文章站
2022-04-09 23:12:21
...
在平时我们的工作中常用到的集合是ArrayList这个类,用来存储元素。那除了ArrayList还有哪些集合类可以使用呢,ArrayList它的底层又是如何实现的?我们常说到的ArrayList查询快、LinkedList增删快到底怎么回事呢?
集合的体系结构
我这里用一张图来表示常用的集合类体系
Vector和ArrayList、LinkedList联系和区别,分别的使⽤用场景?
联系和区别
- ArrayList: 底层是数组实现,所以查询快、增删慢,线程不安全的。
- LinkedList:底层是链表,所以增删快、查询慢,线程不安全的。
- Vector:底层是数组实现,是线程安全的,使用了synchronized
使用场景
- ArrayList:查询居多
- LinkedList:增删居多
- Vector:很少使用
如果需要保证线程安全,ArrayList应该怎么做,有⼏种⽅式?
- Collections.synchronizedList(List list); 使用了synchronized 关键字
- new CopeOnWriteArrayList(List list); 该类在concurrent包下 使用了 ReentrantLock 锁
Collections.synchronizedList(List list);和new CopeOnWriteArrayList(List list);这俩种方案实现上有什么区别,使用场景是怎样的?
- Collections.synchronizedList(List list); 线程中的每个方法加了synchronized 同步锁,增删性能好
- new CopeOnWriteArrayList(List list); 执行修改操作的时候(add、update、remove)会拷贝一份新的数组进行操作,等操作完毕之后新的数组会指向原来的数组,其中使用了ReentrantLock 保证了只有一个线程操作。 因为涉及到数组的拷贝,所以增删慢读的性能好
CopyOnWriteArrayList的设计思想是怎样的,有什什么缺点?
- 读写分离+最终一致
- 内存占用问题,因为复制机制,会存在俩个对象的的内存,如果对象比较大会导致GC情况
public E set(int index, E element) {
final ReentrantLock lock = this.lock; //使用了ReentrantLock锁
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(elements, index);
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len); //数组的拷贝
newElements[index] = element;
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
ArrayList的扩容机制
- 1.7之后初始化集合的时候,未指定的情况下0,在指定的情况下按照指定的
- 在未指定集合容量的情况下,初次扩容为10
- 当容量小于集合的个数需要再次扩容的时候按照 扩容大小=原始大小+原始大小/2
手写简单版ArrayList【需要包含 构造函数(有参和⽆无参)、add(obj)、 扩容机制】
public class MyArrayList implements Serializable {
//使用这个字段,来判断当前集合类是否被并发修改,即迭代器并发修改的fail-fast机制
private transient int modCount = 0;
//第一次扩容的容量
private static final int DEFAULT_CAPACITY = 10;
//用于初始化空的list
private static final Object[] EMPTY_ELEMENT_DATA = {};
//实际存储的元素
transient Object[] elementData;
//实际list集合大小,从0开始
private int size;
public MyArrayList(){
this.elementData = EMPTY_ELEMENT_DATA;
}
public MyArrayList(int initialCapcity){
if(initialCapcity>0){
this.elementData = new Object[initialCapcity];
}else if(initialCapcity == 0){
this.elementData = EMPTY_ELEMENT_DATA;
}else {
throw new IllegalArgumentException("参数异常");
}
}
public boolean add(Object e){
//判断容量
ensureCapacityInternal(size+1);
//使用下标赋值,尾部插入
elementData[size++] = e;
return true;
}
//计算容量+确保容量
private void ensureCapacityInternal(int minCapacity){
//用于并发判断
modCount++;
//如果是初次扩容,则使用默认的容量
if(elementData == EMPTY_ELEMENT_DATA){
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//是否需要扩容,需要的最少容量大于现在数组的长度则要扩容
if(minCapacity - elementData.length > 0){
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity>>1);
//如果新容量 < 最小容量, 则讲最新的容量赋值给新的容量
if(newCapacity - minCapacity < 0){
newCapacity = minCapacity;
}
//创建新数组
Object[] objects = new Object[newCapacity];
//将旧的数组复制到新的数组里面
System.arraycopy(elementData,0, objects,0,elementData.length);
//修改引用
elementData = objects;
}
}
/**
* 通过下标获取对象
* @param index
* @return
*/
public Object get(int index){
rangeCheck(index);
return elementData[index];
}
private void rangeCheck(int index){
if(index > size || size < 0){
throw new IndexOutOfBoundsException("数组越界");
}
}
/**
* 判断对象所在的位置
* @param o
* @return
*/
public int indexOf(Object o){
if(o == null){
for(int i=0; i < size; i++){
if(elementData[i] == null){
return i;
}
}
}else {
for(int i=0; i<size; i++){
if(o.equals(elementData[i])){
return i;
}
}
}
return -1;
}
public Object set(int index, Object obj){
rangeCheck(index);
Object oldValue = elementData[index];
elementData[index] = obj;
return oldValue;
}
/**
* 根据索引删除元素
* @param index
* @return
*/
public Object remove(int index){
rangeCheck(index);
//用于并发判断
modCount++;
Object oldValue = elementData[index];
//计算要删除的位置后面有几个元素
int numMoved = size - index -1;
if(numMoved>0){
System.arraycopy(elementData,index+1,elementData,index,numMoved);
}
//将多出的位置为空,没有引用对象,垃圾收集器可以回收,如果不为空,将会保存一个引用,可能会造成内存泄露
elementData[--size] = null;
return oldValue;
}
//获取数组实际大小
public int size(){
return this.size;
}
}
Set集合
核心就是不保存重复的元素,存储一组唯一的对象set的每一种实现都是对应Map里面的一种封装,HashSet对应的就是HashMap,treeSet对应的就是treeMap
public HashSet() {
map = new HashMap<>();
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
关注我的技术公众号alistarfeng,每周都有优质技术文章推送。
微信扫一扫下方二维码即可关注:
上一篇: MySQL锁,你真的理解么?
下一篇: 6. 选择器的使用