Surpass Day23 – Java Map interface, HashMap interface, HashCode collection, Properties class, TreeSet collection

Table of contents

1. About the Map interface

1.1 About the Map interface

1.2 Commonly used methods in the Map interface

1.3 Traversing the Map collection

2. HashMap collection

2.1 About the HashMap collection

2.2 Features of the key part of the HashMap collection

2.3 Improper use of HashMap HashMap cannot exert its performance

2.4 Implementation principle of map.put(k,v)

2.5 v = map.get(k) implementation principle

2.6 Initialization and expansion of HashMap collection

2.7 Rewrite of euquals and hashCode

3, HashCode set

4. Properties class

5, TreeSet set

5.1 About the TreeSet collection

5.2 Sorting method: implement the Comparable interface

5.3 Binary tree data structure

5.4 Sorting Mode: Implementing the Comparator Comparator Interface

5.5 Selection of Comparable Interface and Comparator Comparator Interface

6. Collections tool class

  1. Map interface

1.1 About the Map interface

1) MapCollection has no inheritance relationship.

2) The Map [collection] The Map [collection] stores data in the form of keys and values: key-value pairs

Both key and value are reference data types.

Both key and value are memory addresses where objects are stored.

The key plays a dominant role, and the value is an accessory of the key

1.2 Common methods in the Map interface

V put (K key, V value) adds key-value pairs to the Map collection

V get(Object key) Get value by key

void clear() clears the Map collection

boolean containsKey(Object key) Determines whether the Map contains a key

boolean containsValue(Object value) Determines whether the Map contains a value

boolean isEmpty() Determines whether the number of elements in the Map collection is e

Set keySet() Get all the keys of the Map collection (all keys are a set collection)

V remove(Object key) delete key-value pair by key

int size() Get the number of key-value pairs in the Map collection.

Collection values() Get all the values ​​in the Map collection and return a Collection

Set >entrySet() Convert Map collection to set collection

Note: About converting Map collection to set collection Set>entrySet()

Suppose we now have a Map collection as follows:

// Create a Map collection object
Map<Integer, String> map = new HashMap<>();
// Add key-value pairs to the Nap collection
map .put( 1 , "zhangsan" ); // 1 is automatically performed here Boxed.
map .put( 2 , "lisi" );
map .put( 3 , "wangwu" );
map .put( 4 , "zhaoliu" );
// Get value by key
String value = map .get( 2 );
System.out.println(value);
//Get the number of key-value pairs
System.out.println( "Number of key-value pairs: " + map .size());|
// Delete key-value by key
map .remove(key: 2 );
System.out.println( "Number of key-value pairs: " + map .size());
// Determine whether a key is included
// The contoins method calls all equals for comparison, so custom Types need to override the equals method.
System.out.println(imap.containsKey( new Integer( value: 4 ))); // true
//Determine whether a value is included
System.out.println( map .containsValue( new String( original: "wangwu" ) )); // trud

//Get all values
​​Collection<String> values ​​= map .value();
for (String s:values){
   System.out.println(s);
}
//Clear the Map collection
map .clear();
System.out.println( "Number of key-value pairs: " + map .size());

Set set = map1.entrySet();

Map<Integer, String> map = new MashMap<>(); map .put( 1 , "zhangsan" ); map .put( 2 , "1isi" ); map .put( 3 , "wangwu" ); map . put( 4 , "zhaoliu" ); //Welcome the Nap set //Get all the keys, all keys are a 5et set Set<Integer> keys = map .keySet(); //Traverse the keys and get the keys value //The selector can Iterator<Integer> it = keys.iterator(); ​ ​ //Iterator traverses while (it.hasNext())( // Take out one of the keys Integer key = it.next(); // Get value by key String value = map .get(key); System.out.println(key + "=" + value); }</p> <p>//foreach loop through for (Integer key:keys){    System.out.println(key + "=" +map.get(key)); }

Entry is a static inner class in Map

//Convert all Map collections directly into Set collections. 
// The type of elements in the Set collection is: Map.Entry 
Set < Map .Entry<Integer, String >> set = map.entrySet();
// Traverse the set collection, taking out a Node each time
​
​
// iterator traverse
Iterator<Map.Entry<Integer,String>> it2 = set.iterator(>;
while(it2.hasNext()){
    Map.Entry<Integer,String> node = it2.next();
    Integer key = node.getkey();
    String value = node.getValue();
    System.out.println(key + "=" + value);
}
                                                       
// foreach
for(Map.Entry<Integer,String> node : set){
    System.out.println(node.getkey() + "---y" + node.getValue());
}

1.3 Traverse the Map collection

The first way: get all the keys, traverse the value by traversing the key

public  class  HashMap {
     //The bottom layer of HashMap is actually an array. (one-dimensional array)
    Node<K,V>[] table;
    //Static inner class HashMap.Node 
    static  class  Node < K , V > {
         final  int hash; // Hash value (the hash value is the execution result of the key's hashCode() method. The hash value is passed through the hash function/algorithm The subscript that can be converted into an array 
        final K key; // the key stored in the Map collection 
        v value; // the value stored in the Map collection 
        Node<K,V> next; //The memory address of the next node .
    }
}

The second way: Set>entrySet() [high efficiency]

//Test the element characteristics of the key part of the HashMap collection 
//Integer is the key. Both his euquals and hashCode rewrite 
import java.util.*;
​
public class java{
    public static void main(String[] args) {
        Map<Integer,String> map = new HashMap<>();
         map .put( 1111 , "zahngsan" );
         map .put( 2222 , "wusan" );
         map .put( 3333 , "lisi" );
         map . put( 1111 , "sadasd" ); //When the key is repeated, the value will automatically override 
        System.out.println( map .size());
        Set<Map.Entry<Integer,String>> set = map.entrySet();
        for(Map.Entry<Integer,String> entry : set){
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }
    }
}
​

2. HashMap collection

2.1 About the HashMap collection

1) The bottom layer of the HashMap collection is the data structure of the hash table/hash table.

2) What kind of data structure is a hash table?

public class HashMapTest02 { public static void main(String[] args){ Student s1 = new Student( name: "zhangsan"); Student s2 = new Student( name: "zhangsan");</p> <pre><code> //false before overriding the equals method //System.out.println(s1.equals(s2)); // false //After overriding the equals method is true System.out.println ( s1.equals ( s2)); //true (s1 and s2 are equal) System.out .println ( "s1's hashCode=" + s1.hashCode()); //284720968 System.out .println ( " s2's hashCode=" +s2.hashCode()); // 122883338 //s1. The result of equals (s2) is already true, indicating that s1 and s2 are the same, the same, then if you put it in the HashSet collection, //It is said that only one can be put in. (HashSet collection features: unordered and non-repeatable) Set<Student> students = new HashSet<>(); students.add(s1); students.add(s2);System.out .println (students.size()); //This result is supposed to be 1. But the result is 2. Obviously it does not conform to the HashSet collection storage characteristics, so the equals and HashCode methods must be rewritten </code></pre> <p>} }

4) The source code of the underlying HashMap collection:

public  class  PropertiesTeste1 {
     public  static  void  main ( String[] args ) {
         // create a small properties object 
        Properties pro = new Properties();
         // save the properties 
        pro.setProperty( "ur1" , "jdbc:mysq1:// localhost:3306/bjpovernode" );
        pro.setProperty("driver","com.mysq1.jdbc.Driver");
        pro.setProperty("username","root");
        pro.setProperty("password", "123");
        
        // Get value by key 
        String url = pro.getProperty( "ur1" );
        String driver = pro.getProperty("driver");
        String username = pro.getProperty("username");
        String password = pro.getProperty("password");
        
        System.out.println(url);
        System.out.println(driver);
        System.out.println(username);
        System.out.printIn(password);l
    }
}

Hash table/Hash table: One-dimensional array, each element in this array is a singly linked list. (A combination of array and linked list.)

5) After JDK8, if the hash table has more than 8 elements in the linked list, the data structure of the singly linked list will become a red-black tree data structure.

When the number of nodes on the red-black tree is less than 6, the red-thinking tree will be re-transformed into a singly linked list data structure.

[Increase efficiency, the retrieval of binary tree will narrow the scanning range again]

6) 5. For the hash table data structure:

[If the hash] values ​​of o1 and o2 are the same, they must be placed on the same singly linked list.

Of course, if the hash values ​​of o1 and o2 are different, but since the converted array subscripts after the execution of the hash algorithm may be the same, “hash collision” will occur at this time.

7) HashMap allows the key part to be empty, but the null value can only be one

2.2 Features of the key part of the HashMap collection

Unordered and non-repeatable.

Why out of order? Because it is not necessarily linked to which singly linked list.

Why can’t it be repeated? The equals method is used to ensure that the keys of the HashMap collection are not repeatable. If the key is duplicated, the value will be overwritten.

The elements placed in the key part of the HashMap collection are actually placed in the HashSet collection.

So the elements in the HashSet collection also need to override the hashCode()+equals() method at the same time.

2.3 Improper use of HashMap HashMap cannot exert performance

Assuming that all the return values ​​of the hashCode() method are fixed to a certain value, it will cause the underlying hash table to become a pure singly linked list.

In this case we become: the hash distribution is uneven.

1) What is uniform hash distribution?

Suppose there are 100 elements, 10 singly linked lists, then there are 10 nodes on each singly linked list, which is the best, the hash distribution is uniform.

Assuming that all the return values ​​of the hashCode() method are set to different values, the underlying hash table will become a one-dimensional array, and there is no concept of a linked list. Also the hash distribution is uneven.

So evenly distributed hash requires some tricks when overriding the hashCode() method.

2) Why are the random additions and deletions of the hash table and the query efficiency very high? Additions and deletions are done on linked lists. The query also does not need to be scanned all, only part of it.

Important : The key of the HashMap collection will call two methods successively, one is hashCode0 and the other is equals0, then both methods need to be rewritten.

2.4 Implementation principle of map.put(k,v)

The first step : first encapsulate k, v into Node objects.

Step 2 : The bottom layer will call the hashCode() method of k to get the hash value,

Convert the hash value to the subscript of the array through the hash function/hash algorithm. If there is no element at the subscript position, add Node to this position.

If there is a linked list at the position corresponding to the subscript, then equals will be performed with k and k in each node on the linked list,

If all equals methods return false, then the new node will be added to the end of the list.

If one of the equals returns true, then the value of this node will be overwritten.

2.5 v = map.get(k) implementation principle

First call the hashCode() method of k to get the hash value, convert it into an array subscript through the hash algorithm, and quickly locate it to a certain position through the array subscript.

If there is nothing at this position, return nul;

If there is a singly linked list at this position, it will take the parameter k and k in each node on the singly linked list for equals,

If all equals methods return false, then the get method returns null, as long as there is a node’s k and parameter k equals, it returns true,

Then the value of this node at this time is the value we are looking for, and the get method finally returns the value we are looking for.

java.long.ClossCastException:
    class com.bjpowernode.javase.collection.Person
    cannot be cast to class java.Lang.Comparable

2.6 Initialization and expansion of HashMap collection

The default initialization capacity of the HashMap collection is 16, and the default load factor is 0.75

This default load factor is that when the capacity of the underlying array of the HashMap collection reaches 75%, the array begins to expand to twice the original size.

Highlights:

The initial capacity of the HashMap collection must be a multiple of 2 , which is also officially recommended.

This is necessary to improve the access efficiency of the HashMap collection to achieve uniform hashing.

2.7 Rewrite of euquals and hashCode

import java.util.TreeSet;
public class TreeSetTest04 {
    public static void main(String[] args){
        Customer c1 = new Customer( age: 32);
        Customer c2 = new Customer( age: 20);
        Customer c3 = new Customer( age: 30);
        Customer c4 = new Customer( age: 25);
        
        // Create a TreeSet collection 
        TreeSet<Customer> customers = new TreeSet<>();
         //Add elements
        customers.add(c1);
        customers.add(c2);
        customers.add(c3);
        customers.add(c4);
        //traverse 
        for (Customer c : customers){
            System.out.println(c);
        }
    }
}
//The elements placed in the TreeSet collection need to implement the java.lang.Comparable interface. 
//And implement the compareTo method oequals can not be written. 
class  Customer  implements  Comparable < Customer > {
     int age;
     public  Customer ( int age) {
         this .age = age;
    }
    //Need to write the logic of comparison in this method, or the rules of comparison, according to what to compare! 
    // k.compareTo(t.key) 
    //Compare the parameter k with each k in the set, the return value may be >e<e=e 
    //The comparison rule is ultimately specified by the programmer: for example, according to Age in ascending order. Or in descending order by age. 
@Override 
    public  int  compareTo (Customer c)  { // cl.compareTo(c2); 
    // this is c1 
    //c is c2 
    //When c1 and c2 are compared, this is compared with c. 
        /*int age = this.age;
        int age2 = c.age;
        if(agel == age2){
        return 0;
        } else if(agel > age2){
            return 1;
        } else.{
            return -1;
        }*/
        //return this.age - c.age; // =0 >0 <0
        return c.age - this.age;
        
        //The return value of the compareTo method is very important: 
        //Return e means the same, value will be overwritten. 
        //Return > 0, will continue to search on the right subtree. [10-9=1, 1>0 indicates that the number on the left is relatively large. So find it in the right subtree. 
        //Return <0, will continue to find on the left subtree.
        
    }
    public String toString(){
        return "Customer[age="+age+"]";
    }
}

1) Note :

If a class’s equals method is overridden, then the hashCode() method must be overridden. And if the equals method returns true, the value returned by the hashCode() method must be the same.

The equals method returns true to indicate that the two objects are the same and are compared on the same singly linked list. Then for nodes on the same singly linked list, their hash values ​​are the same.

So the return value of hashCode() method should also be the same.

2) How to rewrite?

Generate directly using IDEA tools, but these two methods need to be generated at the same time.

3) Final conclusion:

The elements placed in the key part of the HashMap collection and elements in the HashSet collection need to override both the hashCode method and the equals method.

3, HashCode set

Hashtable does not allow key and value parts to be empty, a null pointer exception will occur

Hashtable methods come with synchronized: thread-safe. There are other solutions for thread safety. This Hashtable’s processing of threads leads to lower efficiency and less use.

HashMap and Hashtable are both hash tables at the bottom

The initial capacity of Hashtable is 11, the default load factor is 0.75, the expansion is 2 times plus one

4. [Properties] class

At present, only the relevant methods of the properties attribute class object are required.

Properties is a Map collection that inherits Hashtable. The key and value of Properties are of type string.

Properties are called property class objects.

Properties are module safe.

public  class  TreeSetTest06  {
     public  static  void  main (String[] args)  {
         //When creating a TreeSet collection, you need to use this comparator. 
        //TreeSet<wuGui>wuGuis=new TreeSet<>();//This doesn't work, no comparator is passed in through the constructor.
        
        // Pass a comparator to the constructor. 
        TreeSet<WuGui> wuGuis = new TreeSet<>( new WuGuiComparator());
       
        
        wuGuis.add( new WuGui( age: 1000 ));
        wuGuis.add( new WuGui( age: 800 ));
        wuGuis.add( new WuGui( age: 810 ));
        
        for (WuGui wuGui : wuGuis){
            System.out.println(wuGui);
        }
    }
}
​
class WuGui {
    int age;
    public WuGui(int age){
        this.age = age;
    }
    @Override 
    public String toString ()  {
         return "Turtle[" +
                 "age=1" + age +
                 ']' ;
    }
}
​
//Write a comparator here alone 
//The comparator implements the java.util.Comparator interface. (Comparable is under the java.lang package. Comparator is under the java.util package.) 
class  WuGuiComparator  implements  Comparator < WuGui > {
     @Override 
    public  int  compare (WuGui o1, WuGui o2)  {
         //Specify comparison rules 
        //According to age sort 
        return o1.age - o2.age;
    }
}

5, TreeSet set

5.1 About the TreeSet collection

1) The bottom layer of the TreeSet collection is actually a TreeMap

2) The bottom layer of the TreeMap collection is a binary tree.

3) The elements placed in the TreeSet collection are equivalent to the key part of the TreeMap collection.

4) Elements in the TreeSet collection: unordered and non-repeatable, but can be automatically sorted according to the size order of the elements. Called: Sortable Collection.

5.2 Sorting: Implementing the Comparable interface

Custom types cannot be sorted because no comparison principle between objects is specified. There is no indication of who is older and who is younger.

When the program runs, this exception occurs:

public class CollectionsTest {
    public static void main(String[] args){
        
        // ArrayList collections are not thread safe. 
        List<String> list = new ArrayList<>();
        
        //become thread-safe 
        Collections.synchronizedlist( list );
        
        list.add("abf");
        list.add("abx");
        list.add("abc");
        list.add("abe");
        Collections.sort(list);
        for(String s : list){
            System.out.println(s);
        }
        
        List<WuGui> wuGuis = new ArrayList<>();
        wuGuis.add( new WuGui( age: 1000 ));
        wuGuis.add( new WuGui( age: 8000 ));
        Collections.sort(wuGuis); //To sort the elements in the List collection, you need to ensure that the elements in the List collection implement the Comparable interface 
        for (WuGui wg : whGuis){
            System.out.println(wg);
        }
}
​
class WuGui implements Comparable<WuGui>{
    int age;
    public WuGui(int age){ this.age = age; }
    
    @Override
    public int compareTo(WuGui o){
        return this.age - o.age;
    }
    
    @Override
    public String |toString() {
        return "WuGui2{" +
                "age=" + age +
                '}';
    }
}
    
    //How to sort the Set collection? 
    Set<String> set = new HashSet<>();
     set .add( "king" );
     set .add ( "kingsoft" );
     set .add ( "king2" );
     set .add ( "king1" );
     / /Convert set collection to List collection 
    List<String> myList = new ArrayList<>( set );
    Collections.sort(myList);
    for(String s :myList){
        System.out.println(s);
        //Collections.sort(l positive st collection, comparator object);
    }
}

The reason for this exception is: the custom class does not implement the java.Lang.Comparable interface.

import java.util.TreeSet;
public class TreeSetTest04 {
    public static void main(String[] args){
        Customer c1 = new Customer( age: 32);
        Customer c2 = new Customer( age: 20);
        Customer c3 = new Customer( age: 30);
        Customer c4 = new Customer( age: 25);
        
        // Create a TreeSet collection 
        TreeSet<Customer> customers = new TreeSet<>();
         //Add elements
        customers.add(c1);
        customers.add(c2);
        customers.add(c3);
        customers.add(c4);
        //traverse 
        for (Customer c : customers){
            System.out.println(c);
        }
    }
}
//The elements placed in the TreeSet collection need to implement the java.lang.Comparable interface. 
//And implement the compareTo method oequals can not be written. 
class  Customer  implements  Comparable < Customer > {
     int age;
     public  Customer ( int age) {
         this .age = age;
    }
    //Need to write the logic of comparison in this method, or the rules of comparison, according to what to compare! 
    // k.compareTo(t.key) 
    //Compare the parameter k with each k in the set, the return value may be >e<e=e 
    //The comparison rule is ultimately specified by the programmer: for example, according to Age in ascending order. Or in descending order by age. 
@Override 
    public  int  compareTo (Customer c)  { // cl.compareTo(c2); 
    // this is c1 
    //c is c2 
    //When c1 and c2 are compared, this is compared with c. 
        /*int age = this.age;
        int age2 = c.age;
        if(agel == age2){
        return 0;
        } else if(agel > age2){
            return 1;
        } else.{
            return -1;
        }*/
        //return this.age - c.age; // =0 >0 <0
        return c.age - this.age;
        
        //The return value of the compareTo method is very important: 
        //Return e means the same, value will be overwritten. 
        //Return > 0, will continue to search on the right subtree. [10-9=1, 1>0 indicates that the number on the left is relatively large. So find it in the right subtree. 
        //Return <0, will continue to find on the left subtree.
        
    }
    public String toString(){
        return "Customer[age="+age+"]";
    }
}

5.3 Binary tree data structure

1) TreeSet/TreeMap is a self-balancing binary tree. Store in accordance with the principle of left small and right large.

2) There are three ways to traverse a binary tree:

Storage is to rely on the principle of left small and right big, so this storage should be compared.

Preorder traversal: around the root

Inorder traversal: left root right

Postorder Traversal: Left and Right Roots

Note : The front, middle, and back refer to the location of the “root”. The root in the front is the preorder, the root in the middle is the inorder, and the root in the back is the postorder.

3) The TreeSet collection / TreeMap collection adopts the in-order traversal method.

Iterator iterators use in-order traversal. Left and right.

4) 100 200 50 60 80 120 140 130 135 180 666 .40 55

5) Use in-order traversal to take out:

40 50 55 60 80 100 120 130 135 140 180 200 666

The process of storage is the process of sorting. Taken out is automatically arranged in order of size.

5.4 Sorting Mode: Implementing the Comparator Comparator Interface

public  class  TreeSetTest06  {
     public  static  void  main (String[] args)  {
         //When creating a TreeSet collection, you need to use this comparator. 
        //TreeSet<wuGui>wuGuis=new TreeSet<>();//This doesn't work, no comparator is passed in through the constructor.
        
        // Pass a comparator to the constructor. 
        TreeSet<WuGui> wuGuis = new TreeSet<>( new WuGuiComparator());
       
        
        wuGuis.add( new WuGui( age: 1000 ));
        wuGuis.add( new WuGui( age: 800 ));
        wuGuis.add( new WuGui( age: 810 ));
        
        for (WuGui wuGui : wuGuis){
            System.out.println(wuGui);
        }
    }
}
​
class WuGui {
    int age;
    public WuGui(int age){
        this.age = age;
    }
    @Override 
    public String toString ()  {
         return "Turtle[" +
                 "age=1" + age +
                 ']' ;
    }
}
​
//Write a comparator here alone 
//The comparator implements the java.util.Comparator interface. (Comparable is under the java.lang package. Comparator is under the java.util package.) 
class  WuGuiComparator  implements  Comparator < WuGui > {
     @Override 
    public  int  compare (WuGui o1, WuGui o2)  {
         //Specify comparison rules 
        //According to age sort 
        return o1.age - o2.age;
    }
}

5.5 Selection of Comparable Interface and Comparator Comparator Interface

There are two ways to sort the elements placed in the key part of the TreeSet or TreeMap collection:

The first: the elements placed in the collection implement the java.lang.Comparable interface.

The second: pass a comparator object to it when constructing a TreeSet or TreeMap collection.

How to choose Comparable and Comparator?

When the comparison rule does not change, or when there is only one comparison rule, it is recommended to implement the Comparable interface.

If there are multiple comparison rules and frequent switching between multiple comparison rules is required, it is recommended to use the Comparator interface.

The design of the Comparator interface conforms to OCP principles.

6. Collections tool class

java.util.Collection collection interface

The java.util.Collections collection tool class is convenient for collection operations.

public class CollectionsTest {
    public static void main(String[] args){
        
        // ArrayList collections are not thread safe. 
        List<String> list = new ArrayList<>();
        
        //become thread-safe 
        Collections.synchronizedlist( list );
        
        list.add("abf");
        list.add("abx");
        list.add("abc");
        list.add("abe");
        Collections.sort(list);
        for(String s : list){
            System.out.println(s);
        }
        
        List<WuGui> wuGuis = new ArrayList<>();
        wuGuis.add( new WuGui( age: 1000 ));
        wuGuis.add( new WuGui( age: 8000 ));
        Collections.sort(wuGuis); //To sort the elements in the List collection, you need to ensure that the elements in the List collection implement the Comparable interface 
        for (WuGui wg : whGuis){
            System.out.println(wg);
        }
}
​
class WuGui implements Comparable<WuGui>{
    int age;
    public WuGui(int age){ this.age = age; }
    
    @Override
    public int compareTo(WuGui o){
        return this.age - o.age;
    }
    
    @Override
    public String |toString() {
        return "WuGui2{" +
                "age=" + age +
                '}';
    }
}
    
    //How to sort the Set collection? 
    Set<String> set = new HashSet<>();
     set .add( "king" );
     set .add ( "kingsoft" );
     set .add ( "king2" );
     set .add ( "king1" );
     / /Convert set collection to List collection 
    List<String> myList = new ArrayList<>( set );
    Collections.sort(myList);
    for(String s :myList){
        System.out.println(s);
        //Collections.sort(l positive st collection, comparator object);
    }
}

Leave a Comment

Your email address will not be published. Required fields are marked *