Collection / container

aggregate / Containers

Set concept

• When we need to save a group like （ The same type ） Of the elements , We should use a container to store , An array is such a container . however , Once an array is defined , The length will no longer change .

• However, in our development practice , It is often necessary to save some variable length data sets , therefore , We need something that can Dynamic growth Long containers to hold our data .

• The logic we need to save data may be various , So there are all kinds of data structures

  structure .Java Implementation of various data structures in , Is the set we use .

Collection system overview

• Java The collection framework consists of many interfaces 、 abstract class 、 Composed of concrete classes , All in java.util In bag .

Collection Interface

• Collection Interface － Defines how to access a set of objects , Its sub interfaces Set and List Storage methods are defined respectively .
  • Set The data objects in have no order and cannot be repeated .
  • List The data objects in are sequential and repeatable .
• stay Collection Some common methods in the set are defined in :

boolean addAll(Collection c);// Set c Add to the specified collection 

boolean remove(Object element);// Delete the specified element in the collection 

boolean removeAll(Collection c);// Delete specified collection   When not included , Delete intersection   The elements of 
void clear();// Empty all elements in the collection .

int size();// The number of elements in the collection 

boolean isEmpty();// Determines if the set is empty 

boolean contains(Object element);// Determines whether the collection contains the specified elements 

boolean containsAll(Collection c);// Used to detect  arraylist  Whether to include all elements in the specified collection .

boolean retainAll(Collection c);// Find the intersection , When the set data changes, it returns true,  Return unchanged false

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class CollectionDemo {
    
    public static void main(String[] args) {
    
        Collection<String> collection = new ArrayList<String>();
        collection.add("abcd");
        collection.add("efg");
        collection.add("hijk");
        collection.add("lmn");
        System.out.println(collection);
        //collection.clear(); Clean up all data 
        collection.remove("abcd");
        System.out.println(" Does it include "+"abcd? "+collection.contains("abcd"));
        System.out.println(collection);
        System.out.println(collection+" The length of is ："+ collection.size());
        System.out.println(collection+" Is it empty ？"+collection.isEmpty());

        Object []  strings1 = collection.toArray();
        System.out.println(Arrays.toString(strings1));
        String [] strings2 = collection.toArray(new String[collection.size()]);// The bottom layer is array replication 
        System.out.println(Arrays.toString(strings2));
        System.out.println("\n");
        Collection<String> c = new ArrayList<>();
        c.add("a");
        c.add("b");
        c.add("c");
        c.add("d");
        Collection<String> c1 = new ArrayList<>();
        c1.add("a");
        c1.add("b");
        c1.add("c");
        System.out.println(" take c1 All elements in the collection are added to c in :");
        c.addAll(c1);// take c1 All elements in the collection are added to c in 
        System.out.println(c+"\n"+c1);
        c.removeAll(c1);// Delete c1 stay c All elements in 
        System.out.println(" Delete c1 stay c All elements in  c:"+c);
        System.out.println(" Judge c Include in c1 All the elements in :"+c.containsAll(c1));
        System.out.println(" Retain c And c1 Intersecting elements in , if this When the elements in the set change, it returns true Otherwise return to false "+c.retainAll(c1));
        System.out.println("c:"+c+"\n"+"c1:"+c1);
    }
}

result ：

List Interface and implementation class

• List Inherited Collection Interface , There are three implemented classes
  • ArrayList
    • Data list , The data is stored in array .
  • LinkedList
    • Linked list
  • Vector
    • Array list , Add synchronization lock , Thread safe
• ArrayList Implemented a variable length array , Allocate contiguous space in memory .
• Traversal elements and random access elements are more efficient

• LinkedList Using linked list storage mode . Insert 、 Removing elements is more efficient .

// Nonparametric construction method ：
ArrayList<Object o> alist = new ArrayList<>();

// Parametric construction method ：
ArrayList<Object o> alist = new ArrayList<>(20);// Create a capacity of 20 Set 

//ArrayList The common method of ：
add(E element);// from 0 Start backwards to add elements 
add(int index, E element);// Add data to the specified index element

get(int index); // Get the data of the specified index 

indexOf(Object o); // get data o Index from 0 Start searching backwards 

lastIndexOf(Object o); // get data o The index of is searched forward from the end of the set 

remove(int index);//  Delete and return the specified location element  

removeRange(int fromIndex, int toIndex);//  Delete the element of the specified interval ( Subclass inheritance use ) 

set(int index, E element);

Code testing

public class ArrayListDemo {
    
    public static void main(String[] args) {
    
        ArrayList<String> arrayList1 = new ArrayList<>(20);// Create a capacity of 20 Set 
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("a");
        arrayList.add("a");
        arrayList.add("a");
        arrayList.add("a");
        arrayList.add("bn");
        arrayList.add("a");
        arrayList.add("a");
        arrayList.add("c");
        arrayList.add("a");
        arrayList.add("a");
        arrayList.add("a");
        System.out.println(arrayList.get(2));// Get the elements of the specified index 
        System.out.println(arrayList.indexOf("a")+"\n"+arrayList.indexOf("b"));// Returns the index of the first occurrence of the element , If not, go back -1
        System.out.println();
        System.out.println(" Before deleting "+arrayList);
        arrayList.remove(0);// Delete the elements of the specified index 
        System.out.println(" After deleting "+arrayList);
        arrayList.set(2,"d");// Replace the elements of the specified index 
        System.out.println(" Replace index 2 The element at is  d "+arrayList);
    }
}

result ：

LinkedList The common method of ：
add(int index,Object element)// Add an element to the specified position in the collection 
addFirist(Object element) // Add an element to the collection header 
addLast(Object element) // Add elements to the end of the collection 
get(int index) // Get the collection element of the specified index 
removeFirst() // Delete the collection header element 
removeLast() // Delete the tail element of the set 
remove(int index) // Delete the elements of the specified index 
getFirst() // Get the collection header element 
getLast()// Get the collection tail element 

List Interface set iteration

• Iterator traversal （iterator）

public class IteratorDemo {
    
    public static void main(String[] args) {
    
        ArrayList <String> arrayList = new ArrayList<>();
        arrayList.add("a");
        arrayList.add("a");
        arrayList.add("b");
        arrayList.add("c");
        arrayList.add("d");
        System.out.println(arrayList);
        for(int i=0;i<arrayList.size();i++){
    
            if(arrayList.get(i).equals("a")){
    
                arrayList.remove(i);
                i--;
            }
        }
        System.out.println(arrayList);
        System.out.println();
        System.out.println(" Traversing from front to back ");
        Iterator<String> iterator = arrayList.iterator();// iterator , Traversal only supports from front to back 
        while(iterator.hasNext()){
    
            String s = iterator.next();
            System.out.println(s);
        }

        for(String a:arrayList){
    // Enhancements are not supported for Delete operation in the loop 
            if(a.equals("b")){
    
                arrayList.remove(a);
                break;
            }
        }
        System.out.println(" Go back and forth ");
        ListIterator<String> listIterator = arrayList.listIterator(arrayList.size());
        // You can traverse from front to back , You can also traverse from back to front , But when creating an iterator object, first point the iterator to the next element of the last element of the collection 
        while(listIterator.hasPrevious()){
    
            System.out.println(listIterator.previous());
        }

    }
}

Set Interface

• Set Interface inherited Collection Interface .

  • Set The elements stored in are not repeated , But it's out of order , Set Elements in are not indexed

• Set The interface has two implementation classes .

  • HashSet

    • HashSet Elements in a class cannot be repeated , That is, call each other equals Methods to compare , All back to false.

    • The underlying data structure is the hash table + Linked list

      Hash table depends on hash value storage .

  public class Car {
        
      String name;
      int num;
      public Car(String name,int num){
        
          this.name=name;
          this.num=num;
      }
  
      public String getName() {
        
          return name;
      }
  
      public void setName(String name) {
        
          this.name = name;
      }
  
      public int getNum() {
        
          return num;
      }
  
      public void setNum(int num) {
        
          this.num = num;
      }
          @Override
      public boolean equals(Object o) {
        
          if (this == o) return true;
          if (o == null || getClass() != o.getClass()) return false;
          Car car = (Car) o;
          return num == car.num && name.equals(car.name);
      }
  
      @Override
      public int hashCode() {
        
          return Objects.hash(name, num);
      }
  
      /*  After rewriting these two methods , When Hash stay add when , What is called is the method here , The comparison is the hash value calculated from the content , Although the same as possible , however equals Methods in   When the hash value is the same, it is called to compare the content , If the content is the same, it will be duplicated  */
      @Override
      public String toString() {
        
          return "Car{" +
                  "name='" + name + '\'' +
                  ", num=" + num +
                  '}';
      }
  }
  public class Test {
        
      public static void main(String[] args) {
        
          HashSet<Car> hashSet = new HashSet<>();
          /* Set Interface , Element is not repeatable  HashSet Is chaotic , Calculate the hash value according to the content to store  TreeSet Is ordered  */
  
          Car car = new Car(" BMW 1",300000);
          Car car1 = new Car(" BMW 2",400000);
          Car car2 = new Car(" BMW 3",500000);
          Car car3 = new Car(" BMW 4",600000);
          Car car4 = new Car(" BMW 1",300000);
          hashSet.add(car);
          hashSet.add(car1);
          hashSet.add(car2);
          hashSet.add(car3);
          hashSet.add(car4);
          System.out.println(hashSet);// When not in Car Class equals and hashCode Method will output five , Don't repeat 
          /*  because , No rewriting equals and hashCode When the method is used ,HashSet.add When called by default in Object Of equals and hashcode Method , there hashcode Method is local   Method , Value is the address of the object , Instead of the hash value calculated from the contents of the object , As long as the objects are different ,equals The comparison result of is impossible to be the same , So you can't go heavy  */
      }
  }
  

  • TreeSet
    • You can give Set The elements in the collection are sorted in the specified way . Stored objects must implement Comparable Interface .
    • TreeSet The underlying data structure is a binary tree ( Red black tree is a kind of self balanced binary tree )

  public class User implements Comparable<User>{
        // When you write your own class, you need to add it to TreeSet In the middle of the day , Need to achieve Comparable Interface , Otherwise, type conversion will occur when adding (ClassCastException) error 
      public int num;
      public String name;
      public User (int num,String name){
        
          this.name=name;
          this.num=num;
      }
      /* Why rewrite equals Methods and hashCode Method （ Technology implementation principle ）：  Procedure to HashSet When adding an object to the , First use hashCode Method to calculate the hash code of the object .  Compare ： （1）, If the hash code of the object is inconsistent with the hash code of the object that already exists in the collection , The object does not duplicate other objects , Add to collection ！ （2）, If the same hash code exists in the object , Then through the equals Method to determine whether two objects with the same hash code are the same object （ The standard of judgment is ： Whether the attributes are the same ）*/
      @Override
      public boolean equals(Object o) {
        
          if (this == o) return true;
          if (o == null || getClass() != o.getClass()) return false;
          User user = (User) o;
          return num == user.num && name.equals(user.name);
      }
  
      @Override
      public int hashCode() {
        
          return Objects.hash(num, name);
      }
  
      @Override
      public String toString() {
        
          return "User{" +
                  "num=" + num +
                  ", name='" + name + '\'' +
                  '}';
      }
  
      @Override
      public int compareTo(User o) {
        
          return this.num-o.num;
      }
  }
  
  public class TreeSetDemo {
        
      public static void main(String[] args) {
        
  
          User user1 =  new User(101,"yh1");
          User user2 =  new User(102,"yh2");
          User user3 =  new User(103,"yh3");
          User user4 =  new User(104,"yh4");
          User user5 =  new User(101,"yh1");
  
          /* TreeSet The bottom is still TreeMap  Realized by binary tree , When adding elements, you need to judge the size to choose whether to add the left node or the right node  */
          TreeSet<User> tset = new TreeSet<>();
          tset.add(user3);
          tset.add(user5);
          tset.add(user1);
          tset.add(user4);
          tset.add(user2);
          // enhance for Loop traversal 
          Iterator<User> iterator = tset.iterator();
          for(User a:tset){
        
              System.out.println(a);
          }
          //set Iterator traversal ：
          while(iterator.hasNext()){
        
              System.out.println(iterator.next());
          }
      }
  }
  

Map Interface

• Map Interface Overview

  Objects that map keys to values , A map cannot contain duplicate keys , Each key can be mapped to at most one value .

• Map Interface common methods

• 	V put(K key,V value) // Add key value pairs to the collection key=value
  	V remove(Object key) // according to key Delete corresponding value value 
      void clear() // Empty map aggregate 
      boolean containsKey(Object key) // Determine if there is... In the set key key 
      boolean containsValue(Object value) // Determine if there is... In the set value value 
      boolean isEmpty()// Determines if the set is empty  
      int size() // obtain map Set length 
      V get(Object key) // according to key Key to get the corresponding value value 
      Collection<V> values() // Method call returns   The values contained in this map   Collection view of .
        Hashtable htable = new Hashtable(3); 
        // Add data 
        htable.put(1, "TP");
        htable.put(2, "IS");
        htable.put(3, "THE");
        htable.put(4, "BEST");
        htable.put(5, "TUTORIAL");
        System.out.println(htable.values()); 
  	  // result [TUTORIAL, BEST, THE, IS, TP]
  
      Set<K> keySet() // Method call returns   The key contained in this mapping   Of set View .
        Map<String, String> weakHashMap = new WeakHashMap<String, String>();
        // Add data 
        weakHashMap.put("1", "first");
        weakHashMap.put("2", "two");
        weakHashMap.put("3", "three");
        // return set View 
        Set set = weakHashMap.keySet();
        System.out.println(set);
  		// result [1, 2, 3]
  
      Set<Map.Entry<K,V>> entrySet()// Method call returns   The mapping contained in this mapping   Of set View .
      Hashtable htable = new Hashtable();
        // Add data 
        htable.put(1, "A");
        htable.put(2, "B");
        htable.put(3, "C");
        htable.put(4, "D");
        //  Create view 
        Set nset = htable.entrySet();
        System.out.println(nset); 
  	  // result [4=D, 3=C, 2=B, 1=A]
  

• HashMap

  HashMap Of the elements of key Value cannot be duplicate , The order of arrangement is not fixed , One can be stored as null Key .

  public class HashMapDemo {
        
      public static void main(String[] args) {
        
          /* Map Interface , key , The values correspond to each other   Bonds cannot be repeated , Values can be repeated  */
          HashMap<String,String> map = new HashMap<>();
          /*./1  Disordered sum in storage HashSet equally   Hash structure , Thread unsafe  hash surface + Linked list + Red black tree implementation  */
          map.put("s","s");
          map.put("a","a");
          map.put("c","c");
          map.put("b","a");
          map.put("s","ss");// If the keys are the same , Values are different , Then the value of the key added for the second time will overwrite the value of the key added for the first time ,
          System.out.println(map);// A disorderly , Here it is s==ss,{a=a, b=b, s=ss, c=c}
          // Method ：
  // map.remove("s");// Delete... With the key 
  // System.out.println(map);//{a=a, b=b, c=c}
          System.out.println(map.get("s"));//ss, Get value by key 
          System.out.println(map.containsKey("b"));//true
          System.out.println(map.containsValue("ss"));//true
          Set<String> hset = map.keySet();
          System.out.println(hset);//[a, b, s, c], Store keys in Set Collection , Double chain to single chain 
          
          /*  result ： {a=a, b=a, s=ss, c=c} ss true true [a, b, s, c] */
      }
  }
  

• TreeMap

  TreeMap All the elements in have a fixed order , If you need to get an ordered Map You should use TreeMap,key The class of the value must implement Comparable Interface .

  public class TreeMapDemo {
        
      public static void main(String[] args) {
        
          /* TreeMap The bottom layer is realized by red black tree , also Key The type of must implement Comparable Interface   It can be stored in the natural order of keys  */
          TreeMap<String,String> tset= new TreeMap<>();
          tset.put("s","s");
          tset.put("a","b");
          tset.put("b","d");
          tset.put("aa","ab");
          tset.put("c","c");
          tset.put("s","ss");
          tset.put("x","d");
          System.out.println(tset);
          
          /*  result  {a=b, aa=ab, b=d, c=c, s=ss, x=d} */
      }
  }
  

• HashTable

  Hahstable It is thread safe, but it cannot be stored as null Key value of , Because the obtained hash value is not processed and judged at the bottom

  Only ：int hash = key.hashCode()=>null.hashCode() It's obviously a mistake

Map A collection of traverse

public class EntryDemo {
    
    public static void main(String[] args) {
    
        HashMap<String,String> hset = new HashMap<>();
        hset.put("a","a");
        hset.put("s","s");
        hset.put("s","ss");
        hset.put("b","c");
        hset.put("c","d");
        System.out.println(hset);
        System.out.println("--------------------------");
        //map Traverse 
        // It is equivalent to two operations 
        Set<String> key = hset.keySet();
        for(String a:key){
    
            System.out.println(a+"->"+hset.get(a));
        }
        System.out.println("--------------------------");
        
        //Map The bottom layer is convenient for us to traverse , Store key value pairs in a Entry In the object , Will be multiple Entry Objects in the Set Collection 
        // It is recommended to traverse like this :
        Set<Map.Entry<String,String>> entrySet = hset.entrySet();
        for(Map.Entry<String,String> a:entrySet){
    
            System.out.println(a.getKey()+"->"+a.getValue());
        }
        
         /*  result  {a=a, b=c, s=ss, c=d} -------------------------- a->a b->c s->ss c->d -------------------------- a->a b->c s->ss c->d */
    }
}

Collections class

• Collections It is a tool class of collection class , Tool classes with arrays Arrays similar .

	addAll(Collection<? super T> c, T... elements); 
	binarySearch(List<? extends Comparable<? super T>> list, T key) 
    sort(List<T> list) 
    sort(List<T> list, Comparator<? super T> c) 
    swap(List<?> list, int i, int j) 
    copy(List<? super T> dest, List<? extends T> src) ;  Be careful  dest size Must be greater than or equal to src.size emptyList()  Returns an empty collection , Can't add data  
    fill(List<? super T> list, T obj) 
    max(Collection<? extends T> coll) 
    min(Collection<? extends T> coll) 
    replaceAl l(List<T> list, T oldVal, T newVal) 
    reverse(List<?> list)

public class CollectionsDemo {
    
    public static void main(String[] args) {
    
        /* Colections Tool class , Process the collection , Be similar to Arrays, It contains static methods that operate on collections  */
        ArrayList<String> list = new ArrayList<>();

        Collections.addAll(list,"aa","bb","cc","dd","ee");
        /* int...c  Variable length parameters , The essence is array   There can only be one variable length parameter in a parameter list , And can only be placed at the last place in the parameter list  */
        System.out.println(list);//[aa, bb, cc, dd, ee]
        
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(2);
        list1.add(8);
        list1.add(7);
        list1.add(6);
        list1.add(5);
        list1.add(1);
        list1.add(4);
        list1.add(3);
// Collections.sort(list1);// Sort 1

// Collections.sort(list1, new Comparator<Integer>() {// Sort 2, Anonymous inner class 
// @Override
// public int compare(Integer o1, Integer o2) {
    
// return o1-o2;
// }
// });
        Collections.sort(list1,(o1,o2)->{
    return o1-o2;});// Sort 3,Lambda expression 
        
        System.out.println(Collections.binarySearch(list1,5));// Two points search , Return index location  4

        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(2);
        list2.add(2);
        list2.add(2);
        list2.add(2);
        list2.add(2);
        list2.add(2);
        list2.add(2);
        list2.add(2);
        list2.add(2);
        list2.add(2);
        list2.add(2);
        Collections.copy(list2,list1);// hold list1 Copy the elements of to list2 aggregate , however list2.size() need >=list1.size(), Otherwise, the array out of bounds exception will appear 
        System.out.println(list2);//[1, 2, 3, 4, 5, 6, 7, 8, 2, 2, 2]
        
        Collections.fill(list2,0);// Assemble list2 All filled as 0
        System.out.println(list2);//[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        System.out.println(Collections.max(list1));// return list1 The maximum 8
        
        System.out.println(list1);//[1, 2, 3, 4, 5, 6, 7, 8]
        Collections.reverse(list1);// The reverse 
        System.out.println(list1);//[8, 7, 6, 5, 4, 3, 2, 1]
    }
}