This paper introduces the basic framework of Java collection class, interface structure and part of the source code analysis, and through their own implementation of some collection class to better analyze the overall structure of Java collection class.
We will write several articles on collection classes and introduce the implementation classes of the List, Map, Set and Stack interfaces.
In writing Java programs, we most commonly used in addition to the eight basic data types, String object and a collection class, in our program everywhere full of collection class figure!
This paper introduces the basic framework of Java collection class, interface structure and part of the source code analysis, and through their own implementation of some collection class to better analyze the overall structure of Java collection class.
This article just carries on a general comb to the collection class framework, after all, the collection framework contains too many classes, an article is impossible to finish, here first start, have a clear understanding of the overall framework, and then explore the mystery of each interface implementation class.
Java has a rich family of collections, including ArrayList, HashMap, HashSet, Stack, Queue, thread-safe Vector, HashTable, etc. There are also thread-unsafe linkedLists, TreeMap, and so on!
The diagram above shows the members of the entire collection family and their relationships. The following is a brief introduction to the above various interfaces and base classes (mainly introduces the characteristics of each collection. Difference).
The following diagrams illustrate the relationship between interfaces of the composite class more clearly:
Map implementation class
I. Collection interface
The Collection interface is the most basic Collection interface. It does not provide a direct implementation. The Java SDK provides classes that inherit from the Collection “subinterfaces” such as List and Set. What a Collection represents is a rule that all the elements it contains must follow one or more rules. Some allow repetition and some cannot, some must be inserted sequentially and some hashes, some supports sorting and some does not.
In Java, all classes that implement the Collection interface must provide two standard sets of constructors, one that takes no arguments to create an empty Collection and one that takes arguments to create a new Collection. This new Collection has the same elements as the incoming Collection. // Implement basic add, delete, change and query methods, and need to be able to convert to an array type
Public class Collection interface {class Collection 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() {} @override public Object[]toArray (Object[]a) {return(newObject [0]); }}}Copy the codeList interface
The List interface is the direct interface of Collection. What a List represents is an ordered Collection, that is, it maintains the order of elements with some particular insertion order. The user has precise control over the insertion position of each element in the list, and can access elements based on their integer index (position in the list) and search for elements in the list. List interface implementation of the main set of: ArrayList, LinkedList, Vector, Stack.
1. ArrayList
ArrayList is a dynamic array, and the collection we use most often. It allows any element that conforms to the rule to be inserted, including NULL. Each ArrayList has an initial capacity (10) that represents the size of the array. As the number of elements in the container increases, so does the size of the container. A capacity check is performed each time an element is added to the container, and when overflow is imminent, capacity expansion is performed. Therefore, if we know how many elements to insert, it is better to specify an initial capacity value, so as to avoid wasting time and efficiency by too many expansion operations.
Size, isEmpty, get, set, iterator, and listIterator operations all run at a fixed time. The Add operation runs at apportioned fixed time, that is, it takes O(n) time to add n elements (it’s not just that adding elements has apportioned fixed time overhead because of capacity expansion).
Arraylists are good at random access. The ArrayList is also asynchronous.
2. LinkedList
LinkedList, which also implements the List interface, is different from ArrayList, which is a dynamic array, and LinkedList, which is a two-way LinkedList. So in addition to the basic operations of ArrayList, it also provides get, remove, insert methods at the beginning or end of LinkedList.
Because of the way it is implemented, LinkedList cannot be accessed randomly, and all operations are performed according to the requirements of a double LinkedList. The operation of an index in a list traverses the list from the beginning or end (from the end close to the specified index). The advantage of this is that you can insert and delete from the List at a lower cost.
Like ArrayList, LinkedList is asynchronous. If multiple threads access a List at the same time, they must implement access synchronization themselves. One solution is to construct a synchronization when creating a List of the List: a List List = Collections. SynchronizedList (new LinkedList (…). );
3. Vector is similar to ArrayList, but Vector is synchronous. So Vector is a thread-safe dynamic array. It operates almost the same as ArrayList.
A Stack inherits from a Vector and implements a lifO Stack.
Stack provides five additional methods that allow a Vector to be used as a Stack. The basic push and POP methods, as well as peek to get the element at the top of the stack, empty to see if the stack is empty, and search to see where an element is in the stack. The Stack is empty right after it is created.
The following is the inheritance of the List interface. Since the List interface specifies implementations such as index queries and iterators, classes that implement the List interface will have these methods. */ /* So both ArrayList and LinkedList can use array operations at the bottom, but there are generally no such external calls. ` */ public interface Iterable<T> public interface Collection<E> extends Iterable<E> public interface List<E> extends Collection<E> 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); 27. } @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() {} @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]); }}}Copy the code3. Set interface
A Set is a Collection that does not contain repeating elements. It maintains its own internal ordering, so random access doesn’t make any sense. Like List, it also runs the presence of NULL but only one. Due to the special nature of the Set interface, all elements passed into the Set must be different, and note that any mutable object that causes E1.equals (e2)==true when operating on elements in the Set is bound to cause some problems. Set interfaces include EnumSet, HashSet, and TreeSet.
3.1. EnumSet is a dedicated Set for enumeration. All elements are enumerated types.
A HashSet is the fastest collection to query because it is implemented internally in HashCode. The order of its internal elements is determined by the hash code, so it does not guarantee the iteration order of the set; In particular, it does not guarantee the constancy of the order.
Public class Set {/* Set specifies that a Set is treated as a Set, and is added, subtracted, modified, and looked up in the same way as an array. */ * Public interface Set<E> extends Collection<E> */ /* Public interface Collection<E> extends Iterable<E> */ /* public interface Iterable<T> */ 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]); }}}Copy the code4. Map interface
Unlike the List and Set interfaces, a Map is a Set of key-value pairs and provides the mapping between keys and values. It also does not inherit Collection. It ensures a one-to-one correspondence between keys and values in a Map. That is, a key corresponds to a value, so it cannot have the same key value, but of course the value can be the same. Map implementation includes HashMap, TreeMap, HashTable, Properties, and EnumMap.
4.1. HashMap is implemented in a hash table data structure. When an object is searched, its position is calculated by the hash function. Use a hash list to string together all elements of the same hash address, perhaps by looking at the source code for Hashmap.Entry, which is a single list structure.
4.2 TreeMap keys are sorted by some sort rules, and are internally implemented by red-black tree data structure, which implements SortedMap interface
4.3 HashTable is also implemented as a HashTable data structure, and the form of hash linked list is also used to resolve conflicts with HashMap, but the performance is lower than that of HashMap
Public class Map interface {/* The Map interface is the topmost interface. The Map interface implementation class must implement hash operations such as PUT and GET. */ /* Also provide query structures such as keySet and values, and entrySet. */ /* public interface Map<K,V> */ 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<Entry> entrySet() { return(null); }}}Copy the codeFive, the Queue
Queue, it is mainly divided into two categories, one is blocking queue, queue full after the insertion of elements will throw an exception, mainly including ArrayBlockQueue, PriorityBlockingQueue, LinkedBlockingQueue. The other type of queue is a double-ended queue, which supports the insertion and removal of elements at the head and tail, including ArrayDeque, LinkedBlockingDeque, LinkedList.
Public class Queue interface {/* Queue interface is an implementation of queues, need to provide Queue in Queue out Queue methods. */ 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); } /* 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); }}}Copy the codeCheat sheet on Java collections
This part of self idol Blog: jiangnan white calvin1978.blogcn.com/articles/co… In the shortest possible space, outline the characteristics, implementation, and performance of all collections and concurrent collections. For anyone who is “Java savvy” and not really that confident.
Expect to be able to choose data structures not only in interviews, but also in terms of cost and efficiency, not just when the API fits.
1. List
1.1 ArrayList is an array implementation.
Saves space, but arrays have capacity limits. When the limit is exceeded, the capacity is increased by 50% and copied to the new array with system.arrayCopy (). Therefore, it is good to give an estimate of the size of the array. The default is to create an array of size 10 the first time an element is inserted.
The basic advantage of arrays is the high performance of accessing elements by array subscript -get (I), set (I,e).
If you insert elements and delete elements -add (I,e), remove (I), remove (e), then you have to use system.arrayCopy () to copy and move some of the affected elements.
The earlier the element, the more elements you have to move. Add elements directly to the end of the array – the usual add (e) – and delete the last element without affecting it.
1.2 LinkedList is implemented as a two-way LinkedList.
Lists have no capacity limits, but two-way lists themselves use more space, and each element inserted requires an additional Node object to be constructed, as well as additional list pointer operations.
Press the subscript to access the elements -get (I), set (I,e) 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 nodes before and after, without copying and moving. But it still takes partial traversal to move the pointer to the index.
Only the operations -add (), addFirst (), removeLast (), or remove () on iterator () at either end of the list can eliminate pointer movement.
Apache Commons has a TreeNodeList, which is a binary tree that can quickly move Pointers into place.
1.3 CopyOnWriteArrayList Concurrent optimized ArrayList.
Based on immutable object policy, a snapshot of the array is copied to modify, and then the internal pointer points to the new array.
Since changes to a snapshot are not visible to read operations, read and write operations are not mutually exclusive. Only write and write operations are mutually exclusive with locks. However, snapshot replication is expensive and is typically suitable for scenarios with more read and less write.
Although the addIfAbsent (e) method is added to iterate over the array to check if the element already exists, the performance is predictably not very good.
In either implementation, returning indices by value contains (e), indexOf (e), and remove (e) would require traversing all elements for comparison, and the performance would not be expected to be very good.
There is no SortedList sorted by element value.
Besides CopyOnWriteArrayList, there is no other thread-safe and concurrency optimized implementation such as ConcurrentLinkedList. Making do with the equivalence classes in Set and Queue lacks some list-specific methods such as get (I). If the update frequency is higher, or an array is larger, or use the Collections. SynchronizedList (list), and to all use the same thread lock to ensure safe operation.
2. Map
2.1 a HashMap
Hash bucket array with Entry[] array, using the hash value of Key to take the size of the module bucket array can get the array subscript.
If two keys fall into the same bucket when an element is inserted (e.g., hash 1 and 17 belong to the first hash bucket after mod 16), we call this hash collision.
The JDK uses a linked list approach, where entries are stored in a one-way linked list using a next attribute. To find a key with a Hash value of 17, locate the Hash bucket, and then the list iterates through all the elements in the bucket, comparing the Hash value and then the key value one by one.
In JDK8, there is a new threshold of 8 by default. When the number of entries in a bucket exceeds the threshold, it is stored in a red-black tree instead of a one-way list to speed up Key lookup.
Of course, it’s better to have only one element in the bucket and not have to compare. Therefore, by default, when the number of entries reaches 75% of the number of buckets and hash conflicts are serious, the bucket array is multiplied and all original entries are reassigned. Expansion costs aren’t cheap, so it’s best to have an estimate.
Modulo operations (hash & (arrayLength-1)) are faster, so the size of the array is always 2 to the N, and if you give an initial value such as 17 to 32. The default initial value when an element is first put in is 16.
Iterator () iterates through an array of hash buckets, which looks out of order.
2.2 LinkedHashMap Extends HashMap to add a bidirectionally linked list per Entry, which claims to be the most memory-intensive data structure.
Iterator () is supported to sort entries by insertion order (if the accessOrder attribute is true, all read and write access is sorted).
When inserting, the Entry adds itself to the front of the Header Entry. If all read and write accesses are sorted, and before/after entries are concatenated to remove themselves from the linked list, reads are not thread-safe.
2.3 TreeMap is realized by red-black tree, which is also called self-balanced binary tree:
For any node, each path to the leaf contains the same number of black nodes. The above rules keep the number of levels of the tree from falling too far apart, keeping all operations within order (LGN), but also keep insertion and modification complicated with left and right rotation to keep the tree balanced.
Sorting by Key when iterator () is supported, either by ascending order of keys that implement the Comparable interface, or by the incoming Comparator. As you can imagine, the cost of inserting/removing elements in a tree is higher than that of a HashMap.
Support SortedMap interface, such as firstKey (), lastKey () to obtain the maximum and minimum key, sub (fromKey, toKey), tailMap (fromKey) to cut a Map segment.
To pass in an enumeration class ina constructor, EnumMap builds an array equal to all the values of the enumeration and accesses the array with the subscript enum.ordinal (). Excellent performance and memory footprint.
However, since the Map interface is to be implemented, and the key in V GET (Object key) is Object instead of K, the type of key must be determined for EnumMap each time it is accessed, and the JMC will record a high sampling hit frequency.
2.5 ConcurrentHashMap Concurrent optimized HashMap.
The classic design in JDK5 has 16 write locks by default (more can be set), effectively spreading out the blocking probability. The data structure is Segment[], and each Segment has a lock. Segment is the hash bucket array. Key calculates which Segment it is in and then calculates which hash bucket it is in.
There is also no read lock, because the PUT /remove action is an atomic action (for example, the entire process of put is an assignment to an array element /Entry pointer), and the read does not see the intermediate state of an update action.
In JDK8, however, the Segment[] design is discarded in favor of elaborate locks that are only locked when needed.
Support the ConcurrentMap interface, such as putIfAbsent (key, value) and the opposite replace (key, value) and replace (key, oldValue, newValue) that implements CAS.
2.6 ConcurrentSkipListMap concurrency optimization SortedMap in JDK6, implemented in SkipList structure. It was chosen by the Concurrent package because it supports a CAS-based lock-free algorithm, whereas red-black trees do not have good lock-free algorithms.
In principle, it can be thought of as N floors of linked lists with elements ranging from sparse to dense, and each element has Pointers to the right and down. Start with the first floor, and if the value on the right is larger than expected, go down one floor and keep going.
Typical space for time. Each time you insert, you have to decide which layers to insert, and at the same time, you have to decide if you want to build another floor.
Its size () can also not be arbitrarily adjusted, will be traversed statistics.
3. Set
All sets are implemented internally with a Map, because the KeySet in a Map is a Set, and the value is a false value. All sets use the same Object.
Set characteristics also inherit those of the internal Map implementation.
HashSet: Inside is a HashMap.
LinkedHashSet: Inside is the LinkedHashMap.
TreeSet: Inside is the SortedSet of TreeMap.
ConcurrentSkipListSet: Inside is the ConcurrentSkipListMap’s concurrency optimized SortedSet.
CopyOnWriteArraySet: Inside is a concurrent optimized Set of CopyOnWriteArrayList, with the addIfAbsent () method for element de-duplication. As mentioned earlier, the performance of this method is mediocre.
There seems to be a ConcurrentHashSet missing. There should be a simple implementation of ConcurrentHashMap internally, but the JDK doesn’t provide it. Simple closed a Jetty is himself, Guava is directly in Java. Util. Collections. NewSetFromMap (new ConcurrentHashMap ()).
4. Queue
A Queue is a List that goes in and out at both ends, so you can use arrays or linked lists.
Yes, a LinkedList implemented as a two-way LinkedList is both a List and a Queue.
4.1.2 ArrayDeque A two-way Queue implemented as a circular array. The size is a multiple of 2. The default is 16.
To support FIFO, which means pushing elements from the end of the array (fast) and pulling elements from the header (super slow), you can no longer use a normal ArrayList implementation and use a circular array instead.
There are two subscripts for team head and team tail: when the element is popped, the team head subscript increases; When an element is added, the tail index increases. If the element is at the end of the array space, the element is assigned to array [0] with index 0 at the end, and the next element is assigned to array [1] with index 1 at the end. If the index at the end of the queue catches up with that at the head of the queue, the array space is used up.
4.1.3 PriorityQueue a PriorityQueue implemented by balanced binary minimum heap. Instead of FIFO, queues are drawn according to the Comparable interface implemented by the element or the comparison result passed in by the Comparator. The smaller the value, the higher the priority and the earlier the queue is drawn. Note, however, that the return from its iterator () is not sorted.
Balanced least binary heap, can be expressed in a simple array, can be addressed quickly, no Pointers and so on. The smallest children in queue[0], such as the two children in queue[4], will be in queue[24+1] and queue[2 (4+1)], i.e. Queue [9] and queue[10].
To join the queue, insert queue[size] and then compare the adjusting heap binary upwards.
To exit the queue, eject queue[0], and then take out the queque[size] to compare and adjust the heap dichotomously.
The initial size is 11, and the capacity is automatically expanded by 50% when the space is insufficient.
4.2 the thread safe Queue 2 ConcurrentLinkedQueue/Deque unbounded concurrent optimization of the Queue, based on the list, rely on the CAS lock-free algorithm is realized.
The structure of ConcurrentLinkedQueue is a unidirectional linked list and head/tail Pointers. Because the CAS action of changing the next pointer to the last element and changing the tail pointer to the new element cannot be atomic, a special algorithm is required.
BlockingQueue can block if the queue is empty without having to repeatedly check to see if there is new data, and queue length is limited to ensure that producers and consumers are not too far apart in speed. When the queue is full when joining or empty when leaving the queue, the effects of different functions are shown in the following table:
Add (e) offer (e) put (e) Offer (e, timeout, unit) Remove () poll () take () poll (timeout,) poll (timeout,) Unit) Check element () peek () None none
4.3.1 ArrayBlockingQueue Fixed length concurrent optimization BlockingQueue is also based on a circular array implementation. There is a common lock and two conditions, notFull and notEmpty, manage the blocking state when the queue is full or empty.
4.3.2 LinkedBlockingQueue/Deque can be chosen long concurrent optimization of BlockingQueue, based on the list, so you can set the length of the Integer. MAX_VALUE be unbounded without waiting for.
Using the characteristics of linked lists, 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, also based on array storage binary heap (see previous). A common lock implements thread safety. Because it is unbounded and automatically expands when space is insufficient, it will not be locked when the column is entered, but when the column is empty, it will be locked.
4.3.4 DelayQueue contains a PriorityQueue, which is also unbounded and locked only when the queue is unbounded. A common lock implements thread safety. The element needs to implement the Delayed interface, which returns each time it is called how long it is currently until it is triggered, with less than 0 indicating that it is triggered.
Pull () uses peek () to look at elements in the header to see if trigger time has been reached. ScheduledThreadPoolExecutor with a similar structure.
4.4 SynchronousQueue The SynchronousQueue itself has no capacity and when an element is put in, for example, it waits for the element to be fetched by another thread’s consumer before returning. Use it in the JDK thread pool.
JDK7 also has a LinkedTransferQueue, which adds a Transfer (e) function to the normal thread-safe BlockingQueue to act like SynchronousQueue.
The diagram above shows the members of the entire collection family and their relationships. The following is a brief introduction to the above various interfaces and base classes (mainly introduces the characteristics of each collection. Difference).
The following diagrams illustrate the relationship between interfaces of the composite class more clearly:
Map implementation class
Vii. Collection interface
The Collection interface is the most basic Collection interface. It does not provide a direct implementation. The Java SDK provides classes that inherit from the Collection “subinterfaces” such as List and Set. What a Collection represents is a rule that all the elements it contains must follow one or more rules. Some allow repetition and some cannot, some must be inserted sequentially and some hashes, some supports sorting and some does not.
In Java, all classes that implement the Collection interface must provide two standard sets of constructors, one that takes no arguments to create an empty Collection and one that takes arguments to create a new Collection. This new Collection has the same elements as the incoming Collection. // Implement basic add, delete, change and query methods, and need to be able to convert to an array type
Public class Collection interface {class Collection 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() {} @override public Object[] toArray(Object[] a) {return(new) Object[0]); }}}Copy the codeList interface
The List interface is the direct interface of Collection. What a List represents is an ordered Collection, that is, it maintains the order of elements with some particular insertion order. The user has precise control over the insertion position of each element in the list, and can access elements based on their integer index (position in the list) and search for elements in the list. List interface implementation of the main set of: ArrayList, LinkedList, Vector, Stack.
2.1, the ArrayList
ArrayList is a dynamic array, and the collection we use most often. It allows any element that conforms to the rule to be inserted, including NULL. Each ArrayList has an initial capacity (10) that represents the size of the array. As the number of elements in the container increases, so does the size of the container. A capacity check is performed each time an element is added to the container, and when overflow is imminent, capacity expansion is performed. Therefore, if we know how many elements to insert, it is better to specify an initial capacity value, so as to avoid wasting time and efficiency by too many expansion operations.
Size, isEmpty, get, set, iterator, and listIterator operations all run at a fixed time. The Add operation runs at apportioned fixed time, that is, it takes O(n) time to add n elements (it’s not just that adding elements has apportioned fixed time overhead because of capacity expansion).
Arraylists are good at random access. The ArrayList is also asynchronous.
2.2, LinkedList
LinkedList, which also implements the List interface, is different from ArrayList, which is a dynamic array, and LinkedList, which is a two-way LinkedList. So in addition to the basic operations of ArrayList, it also provides get, remove, insert methods at the beginning or end of LinkedList.
Because of the way it is implemented, LinkedList cannot be accessed randomly, and all operations are performed according to the requirements of a double LinkedList. The operation of an index in a list traverses the list from the beginning or end (from the end close to the specified index). The advantage of this is that you can insert and delete from the List at a lower cost.
Like ArrayList, LinkedList is asynchronous. If multiple threads access a List at the same time, they must implement access synchronization themselves. One solution is to construct a synchronization when creating a List of the List: a List List = Collections. SynchronizedList (new LinkedList (…). );
2.3 Vector is similar to ArrayList, except that Vector is synchronized. So Vector is a thread-safe dynamic array. It operates almost the same as ArrayList.
A Stack inherits from a Vector and implements a lifO Stack. Stack provides five additional methods that allow a Vector to be used as a Stack. The basic push and POP methods, as well as peek to get the element at the top of the stack, empty to see if the stack is empty, and search to see where an element is in the stack. The e Stack is empty after it is created.
The following is the inheritance of the List interface. Since the List interface specifies implementations such as index queries and iterators, classes that implement the List interface will have these methods. */ /* So both ArrayList and LinkedList can use array operations at the bottom, but there are generally no such external calls. */ /* * public interface Iterable<T> * public interface Collection<E> extends Iterable<E> * public interface List<E> extends Collection<E> */ 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() {} @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]); }}}Copy the code9. Set interface
A Set is a Collection that does not contain repeating elements. It maintains its own internal ordering, so random access doesn’t make any sense. Like List, it also runs the presence of NULL but only one. Due to the special nature of the Set interface, all elements passed into the Set must be different, and note that any mutable object that causes E1.equals (e2)==true when operating on elements in the Set is bound to cause some problems. Set interfaces include EnumSet, HashSet, and TreeSet.
3.1. EnumSet is a dedicated Set for enumeration. All elements are enumerated types.
A HashSet is the fastest collection to query because it is implemented internally in HashCode. The order of its internal elements is determined by the hash code, so it does not guarantee the iteration order of the set; In particular, it does not guarantee the constancy of the order.
Public class Set {/* Set specifies that a Set is treated as a Set, and is added, subtracted, modified, and looked up in the same way as an array. */ * Public interface Set<E> extends Collection<E> */ /* Public interface Collection<E> extends Iterable<E> */ /* public interface Iterable<T> */ 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]); }}}Copy the code10. Map interface
Unlike the List and Set interfaces, a Map is a Set of key-value pairs and provides the mapping between keys and values. It also does not inherit Collection. It ensures a one-to-one correspondence between keys and values in a Map. That is, a key corresponds to a value, so it cannot have the same key value, but of course the value can be the same. Map implementation includes HashMap, TreeMap, HashTable, Properties, and EnumMap.
4.1. HashMap is implemented in a hash table data structure. When an object is searched, its position is calculated by the hash function. Use a hash list to string together all elements of the same hash address, perhaps by looking at the source code for Hashmap.Entry, which is a single list structure.
4.2 TreeMap keys are sorted by some sort rules, and are internally implemented by red-black tree data structure, which implements SortedMap interface
4.3 HashTable is also implemented as a HashTable data structure, and the form of hash linked list is also used to resolve conflicts with HashMap, but the performance is lower than that of HashMap
Public class Map interface {/* The Map interface is the topmost interface. The Map interface implementation class must implement hash operations such as PUT and GET. */ /* Also provide query structures such as keySet and values, and entrySet. */ /* public interface Map<K,V > */ 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<Entry> entrySet() { return(null); }}}Copy the code11, the Queue
Queue, it is mainly divided into two categories, one is blocking queue, queue full after the insertion of elements will throw an exception, mainly including ArrayBlockQueue, PriorityBlockingQueue, LinkedBlockingQueue. The other type of queue is a double-ended queue, which supports the insertion and removal of elements at the head and tail, including ArrayDeque, LinkedBlockingDeque, LinkedList.
Public class Queue interface {/* Queue interface is an implementation of queues, need to provide Queue in Queue out Queue methods. */ 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); } /* 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); }}}Copy the codeXii. Summary
I believe you have mastered these Java collection class knowledge points. Point attention, don’t get lost, follow programmer Zeng Zeng, share different Java basics every day.