preface

I’m sure you all use ArrayList, LinkedList, HashMap, ConcurrentHashMap, HashSet, TreeSet, Queue, etc., and NIU. But do you know what the main properties are? What is the data structure? What are the characteristics? Usage scenarios? The underlying implementation principle and so on, if you do not understand, please come over, Lao Niu take you step by step to unlock the clothes of Java collection, see their real body, Let’s go!

List interface and interface implementation classes

Ordered and not unique

ArrayList

  • The interior is implemented through arrays, allowing fast random access to elements.
  • When the size of the array is insufficient and the storage capacity needs to be increased, the data that already has the array needs to be copied to the new storage space.
  • Suitable for random lookup and traversal, not insertion and deletion. When inserting or deleting elements from the middle of an ArrayList, the array needs to be copied, moved, and expensive.

LinkedList

  • LinkedList stores data in a LinkedList structure.
  • Very suitable for dynamic data insertion and deletion, random access and traversal speed is relatively slow.
  • There are methods not defined in the List interface that operate on table header and table tail elements and can be used as stacks, queues, and bidirectional queues.

Vector (thread-safe)

  • Through arrays.
  • By default, Vector doubles its capacity each time it expands.
  • Thread synchronization is supported, so that only one thread can write Vector at a time, avoiding the inconsistencies caused by multiple threads writing simultaneously, but synchronization is expensive and therefore slower to access than ArrayList.

CopyOnWriteArrayList

  • Write operations are performed on a copied array, and read operations are performed on the original array. Read and write operations are separated from each other.
  • Write operations must be locked to prevent data loss in concurrent write operations.
  • After the write operation, you need to point the original array to the new copy array.
  • Read operations can be performed at the same time as write operations, which greatly improves read operation performance. Therefore, it is suitable for the application scenario where read operations are excessive and write operations are insufficient.
  • Memory footprint: A new array needs to be copied at write time, doubling the memory footprint.
  • Data inconsistency: Read operations cannot read real-time data because part of the write operation’s data has not been synchronized to the reading group.

Set interface and interface implementation classes

Disordered and unrepeatable

HashSet

  • The edge of a hash table holds hash values.
  • The HashSet class implements a Set, which is actually an instance of a HashMap.
  • A HashSet does not store elements in the order in which they were stored. I’m going to hash it so I’m going to hash it out. The hash value of an element is obtained using the element’s HashCode method. The HashSet first evaluates the hash value of two elements. If the hash value is the same (hash collision, also called hash collision), it then compares equals if the equls result is true. A HashSet is treated as the same element. If equals is false, it is not the same element. A HashSet uses a hashCode value to determine the location of an element in memory. A hashCode location can hold multiple elements.

LinkedHashSet

  • A set object that is guaranteed to be stored as it is retrieved.
  • LinkedHashSet is a combination of hash and linked list, and is a two-way linked list.
  • The LinkedHashSet underlying layer uses the LinkedHashMap to hold all elements.
  • Inherits from HashSet, and all of its methods are operationally identical to HashSet.

TreeSet

  • TreeSet uses the binary tree principle to sort newly added objects in ascending or descending order. Each new object is sorted and inserted to the specified position in the binary tree.
  • The default TreeSet ordering is available for both Integer and String objects. Objects of custom classes are not. Self-defined classes must implement the Comparable interface and override the corresponding compareTo() function to be usable.
  • When you overwrite compare(), you need to return the corresponding value to make TreeSet sort according to certain rules.
  • Compares the order of this object with the specified object. If the object is less than, equal to, or greater than the specified object, a negative integer, zero, or positive integer is returned, respectively.

Map interfaces and interface implementation classes

There can be no duplicate keys, and each key can map to at most one value

LinkedHashMap

  • The iteration order can be the insertion order.
  • Both Key and Value are allowed to be empty. Duplicate keys are overwritten and duplicate values are allowed.
  • LinkedHashMap is a subclass of HashMap that holds the insertion order of records Iterator over.
  • When LinkedHashMap, the records obtained first must be inserted first, or can be constructed with parameters and sorted by access order.

HashMap

  • A HashMap stores data based on the hashCode value of a key, and in most cases its value can be located directly, thus providing fast access, but the traversal order is uncertain.
  • A HashMap allows at most one record to have a null key and multiple records to have a NULL value.
  • A HashMap is not thread-safe, meaning that more than one thread can write a HashMap at any one time, which can lead to data inconsistencies.
  • If thread-safe is desired, the Collections synchronizedMap method can be used to make HashMap thread-safe, or ConcurrentHashMap can be used.

TreeMap

  • TreeMap implements the SortedMap interface, which sorts the records it holds by key. By default, the keys are sorted in ascending order. You can also specify a comparator for sorting. If sorted mappings are used, TreeMap is recommended.
  • Key must implement the Comparable interface or in constructing TreeMap incoming custom Comparator, otherwise it will throw at runtime Java lang. ClassCastException type of exception.

Hashtable (Thread-safe)

  • Hashtable is a legacy class, and many maps have common functionality similar to HashMap.
  • From the Dictionary class.
  • Is thread-safe, and only one thread can write a Hashtable at any time.
  • Concurrency is not as good as ConcurrentHashMap because ConcurrentHashMap introduces segmented locking. The use of Hashtable is not recommended in new code, and can be replaced with HashMap in cases where thread safety is not required, and ConcurrentHashMap in cases where thread safety is required.

ConcurrentHashMap Thread safe (Segment inheritance ReentrantLock)

  • ConcurrentHashMap and HashMap have similar ideas.
  • Supports concurrent operations.
  • The entire ConcurrentHashMap consists of segments that stand for “part” or “Segment”, and are often described as segmented locks. Notice how many places I used “slots” to represent a segment.

Thread-safe handling methods

//Collections.synchronized***()

List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);

Map<String,String> map = new HashMap<>();
Map<String,String> synMap = Collections.synchronizedMap(map);

Set<String> set = new HashSet<>();
Set<String> synset = Collections.synchronizedSet(set);
12345678910
Copy the code

The difference between ArrayList, LinkedList, and Vector

  • ArrayList: You can think of an array that grows automatically.
  • The underlying implementation of ArrayList is Array, an Array expansion implementation.
  • ArrayList is fast by index, but is as fast by value as LinkList.
  • ArrayList threads are insecure and efficient.
  • LinkList is a double-linked list that performs better than ArrayList when adding and removing elements.
  • LinkList threads are insecure and efficient.
  • The underlying data structure of a Vector is an array, which is fast to query but slow to add and delete.
  • Vector is thread-safe and inefficient.

Difference between HashMap and HashTable

  • The thread-safe ConcurrentHashMap is also thread-safe, but is many times more efficient than Hashtable because HashMap is thread-safe. Because ConcurrentHashMap uses segmental locking, the entire data is not locked.
  • HashMap: The key can be null, but there can only be one key, because the uniqueness of the key must be guaranteed.
  • Hashtable is thread-safe and has the synchronized keyword on every method.
  • Hashtable: Neither key nor value can be null.

List, Set, and Map

  • List: ordered, not unique.
  • Set: unordered and unique.
  • Map: cannot contain duplicate keys, each key can Map to at most one value, element storage order is unordered, and data is stored in key-value pairs.

Xiaobian share content is over here!

Xiaobian here sorted out some Java core technology knowledge points collection information

Public account: Kylin bug