Container overview relationships
The List of
ArrayList
-
Features – Application scenarios
Lookup is fast, and non-tail inserts and deletes require moving elements that follow at insertion, so inserts are slow
Applicable to scenarios with frequent access and few non-tail modifications
-
Realize the principle of
An array of
Non-thread-safe
It is a continuous space. When the memory space is insufficient, the system proactively expands the capacity
Constructed with no arguments, the initial capacity is 0, and the capacity is 10 when the element is actually added
Dynamic capacity expansion: When the capacity of an element is used up, it is dynamically expanded to 1.5 times the current capacity
Array.copyof (elementData, newCapacity) is used for dynamic capacity expansion, which returns new Arrays, but the copy is a shallow copy, and the contents of the two Arrays all point to the same reference
Vector
-
Features – Application scenarios
Like ArrayList, and suitable for multithreaded access scenarios
-
Realize the principle of
An array of
Thread safety, safe use of synchronized entire array, so the lock range is wide, low concurrency efficiency
The no-parameter construct initializes capacity 10
It is a continuous space. When the memory space is insufficient, the system proactively expands the capacity
Dynamic expansion process: The increment size can be initialized. If the capacity is full, the current capacity plus the increment size is expanded. If the increment size is not transferred, the current capacity is expanded twice
Array.copyof (elementData, newCapacity) returns new Arrays, but the copy is a shallow copy, and the contents of the two Arrays all point to the same reference
LinkedList Is a two-way list
-
Features – Application Scenario Fast insert, delete, and search, suitable for a large number of inserts but little access
Delete directly modify the address value of the element record, do not need to move a lot of elements, so delete fast
-
Realize the principle of
The head node, the tail node, and the node data object LinkedList are discrete Spaces, so they do not need to be actively expanded
Single linked list structure features: The head node and the tail node data object data has a next reference
Bidirectional linked list: The header and tail data objects have pre and Next points to them
Circular list: the structure is single linked list, characterized by no head node, tail node points to the first node object
Self-building linked list objects are similar:
public class LinkList {
public Node root = null; // Define the head node, which is null by default
public Node tail; // Define the tail node
public int length; // Define the length of the list
public class Node{ // Declare the node class
public int data; // Define data objects
public Node next = null; // Define pointer, default is null
public Node(int data) {this.data = data; } // Overwrite the constructor to initialize the node
}
Copy the code
Stack
-
Features – Application scenarios
After the advanced
Thread safety
-
Realize the principle of
It inherits from Vector and has the characteristics and principles of vector
The Set of
Elements are stored and retrieved in unordered order
HashSet
-
Features – Application scenarios
Elements are stored and fetched in an unordered order. No corner markers can be used to precisely locate elements that are not allowed to be duplicated. Only one element is kept
-
Realize the principle of
Internally, hashMap is used to realize the storage of content. The key value is the object added and the value is the fixed object
public HashSet() {
105 map = new HashMap<>();
106 }
public boolean add(E e) {
219 return map.put(e, PRESENT)==null;
220 }
221
222 /** 223 * Removes the specified element from this set if it is present. 224 * More formally, removes an element <tt>e</tt> such that 225 * <tt>(o==null ? e==null : o.equals(e))</tt>, 226 * if this set contains such an element. Returns <tt>true</tt> if 227 * this set contained the element (or equivalently, if this set 228 * changed as a result of the call). (This set will not contain the 229 * element once the call returns.) 230 * 231 *@param o object to be removed from this set, if present
232 * @return <tt>true</tt> if the set contained the specified element
233 */
234 public boolean remove(Object o) {
235 return map.remove(o)==PRESENT;
236 }
Copy the code
TreeSet
-
Features – Application scenarios
The elements are sorted by Comparable and inserted into the TreeMap of the internal binary tree
The ability to sort elements according to some sort of rule.
Features: sort and unique
The underlying data structure is a red-black tree (red-black tree is a self-balanced binary tree), which ensures the ordering and uniqueness of elements
Internal implementation of sorting, you can also customize sorting rules
Natural sorting and comparator sorting guarantee element sorting
Element uniqueness is guaranteed based on whether the return value of the comparison is 0
-
Realize the principle of
Treemap is encapsulated internally, and the value object is a fixed object
3 public TreeSet() {
124 this(new TreeMap<E,Object> ());125 }
126
127 /**
128 * Constructs a new, empty tree set, sorted according to the specified
129 * comparator. All elements inserted into the set must be <i>mutually
130 * comparable</i> by the specified comparator: {@code comparator.compare(e1,
131 * e2)} must not throw a {@code ClassCastException} for any elements
132 * {@code e1} and {@code e2} in the set. If the user attempts to add
133 * an element to the set that violates this constraint, the
134 * {@code add} call will throw a {@code ClassCastException}.
135 *
136 * @param comparator the comparator that will be used to order this set.
137 * If {@code null}, the {@linkplain Comparable natural
138 * ordering} of the elements will be used.
139 */
140 public TreeSet(Comparator<? super E> comparator) {
141 this(new TreeMap<>(comparator));
142 }
143
Copy the code
The family of the map
HashTable
-
Features – Application scenarios
Multi-threaded Hashmap is usually replaced by ConcurrentHashMap lock segment concurrent containers due to its low efficiency
-
Realize the principle of
Array + linked list
Thread safety
Synchronized of a HashTable is for the entire Hash table, that is, the entire table is locked at a time for exclusive use by the thread, so locking is not efficient
HashMap
-
Features – Application scenarios
Is chaotic
Allow null values for keys and values
The load factor is 0.75, and the initial size is 16. Whether the storage capacity needs to be expanded depends on whether the current storage capacity has reached 3/4 of the capacity when adding elements. If so, the storage capacity needs to be expanded twice
The capacity value of a HashMap is 2 to the n
Container initial size 16, maximum capacity 2^30 (1 sign bit, up to 30 left, left calculation capacity, 0 to 31 bits,1 sign bit 0 to 30 bits)
-
Realize the principle of
Array + linked list (single linked list, next records the location of an element)
Non-thread-safe
The capacity must be 2^n because of hash calculation rules
Determine index using hash value:
If n is to the second power, the formula (n-1) &hash = hash % n is satisfied
Hash value generation method:
Hash is 32 bits, but the number of containers n is 2^4 4 to 30 bits. In order to get high bits involved, we use xor of high bits and Hashcode to get the hash value
static final int hash(Object key) {
int h;
return (key == null)?0 :(h = key.hashCode()) ^ (h >>> 16);
}
Copy the code
StringHashCode implements public inthashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
returnh; } There is a number here31Why do you choose31As a product factor, and it's not declared as a constant, right? There are two main reasons for this.31Is a moderate prime number that is one of the preferred primes to be used as a hashCode multiplier. (2),31Can be optimized by the JVM,31 * i = (i << 5) - I. Because shifts are faster and less efficient than multiplications.Copy the code
Source code to add elements to determine the timing
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
625 boolean evict) {
626 Node<K,V>[] tab; Node<K,V> p; int n, i;
// Check whether the capacity needs to be expanded
627 if ((tab = table) == null || (n = tab.length) == 0)
628 n = (tab = resize()).length;
// Then check whether hashcode index exists for this value, and newNode if not
629 if ((p = tab[i = (n - 1) & hash]) == null)
630 tab[i] = newNode(hash, key, value, null);
631 else {
632 Node<K,V> e; K k;
// If yes, the hash value and key value are the same
633 if (p.hash == hash &&
634((k = p.key) == key || (key ! =null && key.equals(k))))
635 e = p;
// If the hash value is the same, the TreeNode can be inserted
636 else if (p instanceof TreeNode)
637 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
638 else {
// Otherwise, generate nodes and insert them into the linked list under the array, i.e., same hash value but different key value
639 for (int binCount = 0; ; ++binCount) {
640 if ((e = p.next) == null) {
641 p.next = newNode(hash, key, value, null);
642 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
643 treeifyBin(tab, hash);
644 break;
645 }
646 if (e.hash == hash &&
647((k = e.key) == key || (key ! =null && key.equals(k))))
648 break;
649 p = e;
650 }
651 }
// In the case of the same key value, return the same object, but replace the old value with the new value
652 if(e ! =null) { // existing mapping for key
653 V oldValue = e.value;
654 if(! onlyIfAbsent || oldValue ==null)
655 e.value = value;
656 afterNodeAccess(e);
657 return oldValue;
658 }
659 }
660 ++modCount;
661 if (++size > threshold)
662 resize();
663 afterNodeInsertion(evict);
664 return null;
665 }
Copy the code
TreeMap
-
Features – Application scenarios
A collection of maps that can be sorted by COMPARABLE
Out-of-order, no repetition allowed (out-of-order means that the order of elements is not the same as the order of additions)
The TreeMap collection sorts keys by default, so keys must implement either natural or custom sorting
The underlying data structure used is a binary tree
-
Realize the principle of
An internal element is structured in the form of a key value, such as an entry, and an entry has left and right elements. The left or right node is inserted according to the Comparable comparison
You can accept incoming SortedMap objects or comparator interface objects for comparison sorting
Usage:
Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
public int compare(Student p1, Student p2) {
return p1.score > p2.score ? -1 : 1; }}); map.put(new Student("Tom".77), 1);
map.put(new Student("Bob".66), 2);
map.put(new Student("Lily".99), 3);
for (Student key : map.keySet()) {
System.out.println(key);
}
Copy the code
LinkedHashMap
-
Features – Application scenarios
Inherits from hashMap, has the characteristics of HashMap, and sorts the elements in the order in which they are added
-
Realize the principle of
HashMap+ bidirectional linked list
Initialize the capacity and load factor (default: 0.75). AccessOrder specifies whether the entries are sorted by accessOrder. If so, the accessed entries are sorted to the last. The default value is false, that is, the entries are sorted by input order
AccessOrder is false by default. Get does not change the order. Put determines the order
The array corresponding to hashMap is changed to the following objects:
static class Entry<K.V> extends HashMap.Node<K.V> {
193 Entry<K,V> before, after;
194 Entry(int hash, K key, V value, Node<K,V> next) {
195 super(hash, key, value, next);
196 }
197 }
/** 202 * The head (eldest) of the doubly linked list. 203 */
204 transient LinkedHashMap.Entry<K,V> head;
205
206 /** 207 * The tail (youngest) of the doubly linked list. 208 */
209 transient LinkedHashMap.Entry<K,V> tail;
Copy the code
Use the add, delete, and access hook methods in the HashMap to create a before-and-after reference for each new element added to the array
void afterNodeAccess(Node<K,V> p){}1767 void afterNodeInsertion(boolean evict){}1768 void afterNodeRemoval(Node<K,V> p){}Copy the code
Each time the newNode method is used, use linkedhashmap.entry:
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
257 new LinkedHashMap.Entry<K,V>(hash, key, value, e);
static class Entry<K.V> extends HashMap.Node<K.V> {
193 Entry<K,V> before, after;
194 Entry(int hash, K key, V value, Node<K,V> next) {
195 super(hash, key, value, next);
196 }
197 }
Copy the code
ConcurrentHashMap
-
Features – Application scenarios
Hashmap features, and multithreaded safety, using lock fragmentation technology
-
Realize the principle of
(1)
In JDK1.7, ConcurrentHashMap uses the segment lock, which is inherited from the ReentrantLock. Once initialized, it cannot be changed, but the HashEntry array in the segment array can be changed
The structure is segment lock array + Hashentry array + linked list data
Locating an element requires two Hash operations.
The first Hash goes to the Segment, and the second Hash goes to the head of the list that the element is in
Segment Meaning Array of segments, segment structure – HashEntry array, each hashentry is a linked list structure
The segment structure inherits from ReentrantLock
A ConcurrentHashMap contains an array of segments. The Segment structure is similar to that of a HashMap.
A Segment contains an array of hashentries. Each HashEntry is an element of a linked list.
Each Segment contains an element in the HashEntry array. When modifying the HashEntry array, the Segment lock must be obtained.
(2) The ConcurrentHashMap in JDK1.8 discards the segment lock and uses array elements directly. Each element in the array can be used as a lock.
When there is no value in the element, the CAS operation can be used directly to set the value, while ensuring concurrency safety.
If the element already contains a value, use the synchronized keyword to lock the element and then hash the conflict
Key: Synchronized locks the linked list objects according to the operation, to ensure that the same object in the same lock operation
LruCache
-
Features – Application scenarios
The LinkedHashMap is encapsulated internally
-
Realize the principle of
When the sequence reaches the set memory limit, the least recently used element in the sequence is discarded
// Initial capacity 0, expansion coefficient),0.75, sort by true means get access sort, false means put insert sort
this.maxSize = maxSize; Initialize the maximum incoming capacity sizethis.map = new LinkedHashMap<K, V>(0.0.75f, true);
Copy the code
The Queue Queue
-
Features – Application scenarios
A fifO queue is a restricted data structure in which an insert can only be performed from one end, called the tail of the queue. Removal can only be done from the other end, called the head of the queue
-
Realize the principle of
Queues can be implemented in two ways: arrays and linked lists
Refer to the link
Array:
www.cnblogs.com/kuoAT/p/677… Blog.csdn.net/dietime1943… Blog.csdn.net/qq_42592994…
set
Blog.csdn.net/Piconjo/art…
zhuanlan.zhihu.com/p/105958354
map
Blog.csdn.net/hm_135/arti… Cloud.tencent.com/developer/a… Blog.csdn.net/baidu_37107… www.liaoxuefeng.com/wiki/125259… www.jianshu.com/p/181df0893… Blog.csdn.net/wxgxgp/arti… Lock block www.infoq.cn/article/Con…
Blog.csdn.net/LO_YUN/arti…
www.cnblogs.com/jelly12345/…
queue
Data.biancheng.net/view/109.ht…
Cs.xieyonghui.com/java/java-q…