RuiCode

  • 首页
  • 归档

  • 搜索
操作系统 并发 排序 网络 源码分析 二分法 面试 不重复算法 指针移动 java 算法 mysql Linux

【面试经】JAVA基础知识(六)-- 容器总结之List

发表于 2020-02-20 | 分类于 面试经 | 0 | 阅读次数 261
  1. ArrayList
  • 底层结构就是Object[] 数组,该数组特点是可以存储任意类型的对象,向上转型,在使用时需要向下转型为实际的类型
	Object[] o = new Object[2];
        o[0] = new String("ss");
        o[1] = new Integer(1);
        boolean b =(o[0] instanceof String); //true
        boolean b2 =(o[1] instanceof String); //false
	boolean b3 =(o[1] instanceof Integer); //true
        Integer i = (Integer) o[1]; // need cast when using
  • 初始容量是10,如果添加时超过容量时,每次扩容为1.5倍
  • ArrayList有 Itr内部类,实现Iterator接口,每次调用iterator()方法时,返回new Itr()
  • ArrayList实现 RandomAccess 接口,实现随机访问查找,使用index查询的时间复杂度是o1
  • remove() 实际上调用复制数组方法,时间复杂度On
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
  1. LinkedList
  • 数据结构是双向队列,有first和last Node
  • 其中Node是静态内部类,有prev 和 next 两个指针
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
  • 队列的最常用方法:
    -- offer(E e) 调用 add()/addLast() 最终调用 linkLast()
    -- poll() 首先判断Node first 是否为空,空的话返回null,不为空调用removeFirst()
    -- peek() 和poll类型,允许返回null

  • 栈的最常用方法:
    -- push(E e) 调用 addFirst() 最终调用 linkFirst()
    -- pop() 直接调用 removeFirst() 头结点为空,报异常 因此调用前需要确保 LinkedList非空

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
  • get(int index) 调用 node(int index) 时间复杂度为On
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
  1. CopyOnWriteArrayList
  • 位于java.util.concurrent 包下
  • 是线程安全类,主要使用了ReentrantLock, array 前加了 volatile 修饰
    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;
  • 写入之前加锁,并且在写入过程中先使用临时数组保存修改好的数组,然后使用setArray方法修改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); 
            return true;
        } finally {
            lock.unlock();  // 使用完之后务必释放锁
        }
    }
  • 删除时和写入类似,都采用 加锁+新建临时数组
    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
  • get(int index) 无须加锁,如果在get时其他线程正在修改 array,get方法虽然得不到最新的值,但是不会阻塞线程的执行。
  • CopyOnWrite并发容器用于读多写少的并发场景。比如白名单,黑名单,商品类目的访问和更新场景,假如我们有一个搜索网站,用户在这个网站的搜索框中,输入关键字搜索内容,但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中,黑名单每天晚上更新一次。当用户搜索时,会检查当前关键字在不在黑名单当中,如果在,则提示不能搜索
  • 本文作者: RuiCode
  • 本文链接: https://www.ruicode.cn/archives/面试经java基础知识六--容器总结之list
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 操作系统 # 并发 # 排序 # 网络 # 源码分析 # 二分法 # 面试 # 不重复算法 # 指针移动 # java # 算法 # mysql # Linux
二分法总结
【面试经】JAVA基础知识(七)-- 容器总结之Set、Map
  • 文章目录
  • 站点概览
RuiCode

RuiCode

19 日志
5 分类
13 标签
Creative Commons
© 2021 RuiCode
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4

冀公网安备 13050002001906号