Revisit Java Chapter 5 – Collections

  • Collections, containers of data, we use them every day. Let’s go over them

Why collections? Why not arrays

  • Arrays can store data, but once the array is specified, it cannot exceed the specified length. When the number of data is unknown, it is a bit troublesome

What’s the difference between collections and arrays?

  • The data type of the element of an array, which can be a primitive data type or an object. Collections, on the other hand, can only be objects, so when you need to store basic data types, you store their wrapper classes. For example, if you want to store int, the corresponding wrapper class is Integer.

Classification of sets

  • Aggregate root interface

    • Collection
    • Map, key-value pair, data that has a mapping relationship

  • The subinterface of the root interface, where Map does not have a subinterface but is directly implemented.

    • Collection
      • List, ordered, repeatable
      • Set, unordered, non-repeatable

  • Common implementation classes for the List interface

    • ArrayList, the underlying implementation of arrays
    • LinkedList, the underlying bidirectional link-up list implementation
    • Vector is a thread-safe ArrayList, and an ArrayList is thread-unsafe
    • CopyOnWriteArrayList, a List interface implementation class added to the JDk1.5-Concurrent package designed for concurrency

  • Common implementation classes for the Set interface

    • A HashSet is an unordered hash table that cannot be repeated. If the value is repeated, the new value overwrites the old value
    • LinkedHashSet, a hash table implemented as a linked list, is ordered and non-repeatable
    • TreeSet: The bottom layer is a red-black tree, and the overall records are sorted according to the specified rule
    • CopyOnWriteArraySet is similar to CopyOnWriteArrayList, but it implements the Set interface.

  • Common implementation classes for the Map interface

    • HashMap, the underlying hash table, key-value pairs. The key Value of a maximum of one record is allowed to be Null(multiple records will be overwritten). The Value of multiple records is allowed to be Null.
    • LinkedHashMap, a hash table that implements linked lists at the bottom. Key-value pairs, ordered.
    • TreeMap: The bottom layer is a red-black tree with key-value pairs. The overall records are sorted according to the specified rule
    • A Hashtable is similar to a HashMap, except that neither Key nor Value can be Null, and it is thread-safe, resulting in lower performance.
    • ConcurrentHashMap, a Map implementation for concurrent design.

The List collection implements the similarities and differences of classes

  • ArrayList, the bottom of the array implementation, so the storage space is continuous, do the query will be faster. But when you do insert and delete, you have to move the array elements every time, so it’s slow.

  • LinkedList, the bottom layer is a bidirectional LinkedList. LinkedList elements are connected from end to end. When inserting, you only need to find the front element, attach the current element to the tail, and then find the back element, attach the head, so the insertion and deletion speed is relatively fast. When querying, memory addresses are not necessarily contiguous, so the search will be slow.

  • Vector, which can be understood as a thread-safe ArrayList, has been added with the synchronized keyword to ensure thread-safe, but it loses performance and is generally not used now. Using the Collections utility class to call synchronizedList for wrapping (essentially using decorator mode to add, delete, and query methods with the synchronized keyword to ensure thread-safety).

  • CopyOnWriteArrayList, designed for concurrent List interface implementation class, mostly used for read and write less scene, as the name implies is in the write operation, copy a copy of data to the new container, and then reference to the new container reference, the whole process is to lock the implementation of thread safety, and read is not locked.

  • conclusion

    • Most single-threaded read operations are performed by ArrayList, while most add and delete operations are performed by LinkedList.

    • Multithreading, the Collections utility class calls synchronizedList to wrap the List implementation; Vector is not recommended.

    • In high concurrency scenarios, CopyOnWriteArrayList read-write separation solves concurrency problems.

The similarities and differences of Set collection implementation classes

  • HashSet, the underlying hash table, unordered, cannot store repeated elements, such as repetition, the new value will overwrite the old value, hash table generates index, relatively fast. Do not care about the order, need to exclude repetition when used.

  • LinkedHashSet, an ordered, non-repeatable hash table implemented as a linked list, used when a non-repetitive, and ordered scene is required.

  • TreeSet, which is A red-black tree at the bottom, can be sorted after insertion. This type of TreeSet is not sorted by insertion order, but by certain rules, such as the order of digits and letters A and B.

  • conclusion

    • Single thread

      • Don’t care about order, just make sure you don’t repeat, use HashSet

      • To ensure the order in which inserts are sorted, use LinkedHashSet

      • After all inserts are needed, the whole sort is sorted in the specified order, using TreeSet

    • multithreading

      • When thread-safe is required, the Map implementation is wrapped using the Collections utility class call synchronizedMap.

    • High concurrency

      • You can use CopyOnWriteArraySet for concurrent processing

Map collection implementation class similarities and differences

  • HashMap, the underlying hash table, key-value pairs. The key Value of a maximum of one record is allowed to be Null(multiple records will be overwritten). The Value of multiple records is allowed to be Null.

  • LinkedHashMap, hash table with key-value pairs, ordered, key-value allowed to be null, asynchronous

  • TreeMap: The bottom layer is a red-black tree with key-value pairs. The overall records are sorted according to the specified rule

  • A Hashtable is similar to a HashMap, except that neither Key nor Value can be Null, and it is thread-safe, resulting in lower performance.

  • ConcurrentHashMap, a Map implementation to deal with concurrent design, implements lock separation. The Hash bucket is divided into 18 segments. The Hash bucket is not locked in the GET operation but is locked by segment in the set mode

  • conclusion

    • Single thread

      • Don’t care about the order, just make sure you don’t repeat, use HashMap

      • To ensure insertion ordering, use LinkedHashMap

      • After all inserts are required, TreeMap is used when the overall sort is sorted in the specified order

    • multithreading

      • When thread-safe is required, the Map implementation is wrapped using the Collections utility class call synchronizedMap.

    • High concurrency

      • ConcurrentHashMap can be used for concurrent processing

Common collection manipulation apis

  • boolean add(Object o); Inserts data into a collection, returning true if the collection object was changed by the add operation. So the insertion was successful.

    ArrayList<String> list = new ArrayList<>();
        list.add("Wally");
Copy the code

  • boolean addAll(Collection c); Adds all elements of another collection c to the specified collection, returns true on success.

    ArrayList<String> list = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();
list2.add("Barry");
list.addAll(list2);
Copy the code

  • void clear(); Empties the set element, set length 0.

    ArrayList<String> list = new ArrayList<>();
list.add("Barry");
list.clear();
Copy the code

  • Boolean contains(Object O), determines whether the collection contains the specified element.

    ArrayList<String> list = new ArrayList<>();
String name = "Barry";
list.add(name);
list.contains(name);
Copy the code

  • Boolean containsAll(Collection c), checks whether the Collection containsAll the elements in the specified Collection c.

    ArrayList<String> list = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();
String name = "Barry";
list.add(name);
list2.add(name);
list2.add("Wally");
list2.containsAll(list);
Copy the code

  • Boolean isEmpty(), checks whether the set isEmpty, returns true for length 0, false otherwise.

    ArrayList<String> list = new ArrayList<>();
list.isEmpty();
Copy the code

  • Boolean remove(Object o), removes the specified element from the set. If more than one element in the set matches, only the first matching element is removed. Returns true on success, false otherwise.

    ArrayList<String> list = new ArrayList<>();
String name = "Barry";
list.add(name);
list.remove(name);
Copy the code

  • Boolean removeAll(Collection C), removes all elements from the specified Collection C.

    ArrayList<String> list = new ArrayList<>();
String name = "Barry";
//[Barry]
list.add(name);
ArrayList<String> list2 = new ArrayList<>();
list2.add(name);
//[Barry, wally]
list2.add("Wally"); [Wally] list2. RemoveAll (list);Copy the code

  • Boolean retainAll(Collection C), removes elements from the Collection that are not in the specified Collection C. It’s equivalent to preserving only the intersection of the two sets.

    ArrayList<String> list = new ArrayList<>();
String name = "Barry";
//[Barry]
list.add(name);
ArrayList<String> list2 = new ArrayList<>();
list2.add(name);
//[Barry, wally]
list2.add("Wally"); // only the intersection part of 2 sets, only [Barry] list2.retainAll(list);Copy the code

Apis for special collections

  • ArrayList
  • Find elements by corner markers
  ArrayList<String> list = new ArrayList<>();
  list.add("Barry");
  //Barry
  String result = list.get(0);
Copy the code
  • Remove elements by corner label
ArrayList<String> list = new ArrayList<>();
list.add("Barry");
list.remove(0);
Copy the code
  • Angle of the traverse
ArrayList<String> list = new ArrayList<>();
list.add("Barry");
list.add("Wally");
list.add("Lucy");
for (int i = 0; i < list.size(); i++) {
    String element = list.get(i);
    System.out.println("element " + element);
}
Copy the code

Map collections API

  • Add elements
HashMap<String, Integer> map2 = new HashMap<>();
map.put("Barry", 22);
map.putAll(map2);
Copy the code
  • Remove elements
HashMap<String, Integer> map2 = new HashMap<>();
map.put("Barry", 22);
map.remove("Barry");
Copy the code
  • Get all Key sets
HashMap<String, Integer> map2 = new HashMap<>();
map.put("Barry", 22);
Set<String> keySet = map.keySet();
Copy the code
  • Gets a collection of all values
HashMap<String, Integer> map2 = new HashMap<>();
map.put("Barry", 22);
Collection<Integer> values = map.values();
Copy the code
  • Determines whether a Key is in the collection
HashMap<String, Integer> map2 = new HashMap<>();
map.put("Barry", 22);
boolean isContains = map.containsKey("Barry");
Copy the code
  • Determines whether a Value exists in the set
HashMap<String, Integer> map2 = new HashMap<>();
        map.put("Barry", 22);
        boolean isContainsValue = map.containsValue(18);
Copy the code
  • traverse
HashMap<String, Integer> map2 = new HashMap<>();
map.put("Barry", 22);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}
Copy the code