Java Collection Framework System Summary

Notice:

1. This article cites a large number of high-quality articles, and some of the applied ones have links to directly view the in-depth analysis of knowledge points.
2. As for the content involving the code section, it is presented in the form of Demo + annotations. Demo mainly involves basic and common methods as well as some advanced methods, and is categorized in the annotations so that readers can select the part they want based on the annotations (but it is still recommended that the entire code block has an overall understanding, and various errors and details are prone to occur are also marked in the comments).

Array: fixed length, can only store the same type (basic/reference type)

Collections: variable length, can store different types (only reference types)

Iterator: The Iterator object is called an iterator, which is used to traverse the elements in the Collection collection. All collection classes of the Collection interface have an iterator() method that returns an object that implements the Iterator interface. It is only used to traverse the collection, and does not provide the ability to host objects. If you want to create an IUterator object, you must have an iterated collection.

1,Collection

1.1 List

A collection with order, elements can be accessed by integer subscripts, and can contain duplicate elements

ArrayList

• Basic operation

  Includes build, CRUD, traversal, sorting, deduplication, and other built-in methods.

      /**
       * ArrayList 
       */
      public static void ArrayListDemo() {
          // 1. Construction method √
          // No parameter construction => The capacity is 0, the default value of the number of elements is 0
          // public ArrayList()
          ArrayList<String> arrayStringList = new ArrayList<>();
          // Fixed-len gt h structure => The capacity is a given value (less than 0 will report an error), the number of elements size is the default value of 0
          // public ArrayList(int initialCapacity)
          ArrayList<Integer> arrayIntegerList = new ArrayList<>(10);
          // Collection construction √
          // public ArrayList(Collection<? extends E> c)
          HashSet<Long> hashSet = new HashSet<>(2);
          hashSet.add(1L);
          hashSet.add(Long.valueOf("99999999999999"));
          ArrayList<Long> arrayLongList = new ArrayList<>(hashSet);
          System.out.println(arrayLongList); // [1, 99999999999999]
  
          // 2. Basic CRUD operations √
          // increase
          arrayStringList.add("study");
          arrayStringList.add(0,"I want");
          System.out.println("originStringList: " + arrayStringList.toString()); //originStringList: [I want, learn]
          // change
          arrayStringList.set(0, "I do not");
          // check
          System.out.println("lastStringList: " + arrayStringList.get(0) + arrayStringList.get(1)); //lastStringList: I don't study
          // delete
          arrayStringList.remove("I do not");
          //arrayStringList.remove(0);
          System.out.println(arrayStringList); //[study]
  
          // 3. Traverse
          // normal traversal
          for (int i = 0; i < arrayLongList.size(); i++) {
              System.out.print(arrayLongList.get(i) + " "); //1 99999999999999
          }
          System.out.println();
          // Enhanced traversal √
          for (Long num : arrayLongList) {
              System.out.print(num + " "); //1 99999999999999
          }
          System.out.println();
          // iterator traversal
          Iterator<Long> longIterator = arrayLongList.iterator();
          while(longIterator.hasNext()) {
              System.out.print(longIterator.next() + " "); //1 99999999999999
          }
          System.out.println();
  
          // 4. Sort
          ArrayList<Pair<Integer, String>> sortList = new ArrayList<>();
          sortList.add(new Pair<>(1, "zhangsan"));
          sortList.add(new Pair<>(2, "lisi"));
          sortList.add(new Pair<>(3, "wangwu"));
          // Comparator
          Collections.sort(sortList, new Comparator<Pair<Integer, String>>() {
              @Override
              public int compare(Pair<Integer, String> o1, Pair<Integer, String> o2) {
                  return o1.getKey() - o2.getKey();
              }
          });
          System.out.println(sortList); //[1=zhangsan, 2=lisi, 3=wangwu]
          // Lambda (Java8)√
          Collections.sort(sortList, (o1, o2) -> o1.getValue().compareTo(o2.getValue()));
          System.out.println(sortList); //[2=lisi, 3=wangwu, 1=zhangsan]
          // stream(Java8)√
          sortList = (ArrayList<Pair<Integer, String>>) sortList.stream().sorted((o1, o2) -> o2.getValue().length() - o1.getValue().length()).collect(Collectors.toList());
          System.out.println(sortList); //[1=zhangsan, 3=wangwu, 2=lisi]
  
          // 5. Deduplication
          for(int i = 0; i < 5; i++) {
              arrayIntegerList.add(i % 2);
          }
          // With the help of auxiliary sets (omitted)
          // iterator => change order
          ListIterator<Integer> integerIterator = arrayIntegerList.listIterator();
          while(integerIterator.hasNext()) {
              Integer next = integerIterator.next();
              integerIterator.remove();
              if (!arrayIntegerList.contains(next)) {
                  integerIterator.add(next);
              }
          }
          System.out.println(arrayIntegerList); //[1, 0]
          // stream => the order is unchanged √
          for(int i = 0; i < 5; i++) {
              arrayIntegerList.add(i % 2);
          }
          arrayIntegerList = arrayIntegerList.stream()
                  .collect(Collectors.collectingAndThen(Collectors.toCollection(HashSet::new), ArrayList::new));
          System.out.println(arrayIntegerList); //[0, 1]
  
          // 6. Get the capacity of ArrayList (expansion) => use reflection mechanism
          // Think: Why does the capacity change at this time? => ArrayList expansion principle
          System.out.println("arrayStringList-Capacity: " + getCapacity(arrayStringList)); //arrayStringList-Capacity: 10
          System.out.println("arrayIntegerList-Capacity: " + getCapacity(arrayIntegerList)); //arrayIntegerList-Capacity: 2
  
          // 7. More arrayList content => jdk documentation
          // element exchange
          Collections.reverse(arrayIntegerList);
          System.out.println(arrayIntegerList);
          // reverse
          Collections.swap(arrayIntegerList, 0, 1); //[1, 0]
          System.out.println(arrayIntegerList); //[0, 1]
      }
  
      /**
       * Use reflection mechanism to obtain capacity
       * @param list
       * @return
       */
      public static Integer getCapacity(ArrayList list) {
          Integer length = null;
          Class clazz = list.getClass();
          Field field;
          try {
              field = clazz.getDeclaredField("elementData");
              field.setAccessible(true);
              Object[] object = (Object[]) field.get(list);
              length = object.length;
              return length;
          } catch (Exception e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
          }
          return length;
      }
  

• Expansion mechanism

  • When the capacity of the ArrayList is 0, add an element ⇓ \Downarrow ⇓
    1. No-parameter construction, after adding the first element, the capacity becomes 10, after that, the capacity will be expanded normally if it needs to be expanded.
    2. The capacity transfer structure, after adding the first element, the capacity is 1, after that, if the capacity needs to be expanded, the capacity will be expanded normally.
    3. The list is passed to construct and the list is empty. After adding the first element, the capacity is 1. After that, if the capacity needs to be expanded, the capacity will be expanded normally.
  • When the capacity of the ArrayList is greater than 0 and the ArrayList is full, add elements ⇒ \Rightarrow ⇒ Normal expansion (1.5 times the original capacity each time)

LinkedList

The first and last references point to the first and last elements of the linked list, respectively, and each node is represented by the inner class Node.

Note: When LinkedList is empty, both first and last point to null

• Basic operation

  ​ Including build, CRUD, traverse, reverse, sort, merge, get node (intermediate/arbitrary), judgment loop, judgment palindrome and other built-in methods

      public static void LinkedListDemo() {
          //1. Constructor
          // Null parameter construction => empty linked list, first and null point to empty √
          LinkedList<String> linkedStringList = new LinkedList<>();
          // Collection construction √
          HashSet<Long> hashSet = new HashSet<>(2);
          hashSet.add(1L);
          hashSet.add(Long.valueOf("99999999999999"));
          LinkedList<Long> linkedLongList = new LinkedList<>(hashSet);
          //2. Basic CRUD
          // increment => head, tail, given index
          linkedStringList.add("study");
          linkedStringList.addFirst("I");
          linkedStringList.addLast("habit");
          linkedStringList.add(1, "Love");
          System.out.println(linkedStringList); //[I, love, learn, study]
          // change => given index
          linkedStringList.set(1, "Do not");
          System.out.println(linkedStringList); //[I, do not, learn, study]
          // Search => head, tail, given index (similar to halved search)
          System.out.println(linkedStringList.getFirst() + linkedStringList.get(2)  +linkedStringList.getLast()); //I learn
          // delete => head, tail, given index
          linkedStringList.removeFirst();
          linkedLongList.removeLast(); //Note: delete as empty (think: why no exception is thrown here?)
          linkedStringList.remove(0); //I learn
          //3. Traverse
          // Normal for => Enhanced for √
          for (String s : linkedStringList) {
              System.out.print(s + " "); //study
          }
          System.out.println();
          // iterator => list iterator √
          ListIterator<String> stringListIterator = linkedStringList.listIterator();
          while(stringListIterator.hasNext()) {
              System.out.print(stringListIterator.next() + " "); //study
          }
          System.out.println();
          // forEach method => stream stream method
          linkedStringList.forEach(item -> System.out.print(item + " ")); //study
          System.out.println();
          linkedStringList.stream().forEach(item -> System.out.print(item + " ")); //study
          System.out.println();
          //TODO thinking linked list => reverse, sort, merge, get node (intermediate/arbitrary), judge loop, judge palindrome
      }
  

1.2 Set

A collection without order, elements are not accessed by integer subscripts, and do not contain duplicate elements (hashCode and equals methods ensure element uniqueness)

HashSet

• Basic operation

  public static void hashSetDemo() {
      //1. Construction
      // Empty parameter => default initial capacity is 16 and load factor is 0.75
      HashSet<String> stringHashSet = new HashSet<>();
      // Specify initial capacity => public HashSet(int initialCapacity)
      // The specified initial capacity and the specified load factor => public HashSet(int initialCapacity, float loadFactor)
      // collection construct
      Long[] longs = new Long[]{1L, 2L, 2L, 3L, 4L};
      ArrayList<Long> longArrayList = (ArrayList<Long>) Stream.of(longs).collect(Collectors.toList());
      HashSet<Long> longHashSet = new HashSet<>(longArrayList);
      System.out.println(longHashSet); //[1, 2, 3, 4]
      longArrayList.clear();
      //2. CRUD
      //increase
      longHashSet.addAll(longArrayList);
      if (!longHashSet.isEmpty()) {
          longHashSet.add(99999999999999L);
          longHashSet.add(678910L);
          longHashSet.add(12345L);
  
      }
      System.out.println(longHashSet); //[1, 2, 3, 4, 678910, 99999999999999, 12345]
      //change ×
      //Check × => Include √
      System.out.println(longHashSet.contains(9)); //false
      System.out.println(longHashSet.containsAll(longArrayList)); //true
      //delete
      longHashSet.remove(1L); //Note here that if it is 1, the deletion fails
      System.out.println(longHashSet.removeAll(longArrayList)); //false
      longHashSet.removeIf(item -> item.equals(12345L) || item.equals(678910));
      System.out.println(longHashSet); //[2, 3, 4, 678910, 99999999999999]
      //3. Traverse
      // Enhance for
      for (Long num : longHashSet) {
          System.out.print(num + " "); //2 3 4 678910 99999999999999
      }
      System.out.println();
      // iterator
      Iterator<Long> longIterator = longHashSet.iterator();
      while(longIterator.hasNext()) {
          System.out.print(longIterator.next() + " "); //2 3 4 678910 99999999999999
      }
      System.out.println();
      // TODO verification disorder, clone method, application scenario?
  }
  

1.3 Selection of queues and stacks

Implementation class selection

• Normal queue: ArrayDeque/LinkedList
• Normal stack: ArrayDeque
• Blocking and bidirectional queues: BlockingQueue interface

ArrayDeque

• JDK 1.8 official notes:

  • When ArrayDeque is used as a stack, this class may be faster than Stack

  • ArrayDeque is faster than LinkedList when used as a queue

• characteristic

  • Adding null is not allowed ⇒ \Rightarrow ⇒ as loop end condition

  • Two-way queue, automatic two-way expansion (expansion when the array is full, the length must be a power of 2, the maximum length of the array is 2 30 2^{30} 230)

    

  • Use the head of the queue head, the index pointer of the next tail at the end of the queue ⇒ \Rightarrow ⇒ the whole is equivalent to a circular array

    

  • thread unsafe

• use as a queue

  public static void arrayDequeAsDeque() {
      // 1. Create a stack
      Deque queue = new ArrayDeque<>();
      // 2. Join the team
      queue.offer("first");
      queue.offer("second");
      // 3. Query Team Elements
      System.out.println(queue.getFirst()); //first
      System.out.println(queue.getLast()); //second
      // 4. Departure
      queue.poll();
      System.out.println(queue); //[second]
  }
  

• use as stack

     public static void arrayDequeAsStack() {
      // 1. Create a stack
      Deque stack = new ArrayDeque<>();
      // 2. Push the stack
      stack.push("first");
      stack.push(1);
      stack.push(1.0);
      // 3. View stack elements
      System.out.println(stack.getFirst()); //1.0
      System.out.println(stack.getLast()); //first
      // 4. Pop the stack
      stack.pop();
      System.out.println(stack); //[1, first]
  }
  

2,Map

Two-column collection, one element contains key-value (key cannot be repeated, value can be repeated, and types can be different)

HashMap

The bottom layer is implemented based on a hash algorithm, which is a container of key-value structures.

• Basic operation

      public static void HashMapDemo() {
      // 1. Constructor
      // No parameter => default load factor 0.75f, default capacity 16
      HashMap<Long, String> hashMap = new HashMap<>();
      // Specify the initial capacity public HashMap(int initialCapacity)
      // Specify initial capacity and load factor public HashMap(int initialCapacity, float loadFactor)
      // Constructor for parameters of type Map => public HashMap(Map<? extends K, ? extends V> m)
      HashMap<Long, String> tempHashMap = new HashMap<>(hashMap);
      // 2. CRUD
      // Add, modify (direct coverage)
      tempHashMap.put(1L, "first");
      tempHashMap.put(3L, "third");
      hashMap.putAll(tempHashMap);
      if (!hashMap.isEmpty()) {
          hashMap.put(2L, "second");
      }
      System.out.println(hashMap);
      // check
      System.out.println(hashMap.get(1) + " " + hashMap.get(1L)); //null first
      // delete
      if (hashMap.containsKey(1L) && hashMap.containsValue("first")) {
          if (!hashMap.remove(1, "first")) {
              System.out.println("key = 1L and value = " + hashMap.remove(1L)); //key = 1L and value = first
          }
      }
      // 3. Traverse the following outputs are { key = 2 and value = second, key = 3 and value = third, }
      // Iterator entrySet (key-value pair view) => keySet key view, values ​​value view
      Iterator<Map.Entry<Long, String>> iterator = hashMap.entrySet().iterator();
      System.out.print("{ ");
      while (iterator.hasNext()) {
          Map.Entry<Long, String> next = iterator.next();
          System.out.print("key = " + next.getKey() + " and value = " + next.getValue() + ", ");
      }
      System.out.println(" }");
      // Enhance for
      System.out.print("{ ");
      for (Map.Entry<Long, String> entry : hashMap.entrySet()) {
          System.out.print("key = " + entry.getKey() + " and value = " + entry.getValue() + ", ");
      }
      System.out.println(" }");
      // lambda expression
      System.out.print("{ ");
  
      hashMap.forEach((key, value) -> {
          System.out.print("key = " + key + " and value = " + value + ", ");
  
      });
      System.out.println(" }");
      // stream single-threaded stream
      System.out.print("{ ");
      hashMap.entrySet().stream().forEach((entry -> {
          System.out.print("key = " + entry.getKey() + " and value = " + entry.getValue() + ", ");
      }));
      System.out.println(" }");
      // parallelStream multi-threaded stream => unpredictable output results
      System.out.print("{ ");
      hashMap.entrySet().parallelStream().forEach((entry -> {
          System.out.print("key = " + entry.getKey() + " and value = " + entry.getValue() + ", ");
      }));
      System.out.println(" }");
      // TODO Other built-in methods containsValue containsKey clear ...
  }
  

• red-black tree

• underlying logic

  The bottom layer after jdk8 is implemented by array & linked list & red-black tree

  

• Expansion mechanism

  The bottom layer of HashMap is an array. If the length of the array is found to be insufficient, it is necessary to expand the capacity.

  • Related parameters: initial capacity initialCapacity, load factor loadFactor. By setting parameters, the threshold size can be further influenced.
  • Threshold for expansion: threshold = = = capacity ∗ * ∗ loadFactor (capacity ∗ * ∗ )
  • The maximum number of key-value pairs that the current HashMap can hold, if it exceeds the expansion threshold, the expansion will be carried out.

• fail-fast mechanism

  ​ A common mechanism in Java unsafe collections. This mechanism allows a concurrent modification exception to be triggered if a thread modifies, deletes, or adds to the collection during traversal of the collection. The implementation mechanism is to save a modCount before traversing, and compare whether the current modCount and the saved modCount are equal each time the next element to be traversed is obtained.

  • Avoid some unknown problems due to concurrent modifications and improve performance by failing early.

Properties

Mainly used to read Java configuration files (.properties file, parameter configuration in the form of key-value pairs)

• Basic operation

  Read and write configuration files

      public static void PropertiesDemo() {
      // 1. Construction
      Properties properties = new Properties();
      try {
          // 2. Read the file => Note that the default is to read out of order
          properties.load(new FileInputStream("src/demo.properties"));
          Enumeration fileName = properties.propertyNames();
          while (fileName.hasMoreElements()) {
              String key = (String) fileName.nextElement();
              String value = properties.getProperty(key);
              System.out.println(key + " = " + value);
          }
          // 3. Write to file
          properties = new Properties();
          FileOutputStream outputStream = new FileOutputStream("src/demo.properties",true); //true means append
          properties.setProperty("fifth", "5");
          properties.setProperty("sixth","6");
          properties.store(outputStream,"test");
          outputStream.close();
          // How is TODO written and read sequentially?
      } catch (IOException e) {
          throw new RuntimeException(e);
      }
  }
  

  Directory Structure

  
  before execution

  
  after execution

  

write at the end

Thank you for reading this. If there is something wrong in the article or some relevant content is missing, I hope you can put it in the comment area, and I will make changes as soon as possible, thank you.