基础篇：Java集合，面试专用（上）

上一篇 / 下一篇  2021-11-03 15:03:35

查看( 226 ) / 评论( 0 ) / 评分( 0 / 0 )
　　没啥好说的，在座的各位都是靓仔
　　· 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 synchronized 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>, RandomAccess, 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.synchronizedList 区别
　　· CopyOnWriteArrayList 的写操作性能较差，而多线程的读操作性能较好
　　· Collections.synchronizedList的写操作性能比CopyOnWriteArrayList在多线程操作的情况下要好很多，而读操作因为是采用了 synchronized关键字的方式，其读操作性能并不如CopyOnWriteArrayList

收藏 举报

TAG: 软件开发 Java

 

评分：0

我来说两句

Open Toolbar