Part of the review points about Java collections

ArrayList

  1. ArrayList essentially inherits from AbstractList, which in turn inherits from the Collection class, and ArrayList is the interface that implements List
  2. The initial capacity of the arrayList, DEFAULT_CAPACITY = 10, is 10, but the maximum capacity you can pass in to initialize the object is Interger.MaxValue-8
  3. The default element store for an ArrayList is an Object[] array
  4. There is an EnsureCapacity method in the source code of ArrayList, which is used to confirm whether the size of an array needs to be expanded. When expanding, we use the method of CopyOf of Arrays, which copies the elements into a new array
  5. As for the expansion mechanism of ArrayList, when the defined capacity is reached (if no capacity is passed in, it is the default capacity), the capacity will be dynamically expanded by 1.5 times, also using the above copy method
  6. ArrayList has a method called trimToSize() in the source code, which is called manually
  7. ArrayList’s Remove method uses arrayCopy () to move elements around, much like an array
  8. ArrayList is thread-unsafe. There is no guarantee of thread-safety in the ArrayList. Automated expansion of multiple threads is also part of the reason for thread-unsafe. In contrast, the common Vector is essentially thread-safe with synchronized

HashMap

  • HashMap implements the Map interface with an initial capacity of 16, a maximum capacity of 1 << 30, and a default load factor of 0.75. If you pass in an initial value of K, then the capacity is an integer greater than K to the second power. For example, if you pass in 10, then the capacity is 16

  • The insertion principle of HashMap

  • Prior to JDK1.8, HashMap was implemented as an array + linked list, which handles conflicts using a linked list, where nodes with the same hash value are stored in a linked list. However, when there are more elements in a bucket, that is, there are more elements with the same hash value, the sequential search by key value is less efficient. In JDK1.8, HashMap is implemented by array + linked list + red-black tree. When the length of the linked list exceeds the threshold value (8), the list will be converted into a red-black tree, which greatly reduces the search time. The threshold value of red-black tree to linked list is 6

    • The hash function takes the hashCode of the key and makes the high 16 bits of the hashCode and the low 16 bits of the hashCode perform the XOR operation. The reason for this design is to minimize hash collisions as much as possible. The second reason is that the bit operation is efficient

  • HashMap is not safe in multithreaded situations. Prior to JDK8, HashMap is inserted first and then inserted to determine whether the array needs to be expanded, which is twice the size of the original array

    • When expanding the capacity, 1.7 needs to re-hash the elements in the original array and locate them in the position of the new array. 1.8 adopts simpler judgment logic: position invariable or index + old capacity size
    • The conversion of the linked list to the red-black tree is not carried out when the threshold of 8 nodes is reached, but to judge whether the number of nodes in the whole data structure is greater than 64. If the number is greater than 64, the conversion will be carried out. If the number is less than 64, the conversion of red-black tree will be replaced by an expanded array

extension

In Java HashTable, Collections. SynchronizedMap and ConcurrentHashMap can achieve thread-safety Map.

  1. Hashtable directly adds the synchronized keyword to the operation method and locks the entire array with relatively large granularity.
  2. Collections.synchronizedmap set of tools is the use of the Collections within class, by passing in the Map to encapsulate a synchronizedMap object, internal object defines a lock, by object lock inside method;
  3. ConcurrentHashMap uses segmenting locking, which reduces locking granularity and improves concurrency.