start

This article mainly records the data structures commonly used in common development, and will briefly explain the advantages, disadvantages, characteristics and so on of each data structure.

The JDK provides a major Set of data structure implementations, such as List, Map, Set, Queue, and other commonly used data structures. All of this data inherits from the java.util.Collection interface and resides in the java.util package.

List

  • ArrayList

    • Based on the dynamic array set, you can dynamically add and delete elements, dynamically expand the capacity, etc. The default initial capacity is 10, and the capacity will be expanded to:int newCapacity = oldCapacity + (oldCapacity >> 1);That’s 1.5 times the original capacity.

    • Advantages: Fast index by index (O(1)). Disadvantages: Slow insertion and deletion (O(n)).
    • An ArrayList of capacity 10.
    • After capacity expansion by 1.5 times
    • ArrayList expansion source code
    /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
} 
Copy the code

  • LinkedList

    • A list based collection is a bidirectional list. There is no initialization or expansion mechanism. Nodes are added in front or behind the list all the time.
    • Advantages: Easy access by changing the head and tail node pointing (O(1)). Disadvantages: slow indexing, traversal of the beginning node to the last node in extreme cases (O(n)).
    • One-way linked list: Each node points only to the next node
    • Bidirectional linked lists: Each node holds the previous and the next node


  • Vector

    • Synchronized, a collection of array-based methods that manipulate data, can be seen as a synchronized, thread-safe version of ArrayList
    • Advantages: Thread-safe. Disadvantages: Synchronization inevitably leads to slow efficiency.

  • summary

    • The above sets all belong to linear data structures, which are also ordered, and the elements are associated with each other.
    • Array-based: Allocated memory is a tidy chunk of memory with all data next to each other. Array does not belong to linear structure.
    • List-based: although not contiguous in memory, each node retains a reference to the next node.

Map

A Map is a collection of key objects and value objects mapped together. Each element contains a pair of key and value objects. Map does not inherit from the Collection interface.

  • HashMap

    • The underlying structure of HashMap is array + list (JDk1.8 is array + list/red-black tree).
    • Initial capacity
        /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
Copy the code
    • Load factor: 0.75 is said to be a more suitable number in time and space, too high hash collisions, too low waste of space
    /**
 * The load factor used when none specified in constructor.
 */
static final floatDEFAULT_LOAD_FACTOR = 0.75 f;Copy the code
    • The threshold value
        /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    int threshold;
Copy the code
    • Capacity expansion mechanism:

      当size > (capacity * load factor)Triggers capacity expansion(newCap = oldCap << 1). The source coderesize()The method is a little long, so I won’t paste it here.
    • When to convert a red-black tree:
    If (binCount >= treeIFy_threshthreshold -1) // -1 for 1st treeifyBin(TAB, hash); break; Final void treeifyBin(Node<K,V>[] TAB, int hash) {int n, index; final void treeifyBin(Node<K,V>[] TAB, int hash) {int n, index; Node<K,V> e; / / if less than 64 will continue to increase the if (TAB = = null | | (n = TAB. Length) < MIN_TREEIFY_CAPACITY) the resize (); else if ((e = tab[index = (n - 1) & hash]) ! = null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) ! = null); if ((tab[index] = hd) ! = null) hd.treeify(tab); }}Copy the code
    • When to degenerate into linked lists:

      When the length is less than 6, it will degenerate into a linked list (if it is less than 8, it will be converted into a linked list, and the linked list and red-black tree may be repeatedly converted)removeTreeNode()andsplit()Methods all trigger judgment logic.
    • HashMap linked list red-black tree conversion process

  • HashTable

    This is a thread-safe version of HashMap, with the synchronized keyword added to the inner methods, just as Vector and ArrayList do.

    public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Java.io.Serializable {public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f); }}Copy the code
    • Disadvantages: because of adoptionsynchronizedWith synchronization guaranteed, the entire map is locked each time, so the performance of high-concurrency threads competing for the same lock deteriorates dramatically.

  • TreeMap

    NavigableMap

    implements NavigableMap

    and SortedMap

    . The SortedMap interface has a Comparator
    comparator(); Comparator, so TreeMap supports comparison sorting.
    ,v>
    ,v>
    ,v>

    public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable { public TreeMap(Comparator<? This.parator = this.comparator; this.parator = this.comparator; } static final class Entry<K,V> implements Map.Entry<K,V> {// static final class Entry<K,V> implements Map. V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; /** * Make a new cell with given key, value, and parent, and with * {@code null} child links, and BLACK color. */ Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; }}}Copy the code
    • The structure of the TreeMap
    • Features: Red black tree implementation, is an ordered map.

  • ConcurrentHashMap

    Different from HashTable, ConcurrentHashMap adopts the idea of segmental locking, abandoning the synchronized modification operation method.

    • Segmental locking idea:

      We all know that HashTable is inefficient because there is only one lock for the entire container, and multiple threads are fighting for the same lock. ConcurrentHashMap Segmented locking is used to divide data into individual piecesSegment<K,V>, and each Segment inheritsReentrantLockEach Lock locks different data segments. When a thread accesses one segment, the other segments can be accessed by other threads.
    static class Segment<K,V> extends ReentrantLock implements Serializable { private static final long serialVersionUID = 2249069246763182397L; final float loadFactor; Segment(float lf) { this.loadFactor = lf; }}Copy the code
    • Differences between 1.7 and 1.8:

      1. Since the underlying HashMap, so 1.8 is also an array + linked list/red-black tree.

      2. After 1.8, segmented locking was abandoned and adoptedsynchronized+CASTo ensure concurrency.

    • 1.8 Why Segmented Locking is Abandoned:

      1. I think it’s mainly 1.8 pairssynchronizedOptimized (biased lock, lightweight lock, spin lock, self-appropriate spin) 2. Adding multiple segmental locks wastes memory space. 3. In the production environment, the probability of a map competing for the same lock is very small.

Set

  • HashSet

    The HashSet is based on the HashMap. The key of the Map cannot be repeated to achieve the element uniqueness of the Set

    public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { private transient HashMap<E,Object> map; // Dummy value to associate with an Objectinthe backing Map private static final Object PRESENT = new Object(); public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); Public Boolean add(E E) {public Boolean add(E E) {public Boolean add(E E) {public Boolean add(E E) {returnmap.put(e, PRESENT)==null; }}Copy the code

  • LinkedHashSet

    The LinkedHashSet is based on the implementation of LinkedHashMap, inherited from HashSet, which can be seen as an ordered Set (can be customized like LinkedHashMap)

        public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
        public LinkedHashSet() {
            super(16, .75f, true);
        }
        
        public LinkedHashSet(Collection<? extends E> c) {
            super(Math.max(2*c.size(), 11), .75f, true); addAll(c); }}Copy the code

Stack

todo
Copy the code

Queue

todo
Copy the code

conclusion

The whole article introduces a variety of data structures in a relatively simple way, but also points out the characteristics and advantages of each structure. The pictures in the article are searched on the Internet (avoid repeating the wheel).