1. How does ArrayList keep threads safe?

/ / the answer:
// Method 1:
SynchronizedList adds the synchronized lock to the set add remove method of the collection
List<Object> list = Collections.synchronizedList(new ArrayList<>());

// Method 2:
// Use thread-safe CopyOnWriteArrayList, which also locks increment, subtraction, and modification methods: final ReentrantLock lock = this.lock;

// Method 3:
// Create a wrapper class that inherits ArrayList and controls the add Set remove method according to the business
Copy the code

2. Initial capacity and expansion of Vector and ArrayList?

  • They both have an initial capacity of 0, that is, 0 when the null parameter constructor is invoked, with the initial capacity value 10 attached to the first addition of element data
  • When the Vector is expanded, if capacityIncrement is not specified or the value is not greater than 0, the capacityIncrement is doubled each time. Otherwise, the capacityIncrement is capacityIncrement
  • ArrayList expands by 1.5 times each time

3. Do I need to expand CopyOnWriteArrayList to add new elements? How is it done?

  • CopyOnWriteArrayList is not a dynamically expanded array and cannot be dynamically expanded. Its thread safety is guaranteed by adding a ReentrantLock
  • When adding elements to CopyOnWriteArrayList, the thread acquirement the lock, the add method creates a new array of capacity (old array capacity +1), copies the old array data to that array, and places the new data at the end of the new array

The code is as follows:

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally{ lock.unlock(); }}Copy the code

CopyOnWriteArrayList works for reading too much and writing too little! Because each call to a method that changes the array structure requires a new array, performance is low!

4. What is the difference between HashMap and HashTable?

HashMap

  • HashMap: The underlying HashMap is based on an array + a linked list + a red-black tree. It is not thread-safe and has a default capacity of 16, allowing empty keys and values
  • The initialsizeIs 16. Capacity expansion:newsize = oldsize << 1.Size must be 2 to the NTH power
  • When the total number of elements in the Map exceeds that of the Entry array75%In order to reduce the length of the linked list, element allocation is calculated more evenlyindexMethods:Index = hash & (tab.length - 1)
  • Each time the Map is expanded, the elements in the original array are recalculated and inserted again

HashTable

  • HashTable: the underlyingArray + linked listImplementation, neither key nor value can benull.Thread safetyTo achieve thread-safety, lock (synchroizedConcurrentHashMap optimizes the entire HashTable
  • The initialsizeIs 11. Capacity expansion:(tab.length << 1) + 1
  • To calculateindexMethod:index = (hash & 0x7FFFFFFF) % tab.length

The difference between

  • HashMap is not thread-safe, HashTable is thread-safe
  • A HashMap allows NULL as an entry key or value, whereas a Hashtable does not
  • HashMap contains containsValue and containsKey. Because the CONTAINS method is misleading
  • Hashtable inherits from the Dictionary class, and HashMap is an implementation class of the Map interface

Select index bucket from HashMap and HashTable

  • A HashMap:Index = hash & (tab.length - 1)
  • HashTable:index = (hash & 0x7FFFFFFF) % tab.length

Both formulas for bucket index are designed to make the bucket index obtained by each calculation more scattered, which can reduce hash conflicts.

HashTable:

  • 0x7FFFFFFF 是0111 1111 1111 1111 1111 1111 1111 1111 1111 1111: all 1’s except the sign bit
  • (hash & 0x7FFFFFFF)The result will be a positive integer
  • (hash & 0x7FFFFFFF) % tab.lengthThe index result is always a positive integer and ensures that the value of index is intab.lengthWithin the scope of!
  • If the array length of a HashTable is odd, fewer hash collisions will occur. If the array length of a HashTable is even, more hash collisions will occur. Therefore, the initial capacity is 11 and the expansion isnewsize = olesize << 1+1, ensure that each expansion result is an odd number

HashMap:

  • The initial capacity is 16. When the number of valid data reaches 0.75 times of the array capacity, capacity expansion is triggered
  • Bucket level calculation formula:Index = hash & (tab.length - 1)When calculating bucket index, the capacity must be 2 to the NTH power, that is, an even number. In this way, to reduce hash conflicts, expand:newsize = oldsize << 1And you get even numbers
  • In addition, when the list length in the bucket is larger than 8 and the array length reaches 64, the list is tree-like, and when the list length is smaller than 6, the list is anti-tree-like
  • The header interpolation method used in the pre-hashMap of JDK1.8 has the advantage of being more efficient than the tail interpolation method because it does not need to traverse the list once before inserting data
  • In JDK1.8, we use tail interpolation to determine whether the length of the list is greater than 8
  • HashMap resolves hash conflicts using the linked list method
  • HashMap inserts data first and then determines whether the repository is needed!

5. What is the difference between HashMap and TreeMap?

  • HashMap was introduced above, so let’s go straight to TreeMap
  • TreeMap is based on the balanced binary tree (red-black tree), which can customize the sorting rules. To implement the Comparator interface, it can easily implement various sorts of internal elements, but the performance is worse than that of HashMap

6. Relationship between Set and Map

  • The core of both is to store a set of unique objects without repeating elements
  • Each implementation of a Set is an encapsulation of the corresponding Map
  • For example, the HashSet underlying layer encapsulates the HashMap, and the TreeSet underlying layer encapsulates the TreeMap

7. What is the sort of plugin Map?

  • LinkedHashMap, sorted by element addition order (can also be set to sorted by access order)
  • TreeMap, you can sort by nature or by customTreeMap(Comparetor c)

8. Why did the underlying HashMap choose a red-black tree over another tree, such as a binary lookup tree? Why did it not start with a red-black tree, but only tree when the list length reached 8 and the array capacity was greater than 64?

  • Binary search tree will also become a linear structure in special cases, which has the same depth traversal problem as the original long list and slow search performance, such as:

  • The main purpose of using red-black tree is to improve the speed of data search. Red-black tree is a balanced binary tree. After inserting new data, it will maintain balance through left-rotation, right-rotation, color change and other operations to solve the problem of the depth of single-linked list query
  • The reason why a red-black tree is not used at the beginning is that traversing a linear linked list consumes less resources than traversing a red-black tree when the number of data in the list is small (because of a small amount of data, the red-black tree itself selects and changes color to maintain balance also need to consume resources), so the linear table is used in the early stage
  • The reason for using 8 as the tree threshold is that after extensive testing, 8 is the most appropriate value