Shulou(Shulou.com)06/02 Report--

JDK container class List and Set and Queue source code how to write, in view of this problem, this article introduces the corresponding analysis and solutions in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

List,Set,Queue is a single-column collection interface that inherits the Collection interface. The common implementation of List is that the data in ArrayList,LinkedList,List is orderly and repeatable. The common implementation of Set is that the data in HashSet,Set is unordered and unrepeatable. The common implementation of Queue is that ArrayBlockingQueue,LinkedBlockingQueue,Queue is a first-in-first-out sequential queue, which does not allow random access to the elements in the queue.

Interpretation of ArrayList Core Source Code

ArrayList is an underlying collection implemented in an array, the array element type is Object type, supports random access, the elements are orderly and repeatable, it inherits from AbstractList and implements List, RandomAccess, Cloneable, java.io.Serializable interfaces.

When a collection is constructed through ArrayList (), it constructs an empty array with an initial length of 0. When an element is added for the first time, an array of length 10 is created and assigned to the first position of the array. When the added element is greater than 10, the array is expanded for the first time. The capacity is expanded 1.5 times, and the length is changed to 15.

ArrayList cannot be modified when traversing, that is, elements cannot be added or deleted when traversing, otherwise ConcurrentModificationException will be thrown.

ArrayList is not thread-safe.

The main field in the ArrayList source code / / the size of the default array private static final int DEFAULT_CAPACITY = 10 role / default empty array private static final Object [] EMPTY_ELEMENTDATA = {}; / / the constructor / * Constructs an empty list with an initial capacity of ten in the array private transient Object [] elementData;ArrayList source code where the data is actually stored. * / public ArrayList () {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;} / * * Constructs an empty list with the specified initial capacity. * * @ param initialCapacity the initial capacity of the list * @ throws IllegalArgumentException if the specified initial capacity * is negative * / public ArrayList (int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object [initialCapacity]; / / treat the custom capacity size as the size of the initialization elementData} else if (initialCapacity = = 0) {this.elementData = EMPTY_ELEMENTDATA } else {throw new IllegalArgumentException ("Illegal Capacity:" + initialCapacity);} add method / * Appends the specified element to the end of this list in ArrayList source code. * * @ param e element to be appended to this list * @ return true (as specified by {@ link Collection#add}) * / public boolean add (E e) {ensureCapacityInternal (size+ 1); / / before adding elements, first determine the size of the collection elementData [size++] = e; / / put the element e in the correct position in the data, and size++ return true } private void ensureCapacityInternal (int minCapacity) {ensureExplicitCapacity (calculateCapacity (elementData, minCapacity));} private static int calculateCapacity (Object [] elementData, int minCapacity) {if (elementData = = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {/ / if it is an empty array return Math.max (DEFAULT_CAPACITY, minCapacity); / / returns the default I array length} return minCapacity } private void ensureExplicitCapacity (int minCapacity) {modCount++; / / number of modifications + 1, equivalent to version number / / overflow-conscious code if (minCapacity-elementData.length > 0) / / if the actual capacity is less than the required capacity grow (minCapacity) / / capacity expansion} / * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @ param minCapacity the desired minimum capacity * / private void grow (int minCapacity) {/ / overflow-conscious code int oldCapacity = elementData.length; / / get the current length of the array int newCapacity = oldCapacity + (oldCapacity > > 1); / / the length of the new array is equal to 1.5 times the length of the original array if (newCapacity-minCapacity)

< 0) //当新数组长度仍然比minCapacity小，则为保证最小长度，新数组等于minCapacity newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE >

0) / / when the length of the new array is larger than MAX_ARRAY_SIZE, call hugeCapacity to process the large array newCapacity = hugeCapacity (minCapacity); / / minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf (elementData, newCapacity); / / call Arrays.copyOf to copy the original array to a new array of size newCapacity (copy reference)} private static int hugeCapacity (int minCapacity) {if (minCapacity)

< 0) // overflow throw new OutOfMemoryError(); return (minCapacity >

MAX_ARRAY_SIZE)? Integer.MAX_VALUE: the maximum length of the MAX_ARRAY_SIZE; / / array is the get method / * Returns the element at the specified position in this list in Integer.MAX_VALUE} ArrayList source code. * * @ param index index of the element to return * @ return the element at the specified position in this list * @ throws IndexOutOfBoundsException {@ inheritDoc} * / public E get (int index) {rangeCheck (index); / / determine the validity of the index return elementData (index);} thread-safe ArrayList--CopyOnWriteArrayList

CopyOnWriteArrayList is a thread-safe ArrayList collection class based on the idea of copy-on-write (copy-on-write). It implements the List interface, holds a ReentrantLock internally to lock the write, and the bottom layer is the array array declared with volatile transient, which is read-write separate. when writing data, a new array is copied and ReentrantLock lock is added. After writing, the new array is assigned to the current array, and the read operation does not need to obtain a lock and supports concurrency.

The replication of CopyOnWriteArrayList leads to the fact that the data is not real-time and has a certain delay. At the same time, because of the replication of data, it will take up a lot of memory when the amount of data is very large.

CopyOnWriteArrayList is suitable for scenarios that read more and write less.

CopyOnWriteArrayList core source code interprets / / stores data array private transient volatile Object [] array; / * add data method * Appends the specified element to the end of this list. * * @ param e element to be appended to this list * @ return {@ code true} (as specified by {@ link Collection#add}) * / public boolean add (E) {final ReentrantLock lock = this.lock; lock.lock (); / / Lock to ensure data security try {Object [] elements = getArray () / / get the array int len = elements.length; / / get the array length Object [] newElements = Arrays.copyOf (elements, len + 1); / / copy the array to the new array newElements [len] = e; / / assign the element to the end of the new array setArray (newElements); / / set the new array to the current array return true } finally {lock.unlock (); / / unlock}} HashSet source code interpretation

HashSet is the most commonly used Set implementation, which inherits the AbstractSet abstract class and implements the Set,Cloneable and java.io.Serializable interfaces. What is stored in HashSet is unordered and unrepeatable data, and its underlying data storage is realized through HashMap. HashSet stores the data in the key of HashMap and sets the value of HashMap as an Object reference.

HashSet Core Source Code interpretation / / value reference of HashMapprivate transient HashMap map;// HashMap for actual data storage private static final Object PRESENT = new Object (); / * * Constructs a new, empty set; the backing HashMap instance has * default initial capacity (16) and load factor (0.75). * / public HashSet () {map = new HashMap (); / / new a HashMap object with no parameter HashMap constructor, with default initial capacity (16) and load factor (0.75). } / * Adds the specified element to this set if it is not already present. * More formally, adds the specified element e to this set if * this set contains no element e2 such that * (e==null? e2==null: e.equals (E2)). * If this set already contains the element, the call leaves the set * unchanged and returns false. * * @ param e element to be added to this set * @ return true if this set did not already contain the specified * element * / public boolean add (E) {return map.put (e, PRESENT) = = null;} Thread-safe HashSet--CopyOnWriteArraySet

CopyOnWriteArraySet is a thread-safe HashSet, and its underlying layer is implemented through CopyOnWriteArrayList. It realizes the non-repeatability of data by adding data if it does not exist when adding data.

CopyOnWriteArraySet core source code interpretation / / actual storage data private final CopyOnWriteArrayList al; / * Adds the specified element to this set if it is not already present. * More formally, adds the specified element {@ code e} to this set if * the set contains no element {@ code e2} such that * (e==null? e2==null: e.equals (e2)). * If this set already contains the element, the call leaves the set * unchanged and returns {@ code false}. * * @ param e element to be added to this set * @ return {@ code true} if this set did not already contain the specified * element * / public boolean add (E) {return al.addIfAbsent (e); / / add} Queue detailed analysis if it does not exist

Queue is a queue data structure of first-in, first-out (FIFO), which can be divided into blocking queue and non-blocking queue. Queue interface inherits Collection interface at the same level as List and Set.

Queue API method describes the function of add to add an element if the queue is full, throw an IIIegaISlabEepeplian exception remove remove and return the queue header element if the queue is empty, throw a NoSuchElementException exception element returns the queue header element if the queue is empty, throw a NoSuchElementException exception offer add an element and return true if the queue is full, return falsepoll remove and ask the queue header element if the queue is listed as empty Return nullpeek returns the element of the queue header if the queue is empty, return nullput to add an element if the queue is full, block take remove and return the element of the queue header if the queue is empty, block ArrayBlockingQueue source code interpretation

ArrayBlockingQueue is a thread-safe, bounded blocking queue implemented by an array.

/ / Array final Object [] items;// to store data int takeIndex;// put data index int putIndex;// data quantity int count;// lock final ReentrantLock lock; / * Condition for waiting takes * / private final Condition notEmpty;/** Condition for waiting puts * / private final Condition notFull; / * * items index for next put, offer, or add * / int putIndex / * * Inserts the specified element at the tail of this queue if it is * possible to do so immediately without exceeding the queue's capacity, * returning {@ code true} upon success and {@ code false} if this queue * is full. This method is generally preferable to method {@ link # add}, * which can fail to insert an element only by throwing an exception. * * @ throws NullPointerException if the specified element is null * / public boolean offer (E e) {/ / offer method is non-blocking checkNotNull (e); lock lock.lock () when final ReentrantLock lock = this.lock; / / offer; try {if (count = = items.length) / / return false return false if there is no space Else {enqueue (e); / / if space is available, queue return true;}} finally {lock.unlock ();}} / * Inserts the specified element at the tail of this queue, waiting * for space to become available if the queue is full. * * @ throws InterruptedException {@ inheritDoc} * @ throws NullPointerException {@ inheritDoc} * / public void put (E) throws InterruptedException {checkNotNull (e); final ReentrantLock lock = this.lock; / / locked lock.lockInterruptibly (); try {while (count = = items.length) / / queue has full capacity notFull.await () / / blocking enqueue (e);} finally {lock.unlock ();}} public E take () throws InterruptedException {final ReentrantLock lock = this.lock; lock.lockInterruptibly (); try {while (count = = 0) notEmpty.await () / / when the queue is empty, it will put the thread into a blocking state until the element return dequeue () is taken out when it is awakened by another thread; / / the element in the consumption peer} finally {lock.unlock ();}} LinkedBlockingQueue source code interpretation

The underlying LinkedBlockingQueue is a blocked thread-safe queue implemented using linked lists. If no size is specified when LinkedBlockingQueue is constructed, the default size is Integer.MAX_VALUE. Of course, you can also specify the size in the parameters of the constructor. Two locks are used in LinkedBlockingQueue, adding takeLock when fetching data and putLock when putting data.

/ / capacity number of private final int capacity;// elements private final AtomicInteger count = new AtomicInteger (); / / chain header transient Node head;// chain footer private transient Node last;// take lock private final ReentrantLock takeLock = new ReentrantLock (); / / when the queue has no elements, the take lock will block on the notEmpty condition, waiting for other threads to wake up private final Condition notEmpty = takeLock.newCondition (); / / release lock private final ReentrantLock putLock = new ReentrantLock () / / when the queue is full, the put lock will block on the notFull and wait for other threads to wake up private final Condition notFull = putLock.newCondition (); / * * Creates a {@ code LinkedBlockingQueue} with a capacity of * {@ link Integer#MAX_VALUE}. * / public LinkedBlockingQueue () {this (Integer.MAX_VALUE); / / if no capacity is transferred, initialize its capacity with the maximum int value} / * Inserts the specified element at the tail of this queue, waiting if * necessary for space to become available. * * @ throws InterruptedException {@ inheritDoc} * @ throws NullPointerException {@ inheritDoc} * / public void put (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 node = new Node (e); final ReentrantLock putLock = this.putLock; / / use the putLock lock final AtomicInteger count = this.count; putLock.lockInterruptibly (); try {/ * Note that count is used in wait guard even though it is * not protected by lock. This works because count can * only decrease at this point (all other puts are shut * out by lock), and we (or some other waiting put) are * signalled if it ever changes from capacity. Similarly * for all other uses of count in other wait guards. * / while (count.get () = = capacity) {/ / if the queue is full, notFull.await () is blocked on the notFull condition; / / waiting to be awakened by other threads} enqueue (node); / / if the queue is dissatisfied, join the queue 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加锁 takeLock.lockInterruptibly(); try { while (count.get() == 0) { // 如果队列无元素，则阻塞在notEmpty条件上 notEmpty.await(); } x = dequeue(); c = count.getAndDecrement(); if (c >

1) notEmpty.signal ();} finally {takeLock.unlock ();} if (c = = capacity) signalNotFull (); return x;} ConcurrentLinkedQueue source code interpretation

ConcurrentLinkedQueue is a thread-safe unbounded non-blocking queue, its underlying data structure is implemented by an one-way linked list, and queuing and dequeuing operations use the CAS that we often mention to ensure thread safety. The element that ConcurrentLinkedQueue does not allow to insert is null.

Private transient volatile Node head;private transient volatile Node tail;private static final sun.misc.Unsafe UNSAFE;private static final long headOffset;private static final long tailOffset; / * * Inserts the specified element at the tail of this queue. * As the queue is unbounded, this method will never return {@ code false}. * * @ return {@ code true} (as specified by {@ link Queue#offer}) * @ throws NullPointerException if the specified element is null * / public boolean offer (E) {checkNotNull (e); / / if null throws a null pointer exception final Node newNode = newNode (e); for (Node t = tail, p = t;) {/ / spin Node Q = p.next If (q==null) {/ / if q==null indicates that p is the tail node Then insert / / p is last node if (p.casNext (null, newNode)) {/ / set the next node of p node / / Successful CAS is the linearization point / / for e to become an element of this queue, / / and for newNode to become "live" using CAS. If (p! = t) / / hop two nodes at a time casTail (t, newNode); / / Failure is OK. Return true;} / / Lost CAS race to another thread; re-read next} else if (p = = Q) / / We have fallen off list. If tail is unchanged, it / / will also be off-list, in which case we need to / / jump to head, from which all live nodes are always / / reachable. Else the new tail is a better bet. P = (t! = (t = tail))? T: head; else / / Check for tail updates after two hops. P = (p! = t & & t! = (t = tail))? T: Q;} on the JDK container class List and Set and Queue source code how to write the answer to share here, I hope the above content can be of some help to you, if you still have a lot of doubts to be solved, you can follow the industry information channel for more related knowledge.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.