Java collection framework

This paper summarizes the Java collection framework

Here are some articles about collections

Take a look at the structure chart first to get a general impression, which is convenient for follow-up learning

Overview of collection framework

Sets and arrays are structures that store multiple data, referred to as Java containers for short.
Note that the storage at this time refers to the storage at the memory level, and does not involve persistent storage (. txt,.jpg, database)

Collection can solve the disadvantages of storing data in arrays

Java container

Collection and array are structures used to store multiple data, which are called Java containers for short


Characteristics of array in storing multiple data

1.Once an array is created, its length cannot be changed
2.Once the array is defined, its element type is determined

Disadvantages of arrays in storing multiple data

1. Once the array is determined, its length cannot be changed
2.The methods provided in the array are very limited, which is inconvenient and inefficient for a series of operations such as adding, deleting, modifying and inserting
3.The requirement to obtain the number of actual elements in the array. The array has no ready-made properties or methods to use
4.The characteristics of array storage data: orderly and repeatable, which can not meet the requirements of disorder and non repeatable

Collection framework

System classification of Java collections

Collections cannot directly store basic data types or Java objects, but only the memory address of Java objects

It is divided into two systems: Collection and Map

The collection API provided by JDK is located in Java Util package

Collection interface:

The data stored is one by one, just like objects.

Single column data, which defines the collection of methods to access a group of objects, and does not directly provide its implementation class

Common methods in the Collection interface:

When adding data obj to the object of the implementation class of the Collection interface, the class where obj is located is required to use the equals method again

1,add to 

add(Object obj)
addAll(Collection coll) 

2,Get the number of valid elements

  int size()

3,Empty collection elements

  void clear()  Just empty the element, the object still exists

4,Whether it is an empty collection (i.e. whether there are elements in the collection)

  boolean isEmpty()
  Its bottom layer is:
    public boolean isEmpty(){
    return size==0;

5,Whether to include an element

 The underlying call is equals method
 Generally speaking, we Collection Add data to the object of the implementation class of the interface obj When you need help, ask obj Class to override equals method

boolean contains(Object obj): By element equals Method to determine whether it is the same object


boolean containsAll(Collection c): It is also the of calling elements equals Method to compare. Compare the elements of two sets one by one.


boolean remove(Object obj) : By element equals Method to determine whether it is the element to be deleted. Only the first element found will be deleted

Remove from current collection coll All elements in
 Current set and coll Elements may have different parts, and what is eventually removed is their intersection
boolean removeAll(Collection coll): Take the difference set of the current set

7,Take the intersection of two sets

  boolean retainAll(Collection c): Save the result of intersection in the current set without affecting c ,However, the current set is modified

8,Are sets equal

 boolean equals(Object obj)
be careful:
Collection c=new ArrayList();
Collection c1=new ArrayList();
c.equals(c1);  // The result is false at this time
 because ArrayList It is ordered, so the element order is different false

9,Conversion of set and array
  Convert to array:
  Object[] toArray()
 Convert to set
 List Arrays.asList(); The parameters inside are deformable parameters
   List list=Arrays.asList(new Integer(123,456));//Default as an element
 List list1=Arrays.asList(new int[](123,456));//By default, it is treated as an element system out. println(list1.size()); //  one

10,Gets the hash value of the collection object



  iterator(): Returns an iterator object for collection traversal

import org.junit.Test;

import java.util.*;

 * The traversal operation of collection elements uses the Iterator iterator interface
 * 1.Internal methods: hasNext and next
 * 2.Every time the collection object calls the iterator() method, it gets a new iterator object
 * The default cursors are before the first element of the collection
 * 3.Remove () is defined internally, which can delete the elements in the collection when traversing. This method is different from calling remove directly in the collection
 * @author zengyihong
 * @created 2021-04-25 15:06
public class CollectionTest {
     * Conclusion:
     * When adding data obj to the object of the implementation class of the Collection interface, the class where obj is located is required to use the equals method again
    public void test1() {
        Collection coll = new ArrayList();
        coll.add( new String("Tom"));
        coll.add(new Person("Jerry",20));

        //contains(Object obj) determines whether the current collection contains obj
        //When judging, we will call the equals method of the class where the obj object is located
        boolean contains = coll.contains(123);
        System.out.println(coll.contains(new String("Tom")));
        System.out.println(coll.contains(new Person("Tom",20)));

        //containsAll(Collection coll): judge whether all elements in the formal parameter coll are in the current collection

        Collection coll1= Arrays.asList(123,4567);

    public void test2(){

        //remove(Object obj)

        Collection coll = new ArrayList();
        coll.add( new String("Tom"));

        //removeAll(Collection coll1): removes all elements in the collection coll1 from the current collection

        //Set ----- > array: toArray()
        Object[] array = coll.toArray();
        for (int i = 0; i < array.length; i++) {
        //Extension: array -- > Set
        List<String> list = Arrays.asList(new String[]{"aa", "bb", "cc"});
        List list=Arrays.asList(new Integer(123,456));
        System.out.println(list.size()); // 1

        List list1 = Arrays.asList(new int[]{123, 456});

        List list2 = Arrays.asList(new Integer[]{123, 456});

        //iterator(): returns an instance of the iterator interface for traversing collection elements


    public void test3(){
        Collection coll = new ArrayList();
        coll.add( new String("Tom"));

        //Delete Tom from collection“
        Iterator iterator=coll.iterator();
        while (iterator.hasNext()){

            Object obj =;//Receive the elements in the collection
            if ("Tom".equals(obj)){

        //Traversal set
        //At this time, the pointer has reached the last element. We need to re point the pointer to the first element
        while (iterator.hasNext()){

    public void testListRemove() {
        List list = new ArrayList();
    private static void updateList(List list) {
        list.remove(2);//Remove element with index position 2


Source code analysis of contains method in Collection interface

boolean contains(Object o) determines whether a collection contains an object
The equals method is called at the bottom of the contains method

The contains method is used to determine whether a collection contains an element. At the bottom, it calls the equals method for comparison

The equals method returns true, which means it contains this element

If the elements placed in the collection do not override the equals method, the comparison is that the equals method is called for the object

remove method source code analysis

boolean remove( )

The underlying calls the equals method

Iterator iterator interface:

It can be used to traverse the collection, but the Map cannot be traversed with this

Overview of Iterator interface

Iterator method

You can think of iteritor as a cursor pointing to the left of the element.
1.boolean hasNext(); // Determine whether there is an element on the right side of the cursor
2.Object next(); // Returns the element to the right of the cursor and moves the cursor to the next position
3.void remove(); // Delete the element on the left of the cursor and execute next after execution

remove method in iterator

void remove() deletes the current element pointed to by the iterator

Use the Iterator iterator to iterate over the elements in the collection

Mode 1:

   //Make a set first
   Collection coll=new ArrayList();
   //Adding elements to a collection
   coll.add(new String("Tom"));
   //Then create an Iterator (i.e. Iterator object)
   Iterator iterator=coll.iterator();
   //Then call the next method. If there are several elements, call it several times
   //If the number of calls exceeds the number of elements, an exception NoSuchElementException will be reported;;;;

Mode 2:
//Make a set first
   Collection coll=new ArrayList();
   //Adding elements to a collection
   coll.add(new String("Tom"));
   //Then create an Iterator (i.e. Iterator object)
   Iterator iterator=coll.iterator();
   //Then use the loop statement. If there are several elements, call the next method several times
   for(int i=0;i<coll.length;i++){;

Method 3: key recommendation
//Make a set first
	Collection coll=new ArrayList();
	//Adding elements to a collection
	coll.add(new String("Tom"));
	//Then create an Iterator (i.e. Iterator object)
	Iterator iterator=coll.iterator();
	while(iterator.hasNext()){//Determine whether there is another element
	//next() ① move the pointer down ② return the elements at the set position after moving down

Once the structure of a collection changes, the iterator must retrieve it

Iterator execution principle

The iterator did not initially point to the first element

Let's get an iterator object first

At this point, it is equivalent to having a pointer

Then determine whether the set has the next element

If so, move the pointer back and point to the element to get the element

When using iterators, the following exception may appear. What is the exception of concurrentmodificationexception

The above exception will appear when we have obtained an iterator object and then need to traverse, but operate on the collection before traversal
If we get the iterator object and operate on the collection at the same time, but we don't traverse the iterator, we won't report an exception at this time

Use the foreach loop to traverse the elements in the collection

1.JDK5.0 Provided foreach Cyclic iterative access Collection And array
2. The traversal operation does not need to obtain the length of the collection or array, and does not need to use the index to access the elements
3.The underlying call that traverses the collection Iteraor operation completed

Syntax for using foreach loops

1. For (type of set element, local variable: set object)
2. For (type of array element, local variable: array object)

 //Method 1: ordinary for loop
       String[] arr=new String[]{"MM","MM","MM"};
//        for (int i = 0; i < arr.length; i++) {
//            arr[i]="GG";
//        }

        //Mode 2: enhance for loop
        //The iterator is still called internally
        for (String s:arr){

        for (int i = 0; i < arr.length; i++) {
Analysis and discussion:
     1, Use common for Cycle:
             We directly operate on the elements in the string array to change the value in the constant pool referred to by the element
     2, Use reinforcement for Cycle:
             We use a variable to point to all elements in the string array, and then operate on the new variable. The data stored in the original string array will not be affected

Sub interface of Collection

List interface

Store ordered and repeatable data--->Dynamic array, replacing the original array

Implementation class of List interface

  1. ArrayList: as the main implementation class of the List interface; Unsafe thread and high efficiency; The underlying layer uses Object[] elementData storage
  2. LinkedList: corresponds to frequent insert and delete operations. The efficiency of using this kind is higher than that of ArrayList. The bottom layer uses two-way linked list storage
  3. Vector: the ancient implementation class of the list interface, which is thread safe and inefficient; The underlying layer uses Object[] elementData storage

The same point of the three: the three classes implement the List interface, which stores orderly and repeatable data


1.JDK7 Case
  ArrayList list=new ArrayList();//The bottom layer creates an Object [] array elementData with a length of 10
  List.add(123)//elementData[0]=new Integer(123)
  List.add(11)//If the capacity of the underlying elementData array is insufficient due to this addition, the capacity will be expanded.
  By default, the capacity expansion is 1.5 At the same time, you need to copy the original array to the new array
  Conclusion: it is suggested to use the constructor with parameters in the development: ArrayList list=new ArrayList(int capacity)The number of capacity expansion can be reduced and the efficiency can be higher
2.JDK8 in ArrayList Change of
   ArrayList list=new ArrayList()//The underlying Object[]elementData is initialized to {}, and an array with a length of 10 is not created
   ArrayList.add(123)//The first time add() is called, the bottom layer creates an array with a length of 10 and adds data 123 to elementData
   Subsequent addition and expansion operations and JDK7 There is no difference. The capacity is expanded to 1.5 times

3.summary:JDK7 Medium ArrayList The creation of is similar to the starving Han style of the singleton, and JDK8 Medium ArrayList The creation of the object is similar to the lazy style of the singleton, delaying the creation of the array and saving memory


The bottom layer is a two-way linked list structure

Advantages of linked list:

The elements on the linked list are stored in space, and the memory address is not related. When randomly adding and deleting elements, there is no need to move a large number of elements

However, the search efficiency is low, and each search must start from the node
The LinkedList collection has no initialization capacity

At first, there was no element in the linked list, and both first and larst were null

LinkedList list=new LinkedList();//The first and last attributes of Node type are declared internally, and the default value is null
List.add(123);//Encapsulate 123 into Node and create Node object

among Node Defined as: reflects LinkedList Two way linked list
 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
   = next;
            this.prev = prev;


When creating objects through the Vector() constructor in JDK7 and JDK8, the bottom layer creates an array with a length of 10. In terms of capacity expansion, the default capacity expansion is twice the length of the original array
The bottom layer is also an array

Create a Vector set with a default initialization capacity of 10

After capacity expansion, it is twice the original capacity

All Vector methods are thread synchronized, with synchronized

Thread safety, low efficiency and less use

Method of List interface

List Except from Collection In addition to the methods inherited by the collection, List Some are added to the collection according to the index
 Methods for manipulating collection elements. 
1.void add(int index, Object ele):stay index Position insertion ele element
2. boolean addAll(int index, Collection eles):from index Position start will eles Add all elements in
3.Object get(int index):Get specified index Element of location
4. int indexOf(Object obj):return obj The position of the first occurrence in the collection
5. int lastIndexOf(Object obj):return obj The position of the last occurrence in the current collection
6. Object remove(int index):Remove assignment index The element of the location and returns this element
7. Object set(int index, Object ele):Setting assignment index The element of the location is ele
8. List subList(int fromIndex, int toIndex):return fromIndex reach toIndex Subset of locations

List common methods

1. Add: add(Object obj)
2. Delete: remove(int index)/remove(Object obj)
3. Change: set(int index,Object obj)
4. Check: get(int index)
5. Insert: add(int index,Object obj)
6. Length: size()
7. Traversal: ① Iterator iterator ② enhanced for loop ③ ordinary for loop for (int i = 0; I < list. Size(); i++){

Error prone questions of remove method

public void testListRemove() {
List list = new ArrayList();
private static void updateList(List list) {
Purpose: difference remove(int index)/remove(Object obj)
     When we use remove Method, in which an integer data is passed in. By default, it is assumed that we want to remove the element at the index position
     If we want to remove the corresponding element, we should box it and convert the data into a wrapper class
     for example : List.remove(new Integer(2)) Delete element 2
     	   List.remove(2)) Delete the element where the index position is 2 

Set interface

Storing unordered and unrepeatable data ---- > there are no additional methods defined in the Set interface of the Collection in senior high school, but the methods in the Collection interface are used
Requirement: the class of the data added to the Set interface must override hashCode() and equals()
The rewritten hashCode() and equals() are consistent as much as possible, and the same object has the same hash code

Characteristics of Set interface


Take HashSet as an example: it is not equal to randomness, and the order of each traversal is fixed. The stored data is not added in the order of array index in the underlying array, but determined according to the hash value of the data

The bottom layer of HashSet is an array with a length of 16

Non repeatability

Ensure that when the added element is judged according to the equals method, it cannot return true. If true is returned, it is considered that the two objects are the same, that is, only one element can be added

Process of adding elements: take HashSet as an example

We to HashSet Add element a First call HashCode()Method, calculation element a The hash value calculated by the hash function HashSet Storage location in the underlying array(mean:Index location),Determine whether there are elements on this position of the array:
	If there is no element above this location, the element a Added successfully.---->Case 1
	If there are other elements above this position b(Or multiple elements in the form of a linked list),Compare elements a And elements b of Hash value:
		If Hash If the value is different, the element a Added successfully---->Situation 2
		If Hash The value is the same, and then the element needs to be called a Class equals()method:
			equals()return true,element a Add failed
			equals()return false,Then element a Added successfully---->Situation 3
For case 2 and case 3 of successful addition:element a And the data already existing at the specified index location are stored in the form of linked list
jdk7:element a Put it in the array and point to the original element
jdk8:The original element is in the array and points to the element a

Conclusion: seven up and eight down(stay jdk8 Put the new element on top)
HashSet bottom:array+Linked list
Requirements for adding elements

The class of the element added to the Set interface must override the equals() method and the HashCode() method

Requirements for rewriting methods

The overridden equals() method and HashCode() method are as consistent as possible: equal objects must have equal hash codes (i.e., hash values)
Tip for rewriting two methods: the properties in the object used for the equals() method comparison: both should be used to calculate the hash value
Try to make the hash values of two objects equal when their properties are equal
When their hash values are equal, their properties are equal

Implementation class of Set interface


The basic principle of rewriting the hashCode() method is that when the program runs, the same object should return the same value when calling the hashCode() method multiple times.
When the equals() method of two objects returns true, the return value of the hashCode() method of the two objects should also be equal. Object as
The fields compared by the equals() method should be used to calculate the hashCode value.


1. As a subclass of HashSet, while adding data, each data also maintains two references to record the previous data and the next data of this data
2. LinkedHashSet determines the storage location of elements according to the hashCode value of elements, but it also uses a two-way linked list to maintain the order of elements, which makes the elements appear to be saved in insertion order.
3. The insertion performance of linkedhashset is slightly lower than that of HashSet, but it has good performance when iteratively accessing all elements in the Set.
4. LinkedHashSet does not allow duplicate set elements. Advantages: for frequent traversal operations, LinkedHashSet is more efficient than HashSet
5. When traversing internal data, it can be traversed in the order of addition


Cannot put the same data

TreeSet and TreeMap adopt the storage structure characteristics of red black tree: orderly, and the query speed is faster than List
If the data put into TreeSet comes out of the same class new, we can sort according to some attributes of the object
The default is to sort from small to large

The data added to the TreeSet must be objects of the same class

Natural sorting

Implement Comparable interface
Override compareTo method

In natural sorting, the standard for comparing whether two objects are the same is: compareTo() returns 0, no longer equals()

Custom sorting

Implement Comparator interface
Override compare method

Map interface

Structure of Map implementation class

/---Map:Storing dual column data key-value data   ---Functions similar to those in high school
	/---HashMap:As Map The main implementation class, thread unsafe, high efficiency, can be stored key and value All null Data
		/---LinkedHashMap:HashMap Add a pair of pointers on the original basis to point to the previous element and the latter element to form a linked list structure, which can ensure the traversal Map Elements can be traversed in the order we add them
		For frequent traversal operations, this kind of pointing is more efficient than HashMap
   /---TreeMAp:It can be guaranteed to follow the added key-value Sort and realize sorting traversal according to key To sort
   					Consider at this time key Natural sorting or custom sorting
               Red and black trees are used at the bottom
   /---Hashtable:As an ancient implementation class, thread safety, low efficiency, can not be stored null(key and value One of them is null Not at all)
   		/---Properties:Commonly used to process configuration files. key and value All String type
  HashMap Bottom layer of: array+Linked list( jdk7 (before)
                  array+Linked list+Red black tree( jdk8)

Understanding of Map structure

   We know Map Similar to the function in high school, so Map Medium key Cannot repeat
1.Map Medium key:Disordered and unrepeatable, using Set Store all key  --->Key The class to be overridden equals Methods and HashCode Method (in) HashMap For example) because of the stored key It may be our custom class
2.Map Medium value:Repeatable, unordered, using Collection Store all value---->value The class to be overridden equals method
3.A key value pair: key-value Constitutes a Entry Object, in computer Map Storage is to save one Entry Object instead of storing two values key and value,Instead, the two data are encapsulated together
4.Map Medium entry:Out of order, not repeatable, used Set Store all entry

In fact, the data in the Map is one by one. Each data is an entry. There are two attributes in the entry, a key and a value. The data in the entry is out of order and cannot be repeated, because the key is out of order and cannot be repeated. A key corresponds to a value

Underlying implementation principle of HashMap

Take JDK7 as an example

HashMap map=new HashMap();
After instantiation, the bottom layer creates a one-dimensional array Entry[] table with a length of 16
First, call the HashCode method of the class where key1 belongs to calculate the hash value of key1, and then calculate according to some algorithm to get the storage location in the entry array.
If the location data is empty, key1-value1 is added successfully - Case 1
If the location data is not empty (indicating that there are one or more data in this location (in the form of linked list)), compare the hash value of key1 and one or more existing values:
If the hash value of key1 is different from the hash value of existing data, key1-value1 is added successfully - Case 2
If the hash value of key1 is the same as that of an existing data (key2-value2), continue the comparison, call the equals method of the class where key1 is located, and compare:
If the equals method returns false, key1-value1 is added successfully – case 3
If the equals method returns true: use value1 to replace the data value value2 of the same key

Add: for case 2 and case 3:
At this time, key1-value1 and the original data exist in the form of linked list
In the process of continuous addition, the problem of capacity expansion will be involved: when the critical value is exceeded (and its storage location is not empty), the default capacity expansion method is to double the original capacity and copy the original data

JDK8. Differences between 0 and JDK7

1.  new HashMap();//The underlying layer did not create an array with a length of 16
2.  JDK8 Underlying array: Node[],no Entry[]
3.  JDK8 First call put Method, the underlying layer creates an array with a length of 16
4.  JDK7 The underlying structure has only arrays+Linked list   JDK8 Middle and bottom structure: array+Linked list+Red black tree is the number of data in the form of linked list when the element at a certain position of the array exists=8,And the length of the current array>64,At this time, all data in the index position is stored in red black tree to facilitate data search

Loading factor: 0.75


It can make the output order the same as the order we added, because the underlying layer has before and after attributes, which are used to record who is the last and next person to add an Entry and the order of added elements

Common methods of Map interface

 public void test1(){
  Map map=new HashMap<>();
  map.put("BB",12 );
  map.put( 156,78);

  Map map1=new HashMap();
  //remove returns null if the corresponding key is not found
  Object value = map.remove("cc");
//Clear clear element  


Traversal method of Map

 public void test2(){
  Map map=new HashMap<>();
  map.put("BB",12 );
  map.put( 156,78);
   * Traverse all key s

  Set set = map.keySet();
  Iterator iterator = set.iterator();
  while (iterator.hasNext()) {
   Object next =;

  * Map Traversal of
 public void test2(){
  Map map=new HashMap<>();
  map.put("BB",12 );
  map.put( 156,78);
   * Traverse all key s

  Set set = map.keySet();
  Iterator iterator = set.iterator();
  while (iterator.hasNext()) {
   Object next =;

   * Traverse all value sets
  Collection values = map.values();
  Iterator iterator1 = values.iterator();
  while (iterator1.hasNext()) {
   Object next =;


   * Traverse key and value
   * Mode 1:
  Set entrySet = map.entrySet();
  Iterator iterator2 = entrySet.iterator();
  while (iterator2.hasNext()){
   //At this time, obj is of type entry
   //All elements in the entry set collection are entries
   Map.Entry entry=(Map.Entry)obj;

   * Method 2: first traverse all keys and obtain value through key
  Set set1 = map.keySet();
   Iterator iterator3=set1.iterator();
   while (iterator3.hasNext()){

    //Get key
    Object next =;



Collections utility class

Tool classes for manipulating Collection and Map


import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

 * CollectionsTest It is a tool class for operating Colletion and Map
 * Interview question: the difference between Collection and Collections
 * @author zengyihong
 * @created 2021-09-18 14:52
public class CollectionsTest {
     *reverse(list); Reverse the order of elements in the List
     *shuffle(list): Random sorting of List collection elements
     *sort(list):Sort the elements of the specified list set in ascending order according to the natural sorting of the elements
     *swap(list,int,int):Interchange the elements at i and j in the specified List collection
     *Object max(Collection):Returns the largest element in a given set based on the natural ordering of elements
     *Object max(Collection,Comparator):Returns the largest element in a given collection in the order specified by the Comparator
     *Object min(Collection)
     *int frequency(Collection,Object):Returns the number of occurrences of the specified element in the specified collection
     *void copy(List dest,List src):Copy the contents of src to dest
     *boolean replaceAll(List list,Object newVal):Replace the old value in the List with the new value
     *Collections Class provides multiple synchronizedXxx() methods,
     *This method can wrap the specified set into a thread synchronized set, which can solve the problem
     * Thread safety in multithreaded concurrent access to collections

    public void test1(){

        List list=new ArrayList();

      //  Collections.reverse(list);  Reverse the order of elements in the list
        //shuffle(list) randomly sorts the elements of the list set

        //Exception: Java lang.IndexOutOfBoundsException: Source does not fit in dest

//        List dest=new ArrayList();
//        Collections.copy(dest,list);

        List dest= Arrays.asList(new Object[list.size()]);



Keywords: Java Back-end set

Added by discombobulator on Fri, 25 Feb 2022 18:39:33 +0200