day17_ Under collection

Set below

Learning goals

1. master Map Common classes of set system 
2.Collections Tool class 

One 、Map Interface

1.1 Map Interface Overview

Map And Collection Juxtaposition . Used to save data with mapping relationship :key-value ;Map Medium key and value Can be any reference type of data

Map Medium key use Set To hold the , No repetition , Is the same Map Class corresponding to the object , To be rewritten hashCode() and equals() Method , Commonly used String Class as Map Of “ key ”

key and value There is a one-way one-to-one relationship between , I.e. through the specified key Always find the only 、 affirmatory value

Map Common implementation classes for interfaces ：HashMap、TreeMap、LinkedHashMap and Properties. among ,HashMap yes Map Interface is the most frequently used implementation class

map The bottom design structure is as follows ：

Map Medium key: A disorderly 、 Non repeatable , Use Set Store all key —> key The class in which you want to override equals() and hashCode() （ With HashMap For example ）;Map Medium value: A disorderly 、 Repeatable , Use Collection Store all value —>value The class in which you want to override equals(); A key value pair ：key-value Make up a Entry object .Map Medium entry: A disorderly 、 Non repeatable , Use Set Store all entry

1.2 map Interface common methods

map Common interface methods are as follows ：

• add to 、 Delete 、 Modify the operating ：
  • Object put(Object key,Object value)： Will specify key-value Add to ( Or modify ) At present map In the object
  • void putAll(Map m): take m All in key-value To store to the current map in
  • Object remove(Object key)： Remove the specified key Of key-value Yes , And back to value
  • void clear()： To empty the current map All data in
• Element query operation ：
  • Object get(Object key)： Get specified key Corresponding value
  • boolean containsKey(Object key)： Whether to include the specified key
  • boolean containsValue(Object value)： Whether to include the specified value
  • int size()： return map in key-value The number of right
  • boolean isEmpty()： Judge the present map Is it empty
• Methods of metaview operation ：
  • Set keySet()： Back to all key Composed of Set aggregate
  • Collection values()： Back to all value Composed of Collection aggregate
  • Set entrySet()： Back to all key-value To constitute Set aggregate

1.3 Map Comparison of implementation classes

Map（ Interface ）: Double column data , Storage key-value Right data . His implementation classes differ as follows ：

• HashMap： As Map The main implementation class of ; Thread unsafe , Efficient ; Storage null Of key and value
• LinkedHashMap： As HashMap Subclasses of are guaranteed to traverse map Element time , The traversal can be implemented in the order of addition . reason ： In the original HashMap Based on the underlying structure , Added a pair of pointers , Points to the previous and subsequent elements . For frequent traversal operations , This kind of execution is more efficient than HashMap.
• TreeMap： Make sure to follow the added key-value To sort , Implement sort traversal . Consider... At this time key The bottom layer of natural sorting or custom sorting uses red black tree
• Hashtable： As an ancient implementation class ; Thread safe , Low efficiency ; Can't store null Of key and value, The underlying principles and HashMap Almost the same as .
• Properties： It is often used to process configuration files .key and value All are String type

1.4 HashMap

jdk7 Species HashMap Underlying principle ：

When we create hashMap Object time Map map = new HashMap():

1. After instantiation , The bottom layer creates a length of 16 One dimensional array of Entry[] table.
2. map.put(key1,value1): First , call key1 Of the class hashCode() Calculation key1 Hash value , The hash value is calculated by some algorithm , Get in Entry The storage location in the array . If the data at this location is empty , At this time key1-value1 Add success . ---- situation 1
3. If the data in this location is not empty ,( It means that there is one or more data at this location ( In the form of a linked list )), Compare key1 And the hash value of one or more existing data ： If key1 The hash value of is not the same as the hash value of the existing data , here key1-value1 Add success .---- situation 2
4. If key1 The hash value of and a data that already exists (key2-value2) The hash value of is the same , Continue to compare ： call key1 Of the class equals(key2) Method , Compare ： If equals() return false: here key1-value1 Add success .---- situation 3
5. If equals() return true: Use value1 Replace value2. Situation four
6. Add ： About the situation 2 And circumstances 3： here key1-value1 With the original data One way linked list How to store .
7. In the process of continuous addition , It's about capacity expansion , When the threshold is exceeded ( And the location to be stored is not empty ) when , Capacity expansion . The default expansion method ： Expand to the original capacity 2 times , And copy the original data .

jdk8 Medium hashMap The underlying principle is as follows

1.5 LinkedHashMap Explain in detail

LinkedHashMap yes HashMap Subclasses of

stay HashMap Based on the storage structure , A pair of two-way linked lists are used to record the addition of The order of the elements

And LinkedHashSet similar ,LinkedHashMap Can maintain Map Iteration The order ： Iterative order and Key-Value Pairs are inserted in the same order

1.6 Hashtable Explain in detail

Hashtable It's an old Map Implementation class ,JDK1.0 Provided. . differ HashMap, Hashtable It's thread safe .

Hashtable Realization principle and HashMap identical , Function the same . The bottom layer uses hash table structure , Fast query speed , In many cases, it can be used mutually .

And HashMap Different ,Hashtable Not allowed null As key and value

And HashMap equally ,Hashtable There is no guarantee that Key-Value On the order of

Hashtable Whether two key equal 、 Two value The standard of equality , And HashMap Agreement .

1.7 TreeMap Explain in detail

TreeMap Storage Key-Value Right time , Need basis key-value To sort . TreeMap You can guarantee all of them Key-Value Yeah, in order .

TreeSet The bottom layer uses red black tree structure to store data

TreeMap Of Key Sort ：

• Natural ordering ：TreeMap All of Key Must be realized Comparable Interface , And all Of Key It should be an object of the same class , Otherwise it will be thrown ClasssCastException
• Custom sort ： establish TreeMap when , Pass in a Comparator object , The object is responsible for TreeMap All in key Sort . There is no need for Map Of Key Realization Comparable Interface

TreeMap Whether two key The standard of equality ： Two key adopt compareTo() Method or person compare() Method returns 0

1.8 Properties Explain in detail

Properties Class is Hashtable Subclasses of , This object is used to process the properties file

Because of the key、value They're all string types , therefore Properties Inside key and value They're all string types

When accessing data , It is recommended to use setProperty(String key,String value) Methods and getProperty(String key) Method

@Test
public void test1() throws IOException {
    
    //1. Create objects 
    Properties properties = new Properties();
    //2. Load the file   involve IO I'll talk about it later. Just copy it forcibly here .
    properties.load(new FileReader("src/db.properties"));
    //3. get attribute 
    String username = properties.getProperty("username");
    System.out.println(username);
    String password = properties.getProperty("password");
    System.out.println(password);
    //4. Set properties   Set the properties in the object 
    properties.setProperty("username", " Zhang Fei ");
    properties.setProperty("password", "7654321");
    System.out.println(properties);
}

Two 、Collections Tool class

Collections It's an operation Set、List and Map And so on

Collections Provides a series of static methods for sorting collection elements 、 Query and modify etc , It also provides the ability to set immutability to collection objects 、 Implement synchronous control of collection objects ; Common methods are as follows ：

• The sorting operation ：
  • reverse(List)： reverse List The order of the elements in
  • shuffle(List)： Yes List Set elements in random order
  • sort(List)： Specify according to the natural order of the elements List The set elements are sorted in ascending order
  • sort(List,Comparator)： According to the designation Comparator The order of production is to List Set elements to sort
  • swap(List,int, int)： Will specify list In the collection i The elements and j Exchange elements at
• lookup 、 Replace
  • Object max(Collection)： According to the natural order of the elements , Returns the largest element in a given set
  • Object max(Collection,Comparator)： according to Comparator The order of designation , Returns the largest element in a given set
  • Object min(Collection)
  • Object min(Collection,Comparator)
  • int frequency(Collection,Object)： Returns the number of occurrences of a specified element in a specified collection
  • void copy(List dest,List src)： take src Copy the contents of to dest in
  • boolean replaceAll(List list,Object oldVal,Object newVal)： Replace with a new value List All old values of the object

Example ：Collections Tool applications

/*- reverse(List)： reverse  List  The order of the elements in  - shuffle(List)： Yes  List  Set elements in random order  - sort(List)： Specify according to the natural order of the elements  List  The set elements are sorted in ascending order  - sort(List,Comparator)： According to the designation  Comparator  The order of production is to  List  Set elements to sort  - swap(List,int, int)： Will specify  list  In the collection  i  The elements and  j  Exchange elements at */
	@Test
	public void test1() {
    
		List list = new ArrayList();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(5);
		list.add(6);
		//1. reverse list Collection elements 
		Collections.reverse(list);
		System.out.println(list);
		//2. Random sorting of set elements 
		Collections.shuffle(list);
		System.out.println(list);
		//3. Sort 
		Collections.sort(list);
		System.out.println(list);
		Collections.swap(list, 0, 1);
		System.out.println(list);
	}
	/** * - Object max(Collection)： According to the natural order of the elements , Returns the largest element in a given set  - Object max(Collection,Comparator)： according to  Comparator  The order of designation , Returns the largest element in a given set  - Object min(Collection) - Object min(Collection,Comparator) - int frequency(Collection,Object)： Returns the number of occurrences of a specified element in a specified collection  - void copy(List dest,List src)： take src Copy the contents of to dest in  - boolean replaceAll(List list,Object oldVal,Object newVal)： Replace with a new value  List  All old values of the object  */
	@Test
	public void test2() {
    
		Collection c1 = new ArrayList();
		c1.add(1);
		c1.add(2);
		c1.add(6);
		c1.add(3);
		c1.add(4);
		c1.add(5);
		c1.add(5);
		c1.add(5);
		c1.add(5);
		Object max = Collections.max(c1);
		System.out.println(max);
		System.out.println(Collections.frequency(c1, 5));
		//1. Copy Collection 
		List list = new ArrayList();
		list.add(1);
		list.add(2);
		list.add(3);
		List list2 = new ArrayList();
		for(int i=0;i<list.size();i++) {
    
			list2.add(null);
		}
		Collections.copy(list2, list);
		System.out.println(list2);
		Collections.replaceAll(list, 3, 3333);
		System.out.println(list);
		
	}

3、 ... and 、 Interview questions

sketch Map Implementation class HashMap LinkedHashMap Hashtable TreeMap Underlying principle

1.HashMap The bottom layer adopts array structure , adopt hash Methods calculate and store data Key Get hash value , Through this hash value, the subscript position of the underlying array is obtained , If the subscript has no value , Direct storage ; If the subscript has a value , Compare all values in this subscript hash value , If hash Values are different , Add... Directly ; If the same comparison equals Method return false Add... Directly , return true Modify the current position value . The same subscript stores multiple values in a one-way linked list structure ;jdk8 Red and black tree structure is added to this linked list structure .HashMap It can store null value , Threads are not synchronized .

2.Hashtable The underlying principles and HashMap Almost unanimously , The difference is , No storage null value , Threads are synchronized .

3.LinkedHashMap The underlying principles and HashMap It's almost the same , The difference is that each element is linked by a two-way linked list structure , bring LinkedHashMap Storing data looks like an orderly . You can also store null, Threads are also asynchronous .

4.TreeMap The bottom layer adopts red black tree storage structure , It can realize customized sorting and natural sorting ; Through the bottom layer comporaTo Method to repeat , return 0 It means the same .