Java collections have large trunks ————Collection and Map

1. The Collection interface

• List interface [ordered, repeatable]
  • LinkedList class –> two-way LinkedList
  • ArrayList class –> Array
  • Vector (similar to ArrayList, but slower and less used) –> arrays
  • Stack class –> inherit Vector class
• Set interface [unique]
  • The underlying data structure of the HashSet class ==> is the hash table ==, a generic collection of stored data that relies on HashMap implementation
  • LinkedHashSet == the underlying data structures are linked lists (guaranteed order) and hash tables (guaranteed uniqueness) == “guaranteed ordered collections (first-in, first-out) –> inherit from the HashSet class
  • TreeSet class ==> the underlying data structure is a red-black tree == for sorting –> relies on TreeMap implementation
• The Queue interface
  • LinkedList class == first in, first out

2. Map interface [No duplicate Key]

• HashTable class [unordered]
• A HashMap class“Disorderly”
  • Elements in a HashMap are iterated by starting at the beginning of the array, traversing all the elements under the current bucket, then moving to the next bucket, then jumping to the next bucket if there is no space between the buckets until all the elements are iterated. Obviously, elements are not inserted in this order, hence the HashMap is unordered.
• LinkedHashMap class
  • LinkedHashMap inherits the HashMap, but maintains an additional two-way list that records the order of insertion. The order in which elements are traversed is the order from front to back of the list, and therefore ordered.
• TreeMap class“Orderly”
  • The underlying data structure of TreeMap is a red-black tree, in which elements are ordered.
• Compare HashMap and HashSet
  • The main reason for the difference in retrieval speed is that a HashMap evaluates the hash code of a key (which is typically just a number or string) much faster than a HashSet evaluates the hash code of an entire object
  • The underlying HashSet uses a HashMap container

• TreeMap versus TreeSet

  • The TreeSet layer uses the TreeMap container

• Organize in a unified way

  • Note: Before JDK1.8, the hash table is implemented using array + linked list storage, and the linked list is used to deal with conflicts. Linked lists with the same hash value are stored in a linked list. However, when there are many elements in a bucket, it is inefficient to retrieve the linked list by key. When the length of the linked list exceeds the threshold (8), the linked list is transformed into a red-black tree to improve efficiency
  • Hash table array + linked list structure

  

  • Hash table array + linked list + red-black tree structure

  

• Contrast of sets

• Arrays versus collections

  • It can be created to hold either values of primitive data types or references to objects; Collections can only hold references to objects, and you can use wrapper classes (Integer, Double, and so on) to hold values of primitive data types

• Other details

  • The difference between list.add(list1) and list.add(new ArrayList<>(list1)) is:

  // The first case:
  List<List<Integer>> res = new ArrayList<>();
  List<Integer> row = new ArrayList<>();
  
  for (int i = 1; i <= 3; i++) {
    row.add(i);
    res.add(row);
  }
  / / the result:
  / / row: [1, 2, 3]
  / / res: [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
  // Only two objects, res and row, are created, and finally three references to the same object row are added to res.
  
  // The second case:
  for (int i = 1; i <= 3; i++) {
    row.add(i);
    res.add(new ArrayList<>(row));
  }
  / / the result:
  / / row: [1, 2, 3]
  / / res: [[1], [1, 2], [1, 2, 3]]
  // Create 5 objects, res,row, and copies of row at three different times.
  
  Copy the code