Container overview relationships

The List of

ArrayList

  1. 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

  2. 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

  1. Features – Application scenarios

    Like ArrayList, and suitable for multithreaded access scenarios

  2. 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

  1. 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

  2. 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

  1. Features – Application scenarios

    After the advanced

    Thread safety

  2. 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

  1. 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

  1. 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&nbsp; ? &nbsp; e==null&nbsp; :&nbsp; 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

  1. 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

  2. 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

  1. Features – Application scenarios

    Multi-threaded Hashmap is usually replaced by ConcurrentHashMap lock segment concurrent containers due to its low efficiency

  2. 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

  1. 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)

  1. 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

  1. 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

  2. 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

  1. Features – Application scenarios

    Inherits from hashMap, has the characteristics of HashMap, and sorts the elements in the order in which they are added

  2. 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

  1. Features – Application scenarios

    Hashmap features, and multithreaded safety, using lock fragmentation technology

  2. 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

  1. Features – Application scenarios

    The LinkedHashMap is encapsulated internally

  2. 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

  1. 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

  2. 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…