欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

你真的了解java集合么?

程序员文章站 2022-04-09 23:12:21
...

在平时我们的工作中常用到的集合是ArrayList这个类,用来存储元素。那除了ArrayList还有哪些集合类可以使用呢,ArrayList它的底层又是如何实现的?我们常说到的ArrayList查询快、LinkedList增删快到底怎么回事呢?

集合的体系结构

我这里用一张图来表示常用的集合类体系

你真的了解java集合么?

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,每周都有优质技术文章推送。

微信扫一扫下方二维码即可关注:

你真的了解java集合么?

相关标签: java arraylist