Java Collection Framework System Summary
Notice:
- 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.
- 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
type | underlying data structure | thread safety | efficiency | Use recommended |
---|---|---|---|---|
ArrayList | array | × | Fast query, slow addition and deletion | √ |
LinkedList | Doubly linked list | × | Inquiries are slow, additions and deletions are fast | √ |
Vector | array | √ | Inquiries are fast, additions and deletions are slow, and the overall efficiency is low | × |
Stack | array | √ | First in first out, low overall efficiency | × |
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; }
-
- When the capacity of the ArrayList is 0, add an element
⇓
\Downarrow
⇓
- 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.
- 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.
- 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)
- When the capacity of the ArrayList is 0, add an element
⇓
\Downarrow
⇓
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)
type | underlying data structure | Notice | thread safety | efficiency | category |
---|---|---|---|---|---|
HashSet | Before JDK8, the hash table (array
+
+
+ list) After JDK8, the hash table (array + + + linked list + + + red-black tree) Analysis of the underlying principle of HashSet | disorder | × | quick | Implementation class |
TreeSet | red-black tree | Sorting rules can be specified (default natural ordering) | × | Implementation class | |
LinkedHashSet | HashSet + + + Doubly linked list (record addition order) | ordered (order of addition) | × | Implementation class | |
EnumSet | HashSet + + + enumeration element | The corresponding enum class must be specified explicitly or implicitly | × | abstract class |
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)
type | bottom layer | be careful | thread safety | efficiency | category |
---|---|---|---|---|---|
HashMap | Before JDK8, arrays
+
+
+ singly linked list After JDK8, arrays + + + singly linked list + + + red-black tree | disorder | × | quick | Implementation class |
Hashtable | Quasi-HashMap | null is not allowed as key and value | √ | slow | Implementation class |
Properties | Hashtable + + + internal expansion | Only allow adding String key-value Common processing property profiles | √ | slow | Implementation class |
TreeMap | red-black tree | You can specify a key sort comparator (default ascending sort) | × | Implementation class | |
LinkedHashMap | HashMap + + + Doubly linked list (record addition order) | ordered (order of addition) | × | Implementation class | |
EnumMap | HashMap + + + enum key | key must be the enum value of a single enum class The corresponding enum class must be specified explicitly or implicitly null is not allowed as key | × | Implementation class |
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 ... }
-
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.