1. Inheritance

1.1 based on the Collection

Iterable interface: iterators (responsible for iterative element, used to traverse the element) Collection interface: Collection (all commonly used method is to add, add, delete, empty set, the existence of the Collection number, etc.) the List interface: List (list provides richer API than array, ordered, repeatable) Queue interface: Queue (follow the first-in-first-out principle, the first element in the Queue must be the first out of the Queue) Set interface: Set Set (do not allow duplicate elements, and unordered collection)

1.2 does not belong to Collection

Map interface: Hash tables (a data structure stored using K-V (key-value pairs), where keys are unordered and non-repeatable and values are unordered and repeatable) are not part of the Collection interface

2. The List

2.1 ArrayList

Underlying implementation: Objcet[] (dynamic array)

Expansion method: When the capacity of the underlying array of the original ArrayList is insufficient to store newly inserted elements or a group of elements, the expansion mechanism is triggered and the local C method is called.

Thread safety: no security supplement: if you want to secure call ArrayList, use Collections. SynchronizedList () method. The other apis are the same as before

List<Map<String,Object>> data=Collections.synchronizedList(new ArrayList<Map<String,Object>>());
Copy the code

Usage scenario: Suitable for a large number of random access (in human language, the value can be directly based on the subscript), time complexity O(1)

Insert and delete: append to tail by default, time complexity O(1). Append or delete elements at specified locations, time complexity O(n-i)

Add: The clear() method clears the current List without changing the allocated space

2.2 LinkedList

Underlying implementation: bidirectional linked list

Capacity expansion mode: Add a node to a normal linked list

Thread-safety: unsafe Addendum: If you want to call safely, ditto above. The other apis are the same as before

List<Map<String,Object>> data=Collections.synchronizedList(new LinkedList<Map<String,Object>>());
Copy the code

Usage scenario: Suitable for frequent insert or delete operations, less random access (in human language, the value can be directly based on the subscript), the time complexity of the element O(n).

Insert and delete: append to tail by default. The time complexity is O(1). Append or delete elements at a specified location, and the time complexity is approximately O(n).

Memory footprint: An ArrayList wastes space by reserving space at the end of the list. The space cost of LinkedList is mainly reflected in the fact that each element (storing direct descendants and direct precursors as well as data) consumes more space than ArrayList.

2.3 CopyOnWriteArrayList (not commonly used)

Underlying implementation: Objcet[] (dynamic array)

Thread safety: Security Supplement: How to ensure security, read: unlocked. Write: Add or modify the current element using lock() to lock and make a copy, then add or modify, then use the new copy.

Usage scenario: Suitable for a large number of random access (in human language, the value can be directly based on the subscript) and the situation of read and write, does not require strong consistency (instant consistency cannot be guaranteed), time complexity O(1).

Memory footprint: A copy is required for each write. Huge waste of memory.

2.4 Vector (Left over from history, classes from ancient times)

Underlying implementation: Objcet[] (dynamic array)

Thread safety: safety supplement: how to ensure safety, method all add synchronized keyword (stinky historical residue. Run away from the company that uses it, the code must be shit mountain)

The three.

3.1 HashSet

Underlying implementation: HashMap(using the Key part)

Thread safety: Not safe

Usage scenario: Unordered, data deduplication allows Null values to be inserted

3.2 the TreeSet

Underlying implementation: TreeMap, red-black tree (self-balanced binary search tree)

Thread safety: Not safe

Use scenario: Ordered (natural sort, the order of the first character of the key, or the size of the number 0-9) or custom sort, data deduplication allows the insertion of Null values

Note: It is safe to call a non-thread-safe Set. callCollections.synchronizedSet()

Map for four.

4.1 a HashMap

Underlying implementation: Hash table (also known as Hash table, using Hash algorithm), when the length of the linked list (Value storing the same Hash Value) is greater than the threshold (default is 8) (before converting the linked list to a red-black tree, it will judge that if the length of the current array is less than 64 (storing keys), it will choose to expand the array first instead of converting to a red-black tree), Transform linked lists into red-black trees to reduce search time.

Thread safety: Not safe

Capacity expansion mechanism: the source code specifies the default capacity expansion load factor of 0.75

Interviewer: Why 0.75? If the value is 0.5, it means that the capacity expansion begins when the hash table is half filled, which leads to frequent capacity expansion and low space utilization. If it is 1, it means that the hash table is completely full before it starts to expand, so even though space utilization is improved, the chance of hash conflicts is greater. Load factor 0.75 is the final embodiment of the balance between the chance of conflict and space utilization, and is also the empirical value of the experiment.

Static final float DEFAULT_LOAD_FACTOR = 0.75f;Copy the code

Usage scenario: Data needs to be stored according to the hashCode value of the key. Unordered, the time complexity of obtaining elements is limited to O(1). Key and Value can be null

Memory space usage:

(1) The default initialization size is 16. After each expansion, the capacity is doubled. Why is the interviewer 16? If it’s too small, 4 or 8, it expands more frequently; If it’s too big, 32 or 64 or even too big, it takes up memory. Bit operations are faster and do not require conversion between decimal and binary.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
Copy the code

(2) If a HashMap is created with an initial capacity value, it will be expanded to a power of 2, that is, a HashMap always uses a power of 2 as the size of the hash table.

Simple hashing algorithm demo: set to 7 film, add key: 6, value: “random”

7 = 6 6%

Add key: 7, value: “second”

7 = 0 7%

Resolving Hash conflicts: Zip (a linked list of values with the same Hash Value), or the red-black tree above. But the zipper method is simpler.

4.2 TreeMap

Underlying implementation: red black tree

Thread safety: Not safe

Use scenarios: ordered (natural sort, the order of the first character at the beginning of a key, or the size of a number 0-9) or custom sort. Key and Value can be null

Note: It is safe to call a non-thread-safe Map. callCollections.synchronizedMap()

4.3 ConcurrentHashMap (Recommended)

Array + linked list/red black binary tree (JDK1.8) convert linked list (O(N)) to red black tree (O(log(N)) when the length of linked list exceeds a certain threshold (8).

Thread safety: Safe

Thread-safe method: useNodeArray + linked list + red black tree data structure to achieve, concurrent control usingsynchronizedAnd CAS.

Efficiency problem: Synchronized only locks the first node of the current linked list or red-black binary tree. In this way, as long as hash does not conflict, concurrency will not occur and efficiency will be improved by N times.

4.4 Hashtabel (ancient thread-safe class)

How to ensure security, method all addedsynchronizedKeywords: Stench of history. Run away from the company that uses it, the code must be shit mountain)

Data reference

JavaGuide: snailclimb. Gitee. IO/JavaGuide CSDN:blog.csdn.net

contact

Official account: Qingshan Youlu Github: github.com/z875479694h Blog: www.hcworld.xyz