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

This article mainly introduces "how to realize the Collection interface of Java". In the daily operation, I believe many people have doubts about how to realize the Collection interface of Java. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the questions of "how to realize the Collection interface of Java". Next, please follow the editor to study!

Collection interface

The Collection interface is the most basic collection interface, it does not provide a direct implementation, and the classes provided by Java SDK are inherited from Collection's "subinterfaces" such as List and Set. Collection represents a rule that contains elements that must follow one or more rules. For example, some allow repetition and some cannot, some must be inserted sequentially and some are hashes, some support sorting but some do not.

In Java, all classes that implement the Collection interface must provide two sets of standard constructors, one is no parameter to create an empty Collection, and the other is a parameterized constructor with a Collection parameter to create a new Collection, which has the same elements as the incoming Collection. / / basic addition, deletion, modification and query methods are required, and they need to be able to convert to array types.

Public class Collection interface {class collect implements Collection {@ Override public int size () {return 0;} @ Override public boolean isEmpty () {return false;} @ Override public boolean contains (Object o) {return false;} @ Override public Iterator iterator () {return null } @ Override public Object [] toArray () {return new Object [0];} @ Override public boolean add (Object o) {return false;} @ Override public boolean remove (Object o) {return false;} @ Override public boolean addAll (Collection c) {return false } @ Override public void clear () {} / / omit part of the code @ Override public Object [] toArray (Object [] a) {return new Object [0];} List interface

The List interface is the Collection direct interface. List stands for ordered Collection, that is, it maintains the order of elements in a specific insertion order. Users can precisely control the insertion position of each element in the list, access the element according to its integer index (position in the list), and search for elements in the list. The main collections that implement List interfaces are: ArrayList, LinkedList, Vector, Stack.

2.1 、 ArrayList

ArrayList is a dynamic array and our most commonly used collection. It allows any element that conforms to the rules to be inserted, even including null. Each ArrayList has an initial capacity (10), which represents the size of the array. As the elements in the container increase, so does the size of the container. Each time an element is added to the container, a capacity check is performed, and when there is a quick overflow, a capacity expansion operation is carried out. Therefore, if we specify the number of elements to be inserted, it is best to specify an initial capacity value to avoid excessive expansion operations and waste of time and efficiency.

Size, isEmpty, get, set, iterator, and listIterator operations all run at a fixed time. The add operation runs at an allocated fixed time, that is, adding n elements takes O (n) time (since expansion is taken into account, this is not just as simple as adding elements to share the fixed time overhead).

ArrayList is good at random access. At the same time, ArrayList is asynchronous.

2.2 、 LinkedList

LinkedList, which also implements the List interface, is different from ArrayList. ArrayList is a dynamic array, while LinkedList is a two-way linked list. So it not only has the basic operation method of ArrayList, but also provides the get,remove,insert method in the head or tail of LinkedList.

Due to the different ways of implementation, LinkedList cannot be accessed randomly, and all its operations are performed according to the needs of the double linked list. The operation of the index in the list traverses the list from the beginning or end (from one end near the specified index). The advantage of this is that inserts and deletions can be done in List at a lower cost.

Like ArrayList, LinkedList is asynchronous. If multiple threads access a List at the same time, you must implement access synchronization yourself. One solution is to construct a synchronous List when creating a List: List list = Collections.synchronizedList (new LinkedList (...))

2.3.The Vector is similar to ArrayList, but the Vector is synchronous. So Vector is a thread-safe dynamic array. Its operation is almost the same as ArrayList.

Stack Stack inherits from Vector and implements a last-in, first-out stack. Stack provides five additional methods to enable Vector to be used as a stack. The basic push and pop methods, and the peek method to get the elements at the top of the stack, the empty method to test whether the stack is empty, and the search method to detect the position of an element in the stack. Stack is empty after it has just been created.

Public class List interface {/ / below is the inheritance relationship of List, because the List interface specifies the implementation of such as index query and iterator, so the classes that implement the List interface will have these methods. / / so array operations can be used at the bottom of both ArrayList and LinkedList, but such external invocation methods are generally not provided. / / public interface Iterable// public interface Collection extends Iterable// public interface List extends Collection class MyList implements List {@ Override public int size () {return 0;} @ Override public boolean isEmpty () {return false;} @ Override public boolean contains (Object o) {return false } @ Override public Iterator iterator () {return null;} @ Override public Object [] toArray () {return new Object [0];} @ Override public boolean add (Object o) {return false;} @ Override public boolean remove (Object o) {return false } @ Override public void clear () {} / / omit part of the code @ Override public Object get (int index) {return null;} @ Override public ListIterator listIterator () {return null;} @ Override public ListIterator listIterator (int index) {return null } @ Override public List subList (int fromIndex, int toIndex) {return null;} @ Override public Object [] toArray (Object [] a) {return new Object [0];} Set interface

Set is a Collection that does not include repeating elements. It maintains its own internal ordering, so random access doesn't make any sense. Like List, it also runs the existence of null, but only one. Because of the particularity of the Set interface, all elements passed into the Set collection must be different, and be aware of any mutable objects. If you operate on the elements in the collection, resulting in e1.equals (e2) = = true, some problems are bound to arise. The collections that implement Set interfaces are: EnumSet, HashSet, TreeSet.

EnumSet is a dedicated Set for enumerations. All elements are enumerated types.

HashSet HashSet can be called the fastest query collection, because its interior is implemented in HashCode. The order of its internal elements is determined by the hash code, so it does not guarantee the iterative order of set; in particular, it does not guarantee that the order is permanent.

The public class Set interface {/ / Set interface specifies that the set is regarded as a collection, and uses the addition, deletion, modification and query method similar to the array, while providing the iterator iterator / / public interface Set extends Collection / / public interface Collection extends Iterable / / public interface Iterable class MySet implements Set {@ Override public int size () {return 0 } @ Override public boolean isEmpty () {return false;} @ Override public boolean contains (Object o) {return false;} @ Override public Iterator iterator () {return null;} @ Override public Object [] toArray () {return new Object [0] } @ Override public boolean add (Object o) {return false;} @ Override public boolean remove (Object o) {return false;} @ Override public boolean addAll (Collection c) {return false } @ Override public void clear () {} @ Override public boolean removeAll (Collection c) {return false;} @ Override public boolean retainAll (Collection c) {return false;} @ Override public boolean containsAll (Collection c) {return false } @ Override public Object [] toArray (Object [] a) {return new Object [0];} Map interface

Unlike List and Set interfaces, Map is a collection of key-value pairs that provide key-to-Value mapping. It also does not inherit Collection. In Map, it ensures the one-to-one correspondence between key and value. That is to say, a key corresponds to a value, so it cannot have the same key value, but of course the value can be the same. Map is realized by HashMap, TreeMap, HashTable, Properties and EnumMap.

4.1. HashMap is implemented as a hash table data structure, and its location is calculated by a hash function when looking for an object. It is designed for fast query. An array of hash tables (Entry [] table) is defined internally. The element converts the hash address of the element into the index stored in the array through the hash conversion function. If there is a conflict, all elements with the same hash address are strung together in the form of a hash list. Perhaps by looking at the source code of HashMap.Entry, it is a single linked list structure.

4.2.The TreeMap keys are sorted by some sort of sorting rules, and the internal data structure is implemented by red-black (red-black) tree, and the SortedMap interface is realized.

HashTable is also implemented in hash table data structure, and the conflict resolution is also in the form of hash linked table like HashMap, but the performance is lower than HashMap.

Public class Map interface {/ / Map interface is the top interface, and the Map interface implementation class must implement hash operations such as put and get. / and provide query structures such as keyset and values, as well as entryset. / / public interface Map class MyMap implements Map {@ Override public int size () {return 0;} @ Override public boolean isEmpty () {return false;} @ Override public boolean containsKey (Object key) {return false;} @ Override public boolean containsValue (Object value) {return false } @ Override public Object get (Object key) {return null;} @ Override public Object put (Object key, Object value) {return null;} @ Override public Object remove (Object key) {return null } @ Override public void putAll (Map m) {} @ Override public void clear () {} @ Override public Set keySet () {return null;} @ Override public Collection values () {return null } @ Override public Set entrySet () {return null;} Queue

Queue, it is mainly divided into two categories, one is blocking queue, after the queue is full and then insert elements will throw an exception, including ArrayBlockQueue, PriorityBlockingQueue, LinkedBlockingQueue. The other queue is a double-ended queue, which supports inserting and removing elements at both ends of the header and tail, including: ArrayDeque, LinkedBlockingDeque, and LinkedList.

Public class Queue interface {/ / queue interface is an implementation of the queue, which needs to provide methods such as queuing in and out of the queue. Linkedlist is generally used as the implementation class class MyQueue implements Queue {@ Override public int size () {return 0;} @ Override public boolean isEmpty () {return false;} @ Override public boolean contains (Object o) {return false } @ Override public Iterator iterator () {return null;} @ Override public Object [] toArray () {return new Object [0];} @ Override public Object [] toArray (Object [] a) {return new Object [0] } @ Override public boolean add (Object o) {return false;} @ Override public boolean remove (Object o) {return false;} / / omit part of the code @ Override public boolean offer (Object o) {return false } @ Override public Object remove () {return null;} @ Override public Object poll () {return null;} @ Override public Object element () {return null;} @ Override public Object peek () {return null A cheat sheet about the Java collection

This part of the content to my idol Jiangnan white blog: http://calvin1978.blogcn.com/articles/collection.html in as short a space as possible, all sets and concurrent sets of the characteristics, implementation, performance. It is suitable for all people who are proficient in Java but are not so confident in reading.

It is expected that it can not only be used in the interview, usually choose the data structure, but also consider its cost and efficiency, do not look at the API is suitable to use.

List

1.1 ArrayList is implemented as an array. Save space, but the array has a capacity limit. When the limit is exceeded, the capacity is increased by 50% and copied to the new array with System.arraycopy (). So it's best to give an estimate of the size of the array. By default, an array of size 10 is created the first time an element is inserted.

Accessing elements by array subscript-get (I), set (iMagne)-has high performance, which is the basic advantage of arrays.

If you press the subscript to insert elements and delete elements-add (iGraine e), remove (I), remove (e), then System.arraycopy () is used to copy the elements affected by the move, resulting in poor performance.

The more previous elements, the more elements to move when you modify. Adding an element directly to the end of the array-the usual add (e)-has no effect if you delete the last element.

1.2 LinkedList is implemented as a two-way linked list. The linked list has no capacity limit, but the two-way linked list itself uses more space, and each element inserted requires the construction of an additional Node object and additional linked list pointer operations.

Press the subscript to access the elements-get (I), set (iQuery e) to traverse the linked list to move the pointer into place (from the end if I > half the size of the array).

When inserting or deleting elements, you can modify the pointers of the front and rear nodes, and you no longer need to copy and move them. However, it is still necessary to partially traverse the pointer of the linked list to move to the position indicated by the subscript.

Only operations at both ends of the linked list-add (), addFirst (), removeLast (), or remove () on iterator ()-can save pointer movement.

Apache Commons has a TreeNodeList, which is a binary tree, which can quickly move the pointer into place.

1.3 CopyOnWriteArrayList concurrency optimized ArrayList. Based on the immutable object strategy, first copy an array snapshot to modify it, change it, and then let the internal pointer point to the new array.

Because changes to the snapshot are not visible to the read operation, there is no mutual exclusion between reads and writes, only locking mutual exclusion between writes and writes. However, it is expensive to copy snapshots, which is typically suitable for scenarios with more reads and less writes.

Although the addIfAbsent (e) method is added, which traverses the array to see if the element already exists, the performance is not imaginable.

Unfortunately, no matter which implementation, returning subscript contains (e), indexOf (e), remove (e) by value will need to traverse all the elements for comparison, and the performance will not be very good.

There is no SortedList sorted by element value.

Apart from CopyOnWriteArrayList, there is no other thread-safe and concurrency-optimized implementation such as ConcurrentLinkedList. When making do with the equivalence classes in Set and Queue, some List-specific methods such as get (I) are missing. If the update frequency is high, or if the array is large, you still have to use Collections.synchronizedList (list), and use the same lock for all operations to ensure thread safety.

Map

2.1 HashMap

For the hash bucket array implemented by the Entry [] array, the array subscript can be obtained by taking the size of the mold bucket array with the hash value of Key.

When inserting an element, if two Key fall on the same bucket (for example, hash values 1 and 17 belong to the first hash bucket after module 16), we call it a hash conflict.

The method of JDK is linked list, and Entry uses a next attribute to store multiple Entry in an one-way linked list. When looking for a key with a hash value of 17, locate the hash bucket first, and then the linked list traverses all the elements in the bucket, comparing their hash values and then key values one by one.

In JDK8, the default threshold of 8 is added. When the Entry in a bucket exceeds the threshold value, it is stored in a red-black tree instead of an one-way linked list to speed up the search of Key.

Of course, it's better to have only one element in the bucket without having to compare it. Therefore, by default, when the number of Entry reaches 75% of the number of buckets, the hash conflict is already serious, so the array of buckets will be multiplied and all the original Entry will be redistributed. The cost of capacity expansion is not low, so it is best to have an estimate.

Modularization and operation (hash & (arrayLength-1)) will be faster, so the size of the array is always 2 to the N power, any initial value such as 17 will be converted to 32. By default, the initial value when the element is first placed is 16.

Traversing the hash bucket array when iterator () appears to be out of order.

2.2 LinkedHashMap extends HashMap, adding bi-directional linked lists to each Entry, which claims to be the most memory-intensive data structure.

Sort by the order in which Entry is inserted when iterator () is supported (if the accessOrder property is set to true, all read and write accesses are sorted).

When plugged in, Entry adds himself in front of the Header Entry. If all read and write accesses need to be sorted, the before/after of the front and back Entry should also be concatenated to remove themselves from the linked list, so the read operation is not thread-safe at this time.

2.3 TreeMap is implemented in a red-black tree, which is also called a self-balanced binary tree:

For any node, each path to the leaf node contains the same number of black nodes. The above rules make the number of layers of the tree not too far, so that the complexity of all operations is not more than O (lgn), but it also makes complex left-handed and right-handed rotation during insertion and modification to maintain the balance of the tree.

Sort by key value when iterator () is supported, can be sorted by ascending order of the Key that implements the Comparable interface, or controlled by the incoming Comparator. It is conceivable that inserting / deleting elements on a tree must be more expensive than HashMap.

SortedMap interfaces are supported, such as firstKey (), lastKey () to get the maximum and minimum key, or sub (fromKey, toKey), tailMap (fromKey) to cut a certain segment of Map.

The principle of EnumMap EnumMap is that if you pass an enumeration class into the constructor, it builds an array as large as all the values of the enumeration, and press Enum. The ordinal () subscript accesses the array. Excellent performance and memory footprint.

The only drawback is that because the Map interface is to be implemented, and the key in V get (Object key) is Object rather than generic K, for security reasons, EnumMap must first determine the type of Key for each visit, and a high sampling hit frequency is recorded in JMC.

2.5 ConcurrentHashMap concurrency optimized HashMap.

The classic design in JDK5 defaults to 16 write locks (more can be set), effectively spreading the probability of blocking. The data structure is Segment [], with one lock for each Segment. Inside Segment is the hash bucket array. Key works out which Segment it is in, and then which hash bucket it is in.

There is also no read lock, because the put/remove action is an atomic action (for example, the whole process of put is an assignment to array elements / Entry pointers), and the read operation does not see the intermediate state of an update action.

But in JDK8, the design of Segment [] is abandoned and carefully designed to add locks only when they are needed.

Support ConcurrentMap interfaces, such as putIfAbsent (key,value) and opposite replace (key,value) and replace (key, oldValue, newValue) that implement CAS.

The concurrency optimized SortedMap added by 2.6ConcurrentSkipListMap JDK6 is implemented in SkipList structure. The Concurrent package chose it because it supports lock-free algorithms based on CAS, while red-black trees do not have a good lock-free algorithm.

In principle, it can be thought of as an N-story building composed of multiple linked lists, with elements ranging from sparse to dense, each with pointers to the right and down. Start traversing from the first floor, and if the value at the right end is larger than expected, go down one floor and go on.

Typical space for time. Each time you insert, you have to decide which floor to insert, and at the same time, you have to decide whether or not to build one more floor.

Its size () also can not be adjusted casually, it will be counted all the time.

Set

Almost all Set is implemented internally with a Map, because KeySet in Map is a Set, while value is a false value, all using the same Object.

The characteristics of Set also inherit those of internal Map implementations.

HashSet: inside is HashMap.

LinkedHashSet: inside is LinkedHashMap.

TreeSet: inside is the SortedSet of TreeMap.

ConcurrentSkipListSet: inside is the concurrency-optimized SortedSet of ConcurrentSkipListMap.

CopyOnWriteArraySet: inside is CopyOnWriteArrayList's concurrency-optimized Set, which uses its addIfAbsent () method to de-duplicate elements, which, as mentioned earlier, has mediocre performance.

It seems that without a ConcurrentHashSet, there should have been a simple implementation using ConcurrentHashMap internally, but JDK did not provide it. Jetty simply sealed one of its own, while Guava was directly implemented in java.util.Collections.newSetFromMap (new ConcurrentHashMap ()).

Queue

Queue is a List that goes in and out at both ends, so it can also be implemented as an array or a linked list.

4.1 normal queue 4.1.1 LinkedList Yes, the LinkedList implemented in a two-way linked list is both List and Queue.

4.1.2 A bi-directional Queue implemented by ArrayDeque as a circular array. The size is a multiple of 2, and the default is 16.

To support FIFO, that is, pushing elements from the array tail (fast) and fetching elements from the array header (ultra-slow), you can no longer use the normal ArrayList implementation, but use circular arrays instead.

There are two subscripts at the head and end of the line: when the element is popped up, the subscript at the head of the line increases; when the element is added, the subscript at the end of the line is incremented. If the element is at the end of the array space when it is added, the element is assigned to the array [0], while the subscript at the end of the line points to 0, and if the next element is inserted, it is assigned to the array [1], and the subscript at the end of the line points to 1. If the subscript at the end of the line catches up with the head of the line, it means that all the space in the array has been used up and double the capacity of the array.

4.1.3 the priority queue implemented by PriorityQueue with balanced binary minimum heap is no longer FIFO, but is dequeued by the Comparable interface implemented by elements or the comparison result passed in Comparator. The smaller the value is, the higher the priority is, and the first to dequeue. Note, however, that the return of its iterator () is not sorted.

Balanced minimum binary heap, which can be expressed in a simple array, can be addressed quickly, without pointers and so on. The youngest is in queue [0], such as two children in queue [4], in queue [24 + 1] and queue [2 (4)], that is, queue [9] and queue [10].

When you join the queue, insert queue [size], and then compare the adjustment heap binary up.

When you leave the team, pop up the queue [0], and then take out the queque [size] and compare the adjustment heap down binarily.

The initial size is 11, and the capacity is expanded by 50% automatically when there is not enough space.

4.2.1Thread-safe queue 4.2.1 ConcurrentLinkedQueue/Deque unbounded concurrency optimized Queue, based on linked lists, implements an unlocked algorithm that depends on CAS.

The structure of ConcurrentLinkedQueue is an one-way linked list and two pointers of head/tail, because when joining the queue, you need to modify the next pointer of the element at the end of the queue, and modify the tail to the new element. The two CAS actions cannot be atomic, so you need a special algorithm.

4.3.Thread-safe blocking queue BlockingQueue, on the one hand, if the queue is empty, it will block there without repeatedly checking whether there is any new data, and second, the length of the queue is limited to ensure that the speed of producers and consumers will not be too far apart. The queue is full when you join the queue, or empty when you leave the queue. The effects of different functions are shown in the following table:

Immediately report an exception and immediately return to Boolean blocking to wait. Add (e) offer (e) put (e) offer (e, timeout, unit) dequeue remove () poll () take () poll (timeout, unit) check element () peek () none

4.3.1 concurrency optimized BlockingQueue with fixed length of ArrayBlockingQueue is also implemented based on circular array. There is a common lock and two Condition, notFull and notEmpty, to manage the blocking state when the queue is full or empty.

4.3.2 LinkedBlockingQueue/Deque can choose a long concurrency optimized BlockingQueue, which is based on a linked list, so you can set the length to Integer.MAX_VALUE to be unbounded and unwaiting.

Using the characteristics of the linked list, the two locks of takeLock and putLock are separated, and notEmpty and notFull are used to manage the blocking state when the queue is full or empty.

4.3.3 PriorityBlockingQueue unbounded PriorityQueue is also a binary heap based on array storage (see above). A common lock implements thread safety. Because there is no boundary, the capacity will be expanded automatically when there is not enough space, so it will not be locked when it is listed, but it will only be locked when it is empty.

4.3.4 DelayQueue contains a PriorityQueue inside, which is also unbounded and locked only when it is dequeued. A common lock implements thread safety. The element needs to implement the Delayed interface. You need to return how long it is until the trigger time is returned for each call. A value less than 0 indicates that it is time to trigger.

Pull () looks at the elements at the head of the line with peek () to see if the trigger time has been reached. ScheduledThreadPoolExecutor uses a similar structure.

Synchronization queue SynchronousQueue synchronization queue itself has no capacity and is returned when an element is placed, such as waiting for the element to be taken away by the consumer of another thread. Use it in the JDK thread pool.

JDK7 also has a LinkedTransferQueue, which adds a transfer (e) function to the normal thread-safe BlockingQueue, which has the same effect as SynchronousQueue.

At this point, the study on "how to implement the Collection interface of Java" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.