Java Collection Framework System - The whole system of Collection and Map from practicality, comparison to underlying analysis

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

typeunderlying data structurethread safetyefficiencyUse recommended
ArrayListarray×Fast query, slow addition and deletion
LinkedListDoubly linked list×Inquiries are slow, additions and deletions are fast
VectorarrayInquiries are fast, additions and deletions are slow, and the overall efficiency is low×
StackarrayFirst 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;
        }
    
  • 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)

typeunderlying data structureNoticethread safetyefficiencycategory
HashSetBefore 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×quickImplementation class
TreeSetred-black treeSorting rules can be specified
(default natural ordering)
×Implementation class
LinkedHashSetHashSet + + + Doubly linked list (record addition order)ordered (order of addition)×Implementation class
EnumSetHashSet + + + enumeration elementThe 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)

typebottom layerbe carefulthread safetyefficiencycategory
HashMapBefore JDK8, arrays + + + singly linked list
After JDK8, arrays + + + singly linked list + + + red-black tree
disorder×quickImplementation class
HashtableQuasi-HashMapnull is not allowed as key and valueslowImplementation class
PropertiesHashtable + + + internal expansionOnly allow adding String key-value
Common processing property profiles
slowImplementation class
TreeMapred-black treeYou can specify a key sort comparator (default ascending sort)×Implementation class
LinkedHashMapHashMap + + + Doubly linked list (record addition order)ordered (order of addition)×Implementation class
EnumMapHashMap + + + enum keykey 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 ...
    }
    
  • 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.

Tags: Java data structure linked list

Posted by mrobertson on Sun, 18 Sep 2022 21:24:48 +0300