美文网首页JavaJava 杂谈
JAVA集合和映射表源码详细解读

JAVA集合和映射表源码详细解读

作者: Aiibai | 来源:发表于2019-05-06 16:05 被阅读68次

    下面这些类图是通过IDEA生成的,将一些无用的线删掉了(比如:LinkedList继承了AbstractList,并且实现List,其实不用声明实现List接口,因为这里AbstractList就是List的实现。这种做法不明白其意思,网上搜索的答案是因为手误,但是也不影响程序,所以就一直保留了。。)

    绿色实线:接口继承
    蓝色实现:类继承
    绿色虚线:接口实现

    下面是集合的类图,这里只画出了比较常用的类,并不是java中的全部集合类,大致可以分为三种类型:ListSetQueue,后面会对每种类型的集合进行详细解读,这里只简单提一下这三种类型的区别。

    List:作为有序 可重复 集合的容器,实现方式有数组(ArrayList)和链表(LinkedList)等。
    Set:不能包含重复元素,并且元素是无序的,当然这里的无序指的是天然无序,并不是没有办法让它有顺序,如果不考虑元素的顺序,只是判断元素是否存在于集合中,使用这种数据结构更高效。
    Queue:队列是一种FIFO的数据结构,也有双端队列,常用的场景是阻塞队列实现生产者和消费者。

    Collection.png
    List
    List.png
    • ArrayList
      底层是用Object类型的数组(考虑一下为什么不是泛型数组,为什么没有泛型数组)存储,适用于索引查找元素,但是对于添加和删除元素效率较低,这是底层数组结构决定的,删除和添加元素需要移动受影响的元素。既然ArrayList是动态数组,那么它是如何实现扩容的,请看下面的源代码
         public void add(int index, E element) {
            rangeCheckForAdd(index);
            //检查容量
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
        private void ensureCapacityInternal(int minCapacity) {
            //DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组
           //初始化数组大小最小是DEFAULT_CAPACITY
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            //修改计数器,用于迭代器的快速失败检查
            modCount++;
    
            // overflow-conscious code
            //如果容量不够,进行扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
           //新容量是原来容量加1/2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
           //如果新容量比需要的最小容量小,就是用需要的容量作为新容量
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            //如果新容量大于最大容量(MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8)
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
     //这个方法除了检查minCapacity是不是负数之外,后面返回值不知道意义何在,
    //如果真是newCapacity - MAX_ARRAY_SIZE>0,但是MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8,
    //也就是说数组最大是Integer.MAX_VALUE,为什么不直接将MAX_ARRAY_SIZE 设置为Integer.MAX_VALUE
      private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }
     
        public void add(int index, E element) {
            rangeCheckForAdd(index);
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //将要添加元素位置以后的所有元素向后移动一位
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
         }
        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. newCapacity = oldCapacity + oldCapacity / 2 ,具体还要根据minCapacity以及数组当前状态确定。
    2. ArrayList 的最大容量是Integer.MAX_VALUE
    3. 插入和删除时需要移动元素
    • LinkedList
      链表存储,并且实现了双端队列接口,适用于插入和删除,但是不适用于通过索引获取元素,即便是支持的,效率很低。我们看一下插入和删除操作的源码
      public void add(int index, E element) {
            //插入位置检查:  0<=index<=size
            checkPositionIndex(index);
            //插入链表末尾
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
      }
    
      void linkLast(E e) {
            //插入之前末尾节点
            final Node<E> l = last;
           //设置插入节点的前驱节点是之前的末尾节点,后驱节点为空
            final Node<E> newNode = new Node<>(l, e, null);
           //插入节点作为新的末尾节点
            last = newNode;
           //如果之前的末尾节点为空,也就是链表为空,新节点应该作为首节点,
          //否则设置新节点是之前末尾节点的后驱节点
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
      }
    
      void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
     public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
    
        E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
    
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }
      public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
       //根据元素的索引查找元素
        Node<E> node(int index) {
            // assert isElementIndex(index);
            //如果索引大于1/2 size,从首节点遍历,否则从末节点遍历
            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.获取元素是通过遍历元素,所以效率不高,O(n)
    2.向指定的位置添加和删除元素,也会涉及到通过索引定位元素,然后修改节点关系,也就是LinkedList的插入和删除效率不一定比ArrayList高,当数据量比较大,索引靠近中间位置(遍历查找元素耗时最多)的时候,ArrayList要比LinkedList的效率高。(可以用20w个元素,index设置为10w测试)。但是如果只是在末尾插入元素呢,这个要根据数据量来说,具体可以看一下这篇文章:https://blog.csdn.net/qq_34144916/article/details/81154528

    • List总结
    1. 在插入或者删除场景推荐使用 LinkedList
    2. 在索引查找场景推荐使用 ArrayList
      上面的两点不是绝对的,要具体根据元素数量来说,在元素数量比较小时适用。

    Vector和ArrayList的相同点和不同点

    • 相同点:
    1. 继承自 AbstractList
    2. 底层使用Object数组实现
    3. 实现了RandomAccess,支持随机访问
    4. 能容纳的最大元素数量相同
    • 不同点
    1. Vector的所有公开方法都是 synchronized
    2. 扩容大小不同
    //Vector
    //capacityIncrement 可以通过构造函数传入,默认是0
    newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                             capacityIncrement : oldCapacity)
    //ArrayList
    newCapacity = oldCapacity + (oldCapacity >> 1);
    

    双端队列以及使用场景
    在上面的类图中我们看到 ArrayDequeLinkedList 都实现 Deque 接口,ArrayDeque 是循环队列,可以使用在队列和栈场景,双端队列主要适用于工作秘场景,比如爬虫任务。在队列模块会进行详细解读。可以参考这篇文章:
    https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/4-Stack%20and%20Queue.md

    到此List相关类详细完毕,下一节我们学习Set。

    Set
    Set.png
    这里我们着重介绍 HashSetLinkedHashSetTreeSet
    • HashSet
      HashSet底层是使用 HashMap 存储,HashMap我们会在后面的章节介绍到,那么将HashSet 中的元素如何存储到 HashMap 中的, HashMap中的键是什么?值是什么?请看下面的代码
        private transient HashMap<E,Object> map;
        private static final Object PRESENT = new Object();
        public boolean add(E e) {
            //键是元素,值是一个固定的Object,而且是静态的,
            //也就是所有 `HashSet` 在 `HashMap`中的值是一样的
            return map.put(e, PRESENT)==null;
        }
        public boolean remove(Object o) {
            return map.remove(o)==PRESENT;
        }
        public Iterator<E> iterator() {
            return map.keySet().iterator();
        }
    

    这里需要注意一点,既然 HashSet 中的元素是作为 HashMap 的键,那么为了保证 HashSet 中元素不能重复,就要重写元素的 equals 和 hashCode 方法。至于这两个方法的关系我们在 Map 章节介绍
    实现很简单吧,下面我们再说一下 HashSet 的子类 LinkedHashSet

    • LinkedHashSet
      LinkedHashSet 使用 LinkedHashMap 实现的,LinkedHashMap 是一个比较有意思的MapMap 章节介绍,这里知道 LinkedHashSet 保证元素的遍历顺序和插入顺序是相同的就行,其他和 HashSet 没有什么区别,这也是为什么前面我们说 Set 只是天然无序的,并不是不能做到有序。

    • TreeSet
      TreeSet 是使用 TreeMap 实现
      所有要想深入了解 Set ,必须学习对应的 Map

    • Set总结

    1. Set 使用 Map 实现
    2. HashSet 是无序的
    3. LinkedHashSet 是有序的,顺序是元素插入的顺序
    4. TreeSet 可以对元素排序
    5. 它们都是线程不安全的

    Set学习至此完毕,下一节学习Queue。

    Queue
    Queue.png
    • 队列分类
    阻塞单端队列 非阻塞单端队列 阻塞双端队列 非阻塞双端队列
    BlockingQueue Queue BlockingDeque Deque
    ArrayBlockingQueue
    LinkedBlockingQueue
    SynchronousQueue
    PriorityBlockingQueue
    PriorityQueue LinkedBlockingDeque ArrayDeque/LinkedList
    • 使用场景
      生产者-消费者设计中,所有消费者有一个共享的工作队列,而在工作密取设计中,每个消费者都有各自的双端队列。如果一个消费者完成了自己双端队列中的全部工作,那么它可以从其它消费者双端队列末尾秘密地获取工作。
      密取工作模式比传统的生产者-消费者模式具有更高的可伸缩性,这是因为工作者线程不会在单个共享的任务队列上发生竞争。在大多数时候,它们都只是访问自己的双端队列,从而极大地减少了竞争。当工作者线程需要访问另一个队列时,它会从队列的尾部而不是头部获取工作,因此进一步降低了队列上的竞争程度。
      工作密取非常适用于即是消费者也是生产真问题--当执行某个工作时可能导致出现更多的工作。例如,在网页爬虫程序中处理一个页面时,通常会发现有更多的页面需要处理。类似的还有许多搜索图的算法,例如在垃圾回收阶段对堆进行标记,都可以通过工作密取机制来实现高效并行。当一个工作线程找到新的任务单元时,它会将其放到自己队列的末尾(或者在工作共享模式中,放入其它工作者线程的队列中)。当双端队列为空时,它会在另一个线程的队列末尾查找新的任务,从而确保每个线程都保持忙碌状态。

    首先我们简单陈述一下,各种类型队列的定义:


    image.png

    关注一下对于相同操作,不同方法的操作结果

    Throws exception Special value Blocks Times out
    Insert add(e) offer(e) put(e) offer(e, time, unit)
    Remove remove() poll() take() poll(time, unit)
    Examine element() peek() not applicable not applicable
    • ArrayDeque
      无界循环双端队列
      在阅读代码之前,首先应该明白一个公式:
      a % b == a & (b - 1),前提是b是2^n,并且a>0,具体证明可以参考这里:
      https://www.codercto.com/a/30894.html
      // 第一个元素的索引  
      private transient int head;  
      // 下个要添加元素的位置,为末尾元素的索引 + 1  
      private transient int tail;  
    
      public void addFirst(E e) {
            if (e == null)
                throw new NullPointerException();
           /*当head-1 = -1 时,取余得到的是(elements.length - 1),从而实现了循环,
            这也说明了tail为什么不是最后一个元素的位置,而是最后一个需要插入元素的位置,如果是最后一个  
            元素的位置的话,当:head=0,tail=elements.length-1 时,就没有位置从首部插入新的元素*/
            elements[head = (head - 1) & (elements.length - 1)] = e;
          /*如果head==tail 时进行扩容,请注意这里的tail是下一个可插入元素的位置,也就是这时候数组中其实
            还有一个空位的*/
            if (head == tail)
                doubleCapacity();
       }
       public void addLast(E e) {
            if (e == null)
                throw new NullPointerException();
            //这里直接在尾部插入了元素,就是因为tail是下一个可插入元素的位置
            elements[tail] = e;
            /*更新tail,如果需要扩容
            取模,保证数据不越界*/
            if ( (tail = (tail + 1) & (elements.length - 1)) == head)
                doubleCapacity();
        }
       
        public E pollFirst() {
            int h = head;
            @SuppressWarnings("unchecked")
            E result = (E) elements[h];
            // Element is null if deque empty
            if (result == null)
                return null;
            elements[h] = null;     // Must null out slot
            head = (h + 1) & (elements.length - 1);
            return result;
        }
    
        public E pollLast() {
            int t = (tail - 1) & (elements.length - 1);
            @SuppressWarnings("unchecked")
            E result = (E) elements[t];
            if (result == null)
                return null;
            elements[t] = null;
            tail = t;
            return result;
        }
     /**
         * Allocates empty array to hold the given number of elements.
         *获取大于numElements的最小2^n
         * @param numElements  the number of elements to hold
         */
        private void allocateElements(int numElements) {
            int initialCapacity = MIN_INITIAL_CAPACITY;
            // Find the best power of two to hold elements.
            // Tests "<=" because arrays aren't kept full.
    
            //如果numElements本来就是2^n,则结果翻倍,如果想返回原始值,则在计算之前-1
            if (numElements >= initialCapacity) {
                initialCapacity = numElements;
                initialCapacity |= (initialCapacity >>>  1);//使 n 的前2位为1
                initialCapacity |= (initialCapacity >>>  2);//使 n 的前4位为1
                initialCapacity |= (initialCapacity >>>  4);//使 n 的前8位为1
                initialCapacity |= (initialCapacity >>>  8);//使 n 的前16位为1
                initialCapacity |= (initialCapacity >>> 16);//使 n 的前32位为1
                initialCapacity++;
                //如果大于了最大整数,上面的++会导致溢出,结果变为负数
                if (initialCapacity < 0)   // Too many elements, must back off
                    initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
            }
            elements = new Object[initialCapacity];
        }
        private void doubleCapacity() {
            assert head == tail;
            int p = head;
            int n = elements.length;
            int r = n - p; // number of elements to the right of p
            int newCapacity = n << 1;
            if (newCapacity < 0)
                throw new IllegalStateException("Sorry, deque too big");
            Object[] a = new Object[newCapacity];
            System.arraycopy(elements, p, a, 0, r);
            System.arraycopy(elements, 0, a, r, p);
            elements = a;
            head = 0;
            tail = n;
        }
    

    那么可以回答下面的问题了

    1. 如何做到循环队列?
      通过控制数组元素个数为2^n,通过 & 实现循环
    2. 怎么判断需要扩容
      当 head==tail 时,说明数组中只剩tail位置可以插入,这是进行两倍的扩容
    3. 如何做到无界队列
      数组拷贝扩容

    通过上面源码的学习,我们应该收获到

    1. 实现有界循环:a & (b-1)
    2. 计算一个数的最小2的次幂
    • LinkedList
      在List章节已经详细介绍过

    关于上面这两个双端队列性能的比较可以看一下这篇文章:
    https://www.zhihu.com/question/33030727

    • PriorityQueue
      优先级队列,因为需要排序,有两种方式实现排序,要么元素实现Comparable接口,要么在给队列的构造函数提供比较器:Comparator
      在学习之前我们复习一下我们曾经学习的堆
      堆:
    1. 近似完全二叉树结构
    2. 如果用数组实现堆,每个节点的索引满足下面的公式:节点索引是k,那么左右子节点的索引分别是:2i+1和2i+2
    3. 有序堆:大顶堆(升序)、小顶堆(降序),满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆
      下面代码是用小顶堆排序
       public static void sort(int[] array) {
            //构建小顶堆,从最后一个非叶子节点调整,直到堆顶
            for (int i = array.length / 2 - 1; i >= 0; i--) {
                adjustHeap(array, array.length, i);
            }
    
            //排序
            for (int i = array.length - 1; i >= 0; i--) {
                //将顶部元素和最后一个在数组中(这里请注意,是数组中)未排序的元素交换
                swap(array, 0, i);
                //交换以后,调整由交换引起的可能不满足小顶堆性质的节点
                adjustHeap(array, i, 0);
            }
    
        }
    
        private static void adjustHeap(int[] array, int length, int i) {
            int temp = array[i];
            //从i节点的左子节点开始
            for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
                //如果右子节点比左子节点的值还小,就用右子节点与父节点比较
                if (k + 1 < length && array[k] > array[k + 1]) {
                    //右子节点
                    k = k + 1;
                }
    
                //如果子节点的值比父节点小,交换
                if (temp > array[k]) {
                    swap(array, i, k);
                    //交换以后,确保父节点沉下去以后还是满足小顶堆性质
                    i=k;
                } else {
                    break;
                }
            }
        }
    
        private static void swap(int[] array, int a, int b) {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
        }
    

    好了,如果明白了小顶堆排序,那么学习 PriorityQueue 源代码就简单多了,它的实现就是:数组+小顶堆

        public boolean add(E e) {
            return offer(e);
        }
    
        public boolean offer(E e) {
            if (e == null)
                throw new NullPointerException();
            modCount++;
            int i = size;
            //自动扩容,grow方法和ArrayList中的grow类似,这里不做过多解释
            if (i >= queue.length)
                grow(i + 1);
            //更新元素总数
            size = i + 1;
            //如果是第一个插入到队列中的元素,直接放到数组的0位
            if (i == 0)
                queue[0] = e;
            else
               //将i作为子节点,调整它以及它的祖先节点
                siftUp(i, e);
            return true;
        }
        public boolean remove(Object o) {
            int i = indexOf(o);
            if (i == -1)
                return false;
            else {
                removeAt(i);
                return true;
            }
        }
        private E removeAt(int i) {
            // assert i >= 0 && i < size;
            modCount++;
            int s = --size;
            //如果要移除的是最后一个元素,直接移除,不用调整堆
            if (s == i) // removed last element
                queue[i] = null;
            else {
               //堆中最后一个元素,也是最大的元素
                E moved = (E) queue[s];
                queue[s] = null;
                //将最大的元素移动到要移除的元素的位置,并向下调整堆
                //这里写的不太好,既然已经是小顶堆了,最有可能出现在要删除位置的元素应该是它的子节点
                //这里的moved应该用要删除元素的子节点感觉更合适一点,也有另外一个原因是,不管移动那个
                //节点,要删除的元素的所有子节点都要移动一下
                siftDown(i, moved);
                //如果没有向下调整,也就是说它比它的子节点都小,那就要判断一下是否有向上调整的必要
               //如果queue[i] != moved 说明向下调整了,也就是说有子节点还比它小,所以没有必要再向上调整
               //了,因为本来就是有序堆。
                if (queue[i] == moved) {
                    siftUp(i, moved);
                    if (queue[i] != moved)
                        return moved;
                }
            }
            return null;
        }
        //向下调整堆,也就是将k作为父节点
        private void siftDown(int k, E x) {
            //下面的两个方法的算法是一样的,只不过比较方式不一样
            if (comparator != null)
                siftDownUsingComparator(k, x);
            else
                siftDownComparable(k, x);
        }
        
        private void siftDownComparable(int k, E x) {
            Comparable<? super E> key = (Comparable<? super E>)x;
            //还记得父节点的子节点的索引关系吗?2K+1/2K+2,也就是最大的非叶子节点的索引应该是
           //(size-2)/2=size/2-1,所以这里的half可以理解为第一个叶子节点的索引
            int half = size >>> 1;        // loop while a non-leaf
            //如果是非叶子节点
            while (k < half) {
                //左节点:child=2k+1
                int child = (k << 1) + 1; // assume left child is least
                Object c = queue[child];
                //右节点
                int right = child + 1;
                //如果右节点比左节点小,就用右节点的父节点比较
                if (right < size &&
                    ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                    c = queue[child = right];
                if (key.compareTo((E) c) <= 0)
                    break;
                queue[k] = c;
                //继续调整交换以后的子节点
                k = child;
            }
            queue[k] = key;
        }
    
        //类似于:siftDownComparable
        private void siftDownUsingComparator(int k, E x) {
            int half = size >>> 1;
            while (k < half) {
                int child = (k << 1) + 1;
                Object c = queue[child];
                int right = child + 1;
                if (right < size &&
                    comparator.compare((E) c, (E) queue[right]) > 0)
                    c = queue[child = right];
                if (comparator.compare(x, (E) c) <= 0)
                    break;
                queue[k] = c;
                k = child;
            }
            queue[k] = x;
        }
        //向上调整,k作为子节点
        private void siftUp(int k, E x) {
            if (comparator != null)
                siftUpUsingComparator(k, x);
            else
                siftUpComparable(k, x);
        }
      
        private void siftUpComparable(int k, E x) {
            Comparable<? super E> key = (Comparable<? super E>) x;
            while (k > 0) {
                int parent = (k - 1) >>> 1;
                Object e = queue[parent];
                if (key.compareTo((E) e) >= 0)
                    break;
                queue[k] = e;
                k = parent;
            }
            queue[k] = key;
        }
    
        private void siftUpUsingComparator(int k, E x) {
            //直到对顶元素
            while (k > 0) {
                //parent = (k-1)/2
                int parent = (k - 1) >>> 1;
                Object e = queue[parent];
                //如果比它的父节点大,就结束
                if (comparator.compare(x, (E) e) >= 0)
                    break;
                queue[k] = e;
                k = parent;
            }
            queue[k] = x;
        }
        //初始化堆,从第一个非叶子节点开始(length/2-1)
        private void heapify() {
            for (int i = (size >>> 1) - 1; i >= 0; i--)
                siftDown(i, (E) queue[i]);
        }
    

    学习完源代码是不是觉得没有想象中的那么难?呵呵
    使用场景:
    那么这个队列的使用场景是什么,既然它是优先级队列,那直接想到的就是处理优先级高的数据,比如一个电商网站搞特卖或抢购,用户登录下单提交后,考虑这个时间段用户访问下单提交量很大,通常表单提交到服务器后端后,后端程序一般不直接进行扣库存处理,将请求放到队列,异步消费处理,用普通队列是FIFO的,这里有个需求是,用户会员级别高的,可以优先抢购到商品,可能这个时间段的级别较高的会员用户下单时间在普通用户之后,这个时候使用优先队列代替普通队列,基本能满足我们的需求。

    后面我们学习一下阻塞队列,一般使用阻塞队列使用的比较多,因为大多数涉及到队列的场景都有高并发。
    突然发现除了LinkedList其他队列都不允许元素为空,我想这可能是因为像poll这样的方法如果没有获取到元素会返回null,但是如果允许元素有null,那么就有歧义了。

    1. 阻塞队列是通过 ReentrantLock 来保证线程安全的,有两个 Condition ,分别是: notEmptynotFull
    2. 阻塞队列新增了几个中重要的方法:阻塞方法 take/put 和超时等待的 off /poll
    • ArrayBlockingQueue
      有界队列
      如果读懂之前介绍的队列源代码,这里的源代码就很简单了
       int count;
       final Object[] items;
        //阻塞获取元素索引
        int takeIndex;
        //阻塞添加元素索引
        int putIndex;
        final ReentrantLock lock;
        //有数据条件
        private final Condition notEmpty;
        //有空间条件
        private final Condition notFull;
        //入队列
        private void enqueue(E x) {
            // assert lock.getHoldCount() == 1;
            // assert items[putIndex] == null;
            final Object[] items = this.items;
            items[putIndex] = x;
            //从头开始添加,可以想象成putIndex和takeIndex刚开始都为0,然后takeIndex跟在putIndex后面
            //在数据中循环移动
            if (++putIndex == items.length)
                putIndex = 0;
            count++;
            notEmpty.signal();
        }
        //出队列
        private E dequeue() {
            // assert lock.getHoldCount() == 1;
            // assert items[takeIndex] != null;
            final Object[] items = this.items;
            E x = (E) items[takeIndex];
            items[takeIndex] = null;
            if (++takeIndex == items.length)
                takeIndex = 0;
            count--;
            if (itrs != null)
                itrs.elementDequeued();
            notFull.signal();
            return x;
        }
    
    • LinkedBlockingQueue
      可以是有界,也可以是无界
      类似于ArrayBlockingQueue,不同的是底层使用链表,并且lock的粒度不同,新增了 takeLockputLock,计数使用 AtomicInteger
        private final AtomicInteger count = new AtomicInteger();
        transient Node<E> head;
        private transient Node<E> last;
        private final ReentrantLock takeLock = new ReentrantLock();
        private final Condition notEmpty = takeLock.newCondition();
        private final ReentrantLock putLock = new ReentrantLock();
        private final Condition notFull = putLock.newCondition();
        private void enqueue(Node<E> node) {
            // assert putLock.isHeldByCurrentThread();
            // assert last.next == null;
            last = last.next = node;
        }
      
        private E dequeue() {
            //这里要明白的是head节点是个空节点,移除的是空节点的next
            Node<E> h = head;
            Node<E> first = h.next;
            h.next = h; // help GC
            head = first;
            E x = first.item;
            first.item = null;
            return x;
        }
         public void put(E e) throws InterruptedException {
            if (e == null) throw new NullPointerException();
            // Note: convention in all put/take/etc is to preset local var
            // holding count negative to indicate failure unless set.
            int c = -1;
            Node<E> node = new Node<E>(e);
            final ReentrantLock putLock = this.putLock;
            final AtomicInteger count = this.count;
            putLock.lockInterruptibly();
            try {
                while (count.get() == capacity) {
                    notFull.await();
                }
                enqueue(node);
                c = count.getAndIncrement();
                if (c + 1 < capacity)
                    notFull.signal();
            } finally {
                putLock.unlock();
            }
      
            if (c == 0)
                signalNotEmpty();
        }
         public E take() throws InterruptedException {
            E x;
            int c = -1;
            final AtomicInteger count = this.count;
            final ReentrantLock takeLock = this.takeLock;
            takeLock.lockInterruptibly();
            try {
                while (count.get() == 0) {
                    notEmpty.await();
                }
                x = dequeue();
                c = count.getAndDecrement();
                if (c > 1)
                    notEmpty.signal();
            } finally {
                takeLock.unlock();
            }
            //c是上一次元素数量,如果上一次容量满了,现在移除了一个元素,那么应该通知当前
            //容量非满,刚开始看着说有可能发生多线程挂死,后面才看到signalNotFull方法中又用了
            //putLock,所以不用担心
            if (c == capacity)
                signalNotFull();
            return x;
        }
       private void signalNotFull() {
            final ReentrantLock putLock = this.putLock;
            putLock.lock();
            try {
                notFull.signal();
            } finally {
                putLock.unlock();
            }
        }
       private void signalNotEmpty() {
            final ReentrantLock takeLock = this.takeLock;
            takeLock.lock();
            try {
                notEmpty.signal();
            } finally {
                takeLock.unlock();
            }
        }
    

    通过上面的代码可以看到,LinkedBlockingQueue 使用了两个锁,在容量满了或者为空时,用对方的锁去signal。
    所以LinkedBlockingQueue在多线程上实现生产者和消费者应该要比ArrayBlockingQueue效率高。

    • LinkedBlockingDeque
      LinkedBlockingDeque 实现上和 ArrayBlockingQueue 类似,只不过底层使用的是链表,并且是双端队列。详细代码就不用贴了。

    通过上面的队列学习,我们应该知道:

    1. 循环双端队列 ArrayDeque 是如何实现的?
    2. 阻塞队列是如何实现的以及 ArrayBlockingQueueLinkedBlockingQueue 有什么区别?
    3. 优先级队列的数据结构

    至此,Collection的实现类学习完毕,如果这时候你对Collection类图了然于胸,并且每个实现类的使用场景以及优缺点都整明白了,那么恭喜你,对于集合部分的大部分知识你能应对了。
    下面我们会学习常用的映射表, 它的实现中有很多巧妙的算法,很有意思。

    参考文档:
    https://blog.csdn.net/u013309870/article/details/71478120
    https://blog.csdn.net/l540675759/article/details/62893335

    Map
    • equals 和 hashCode
    • put 的操作过程
    • 如何解决Hash冲突
    • HashTable 和 ConcurrentHashMap 在实现高并发时有什么区别
    Map.png
    视图
    迭代器
    • fail-fast 和 fail-safe
    • Iterator和ListIterator的区别
    • Iterator 和 Enumeration的区别
    并发集合
    建议
    • LinkedList和ArrayList 的使用场景和区别?

    • Iterator 和 ListIterator 的区别?

    • 访问元素的方式?

    • 列表和集的使用场景?
      列表是有序的,但是对于不关心元素顺序的场景,使用集更高效,因为查找相当于索引访问数组(当然这里也要考虑哈希冲突导致的列表查找)

    • 队列类似功能方法区别?

    • 优先级队列的实现

    • 更新一个映射值有那些方式

    • 常见的映射表

    • 视图

    https://www.jianshu.com/p/939b8a672070
    https://www.jianshu.com/p/a53b94b2bcca
    https://mp.weixin.qq.com/s?__biz=MzI3NzE0NjcwMg==&mid=2650120877&idx=1&sn=401bb7094d41918f1a6e142b6c66aaac&chksm=f36bbf8cc41c369aa44c319942b06ca0f119758b22e410e8f705ba56b9ac6d4042fe686dbed4&mpshare=1&scene=1&srcid=1010L0NNyoRB5lVoryo00awY#rd
    http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2

    相关文章

      网友评论

        本文标题:JAVA集合和映射表源码详细解读

        本文链接:https://www.haomeiwen.com/subject/sytroqtx.html