*1, Structure of Map implementation class:
*|--- Map: double column data, storing the data of key value pairs --- similar to the function of high school: y = f(x)
* |---- HashMap: as the main implementation class of Map; Unsafe thread and high efficiency; null key s and value s can be stored
* |---- LinkedHashMap: ensure that when traversing map elements, traversal can be implemented in the order of addition.
*Reason: Based on the original HashMap underlying structure, a pair of pointers are added to point to the previous and subsequent elements.
*For frequent traversal operations, this kind of execution efficiency is higher than HashMap.
*|--- TreeMap: ensure that the added key value pairs are sorted to realize sorting traversal. In this case, consider the natural sorting of keys Or custom sorting, the bottom layer uses red black tree
*|--- Hashtable: as an ancient implementation class; Thread safety and low efficiency; null key and value cannot be stored
* |---- Properties: commonly used to process configuration files. Both key and value are String types
*
*
*The bottom layer of HashMap: array + linked list (jdk7 and before)
*Array + linked list + red black tree (jdk 8)
*2, Understanding of Map structure:
*Keys in Map: unordered and non repeatable. Use Set to store all keys -- > the class where the key is located should override equals() and hashCode() (take HashMap as an example)
*Value in Map: unordered and repeatable. Use Collection to store all values -- > the class where value is located should override equals()
*A key value pair: key value constitutes an Entry object.
*Entries in Map: unordered and non repeatable. Use Set to store all entries
*3, The 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.
*... may have performed put more than once
* map.put(key1,value1):
*First, call hashCode() of the class where key1 is located to calculate the hash value of key1. After the hash value is calculated by some algorithm, the storage location in the Entry array is obtained.
*If the data in this location is empty, key1-value1 is added successfully---- Case 1
*If the data in this location is not empty, (which means that there are one or more data in this location (in the form of linked list)), compare the hash values of key1 and one or more existing data:
*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(key2) method of the class where key1 is located, and compare:
*If equals() returns false: key1-value1 is added successfully---- Case 3
*If equals() returns true: replace value2 with value1.
*
*Supplement: for case 2 and case 3: at this time, key1-value1 and the original data are stored in a linked list.
*
*During the continuous addition process, the problem of capacity expansion will be involved. When the critical value is exceeded (and the location to be stored is not empty), the capacity will be expanded. Default capacity expansion method: expand the capacity to twice the original capacity and copy the original data.
*
*jdk8 is different from jdk7 in terms of underlying implementation:
*1. new HashMap(): the bottom layer does not create an array with a length of 16
*2. The bottom array of JDK 8 is Node [], not Entry []
*3. When the put() method is called for the first time, the underlying layer creates an array with a length of 16
*4. jdk7 underlying structure: array + linked list. The underlying structure in jdk8: array + linked list + red black tree.
*4.1 when a linked list is formed, it is at sixes and sevens (jdk7: the new element points to the old element. jdk8: the old element points to the new element)
4.2 when the number of data in the form of linked list of elements at an index position of the array is > 8 and the length of the current array is > 64, the data at this index position is stored in red black tree instead.
*
* DEFAULT_ INITIAL_ Capability: default capacity of HashMap, 16
* DEFAULT_LOAD_FACTOR: default load factor of HashMap: 0.75
*threshold: critical value of capacity expansion, = capacity * filling factor: 16 * 0.75 = > 12
* TREEIFY_THRESHOLD: if the length of the linked list in the Bucket is greater than the default value, it will be converted into a red black tree: 8
* MIN_ TREEIFY_ Capability: minimum hash table capacity when nodes in the bucket are trealized: 64
*4, Underlying implementation principle of LinkedHashMap (understand)
*In the source code:
* static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;// It can record the order of added elements
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
*5, Methods defined in Map:
Add, delete and modify:
Object put(Object key,Object value): adds (or modifies) the specified key value to the current map object
void putAll(Map m): store all key value pairs in m into the current map
Object remove(Object key): removes the key value pair of the specified key and returns value
void clear(): clear all data in the current map
Operation of element query:
Object get(Object key): get the value corresponding to the specified key
boolean containsKey(Object key): whether the specified key is included
boolean containsValue(Object value): whether the specified value is included
int size(): returns the number of key value pairs in the map
boolean isEmpty(): judge whether the current map is empty
boolean equals(Object obj): judge whether the current map and parameter object obj are equal
Method of metaview operation:
Set keySet(): returns the set set composed of all keys
Collection values(): returns the collection collection composed of all values
Set entrySet(): returns the set set composed of all key value pairs
*Summary: common methods:
*Add: put(Object key,Object value)
*Delete: remove(Object key)
*Modify: put(Object key,Object value)
*Query: get(Object key)
*Length: size()
*Traversal: keySet() / values() / entrySet()
@Test
public void test2(){
Map map = new HashMap();//Disordered
// map = new LinkedHashMap();// Orderly
map.put(123,"AA");
map.put(345,"BB");
map.put(12,"CC");
System.out.println(map);
}
************************************************************
Operation results:
{345=BB, 123=AA, 12=CC}
************************************************************
************************************************************
@Test
public void test2(){
Map map = new HashMap();//Disordered
map = new LinkedHashMap();//Orderly
map.put(123,"AA");
map.put(345,"BB");
map.put(12,"CC");
System.out.println(map);
}
************************************************************
Operation results:
{123=AA, 345=BB, 12=CC}
/*
Add, delete and modify:
Object put(Object key,Object value): adds (or modifies) the specified key value to the current map object
void putAll(Map m): store all key value pairs in m into the current map
Object remove(Object key): removes the key value pair of the specified key and returns value
void clear(): clear all data in the current map
*/
@Test
public void test3(){
Map map = new HashMap();
//add to
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
//modify
map.put("AA",87);
System.out.println(map);
Map map1 = new HashMap();
map1.put("CC",123);
map1.put("DD",123);
map.putAll(map1);
System.out.println(map);
//remove(Object key)
Object value = map.remove("CC");
System.out.println(value);
System.out.println(map);
//clear()
map.clear();//Different from map = null operation
System.out.println(map.size());
System.out.println(map);
}
**********************************************************************
Operation results:
{AA=87, BB=56, 45=123}
{AA=87, BB=56, CC=123, DD=123, 45=123}
123
{AA=87, BB=56, DD=123, 45=123}
0
{}
/*
Operation of element query:
Object get(Object key): get the value corresponding to the specified key
boolean containsKey(Object key): whether the specified key is included
boolean containsValue(Object value): whether the specified value is included
int size(): returns the number of key value pairs in the map
boolean isEmpty(): judge whether the current map is empty
boolean equals(Object obj): judge whether the current map and parameter object obj are equal
*/
@Test
public void test4(){
Map map = new HashMap();
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
// Object get(Object key)
System.out.println(map.get(45));
//containsKey(Object key)
boolean isExist = map.containsKey("BB");
System.out.println(isExist);
isExist = map.containsValue(123);
System.out.println(isExist);
map.clear();
System.out.println(map.isEmpty());
}
****************************************************************
Operation results;
123
true
true
true
/*
Method of metaview operation:
Set keySet(): returns the set set composed of all keys
Collection values(): returns the collection collection composed of all values
Set entrySet(): returns the set set composed of all key value pairs
*/
@Test
public void test5(){
Map map = new HashMap();
map.put("AA",123);
map.put(45,1234);
map.put("BB",56);
//Traverse all key sets: keySet()
Set set = map.keySet();
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
System.out.println();
//Traverse all value sets: values()
Collection values = map.values();
for(Object obj : values){
System.out.println(obj);
}
System.out.println();
//Traverse all key values
//Method 1: entrySet()
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
//All elements in the entry set collection are entries
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
System.out.println();
//Mode 2:
Set keySet = map.keySet();
Iterator iterator2 = keySet.iterator();
while(iterator2.hasNext()){
Object key = iterator2.next();
Object value = map.get(key);
System.out.println(key + "=====" + value);
}
}
**************************************************************************
Operation results:
AA
BB
45
123
56
1234
AA---->123
BB---->56
45---->1234
AA=====123
BB=====56
45=====1234
//Adding key value to TreeMap requires that the key must be an object created by the same class
//Because you need to sort by key: natural sorting and custom sorting
//Natural sorting
@Test
public void test1(){
TreeMap map = new TreeMap();
User u1 = new User("Tom",23);
User u2 = new User("Jerry",32);
User u3 = new User("Jack",20);
User u4 = new User("Rose",18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
}
*********************************************************
Operation results:
User{name='Tom', age=23}---->98
User{name='Rose', age=18}---->100
User{name='Jerry', age=32}---->89
User{name='Jack', age=20}---->76
*********************************************************
public class User implements Comparable{
private String name;
private int age;
public User() {
}
public User(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "User{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
System.out.println("User equals()....");
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
if (age != user.age) return false;
return name != null ? name.equals(user.name) : user.name == null;
}
@Override
public int hashCode() { //return name.hashCode() + age;
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
//In descending order of name and age
@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User)o;
// return -this.name.compareTo(user.name);
int compare = -this.name.compareTo(user.name);
if(compare != 0){
return compare;
}else{
return Integer.compare(this.age,user.age);
}
}else{
throw new RuntimeException("The types entered do not match");
}
}
}
//Custom sorting
@Test
public void test2(){
TreeMap map = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof User && o2 instanceof User){
User u1 = (User)o1;
User u2 = (User)o2;
return Integer.compare(u1.getAge(),u2.getAge());
}
throw new RuntimeException("The input type does not match!");
}
});
User u1 = new User("Tom",23);
User u2 = new User("Jerry",32);
User u3 = new User("Jack",20);
User u4 = new User("Rose",18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
}
******************************************************************************
Operation results:
User{name='Rose', age=18}---->100
User{name='Jack', age=20}---->76
User{name='Tom', age=23}---->98
User{name='Jerry', age=32}---->89
******************************************************************************
public class User implements Comparable{
private String name;
private int age;
public User() {
}
public User(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "User{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
System.out.println("User equals()....");
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
if (age != user.age) return false;
return name != null ? name.equals(user.name) : user.name == null;
}
@Override
public int hashCode() { //return name.hashCode() + age;
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
//In descending order of name and age
@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User)o;
// return -this.name.compareTo(user.name);
int compare = -this.name.compareTo(user.name);
if(compare != 0){
return compare;
}else{
return Integer.compare(this.age,user.age);
}
}else{
throw new RuntimeException("The types entered do not match");
}
}
}