Java collections
Overview of Java collection framework
1, Overview of the collection framework
1. Sets and arrays are structures that store multiple data, referred to as Java containers for short.
Note: storage at this time mainly refers to memory level storage, and does not involve persistent storage (. txt,.jpg,.avi, in the database)
2.1 characteristics of array in storing multiple data:
Once initialized, its length is determined.
Once an array is defined, the type of its elements is determined. We can only operate on the specified type of data.
For example: String[] arr;int[] arr1;Object[] arr2;
2.2 disadvantages of array in storing multiple data:
Once initialized, its length cannot be modified.
The methods provided in the array are very limited. It is very inconvenient and inefficient to add, delete and insert data.
The requirement to obtain the number of actual elements in the array. There are no ready-made properties or methods available in the array
The characteristics of array storage data: orderly and repeatable. For disordered and unrepeatable requirements, they cannot be met.
2, Collection framework
|----Collection interface: single column collection, used to store objects one by one
- |----List interface: store ordered and repeatable data. -- > Dynamic array
- |----ArrayList,LinkedList,Vector
|----Set interface: stores unordered and non repeatable data -- > high school's "set"
- |----HashSet,LinkedHashSet,TreeSet
|----Map interface: double column set, used to store a pair of (key - value) data -- > high school function: y = f(x)
- |----HashMap,LinkedHashMap,TreeMap,Hashtable,Properties
Collection interface method
Use of Collection interface methods
|----Collection interface: single column collection, used to store objects one by one
- |----List interface: store ordered and repeatable data. -- > Dynamic array
- |----ArrayList,LinkedList,Vector
The following shows the use of some Collection interface methods.
public class CollectionTest {
@Test
public void test1(){
Collection coll = new ArrayList();
//add(Object e): add element e to the collection coll
coll.add("AA");
coll.add("BB");
coll.add(123);//Automatic packing
coll.add(new Date());
//size(): gets the number of added elements
System.out.println(coll.size());//4
//addAll(Collection coll1): adds the elements in the coll1 collection to the current collection
Collection coll1 = new ArrayList();
coll1.add(456);
coll1.add("CC");
coll.addAll(coll1);
System.out.println(coll.size());//6
System.out.println(coll);
//clear(): clear collection elements
coll.clear();
//isEmpty(): judge whether the current collection is empty
System.out.println(coll.isEmpty());
}
}
Testing of methods declared in the Collection interface
- Conclusion (criterion): when adding data obj to the object of the implementation class of the Collection interface, the class of obj is required to override equals()
Here are some tests of the methods declared in the Collection interface.
public class CollectionTest {
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
// Person p = new Person("Jerry",20);
// coll.add(p);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//1.contains(Object obj): judge whether the current set contains obj
//When judging, we will call equals() of the class where the obj object is located, and usually override toString
boolean contains = coll.contains(123);
System.out.println(contains);
//Prove that the equal method is called and compare the contents
System.out.println(coll.contains(new String("Tom")));
// System.out.println(coll.contains(p));//true
//toString needs to be rewritten
System.out.println(coll.contains(new Person("Jerry",20)));//false -->true
//2.containsAll(Collection coll1): judge whether all elements in formal parameter coll1 exist in the current collection.
Collection coll1 = Arrays.asList(123,4567);
System.out.println(coll.containsAll(coll1));
}
@Test
public void test2(){
//3.remove(Object obj): removes obj elements from the current collection.
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
coll.remove(1234);
System.out.println(coll);
coll.remove(new Person("Jerry",20));
System.out.println(coll);
//4. removeAll(Collection coll1): subtraction: removes all elements in coll1 from the current collection.
Collection coll1 = Arrays.asList(123,456);
coll.removeAll(coll1);
System.out.println(coll);
}
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//5. Retain all (collection coll1): intersection: get the intersection of the current set and coll1 set and return it to the current set
// Collection coll1 = Arrays.asList(123,456,789);
// coll.retainAll(coll1);
// System.out.println(coll);
//6.equals(Object obj): to return true, the elements of the current set and the parameter set must be the same.
Collection coll1 = new ArrayList();
coll1.add(456);
coll1.add(123);
coll1.add(new Person("Jerry",20));
coll1.add(new String("Tom"));
coll1.add(false);
System.out.println(coll.equals(coll1));
}
@Test
public void test4(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//7.hashCode(): returns the hash value of the current object
System.out.println(coll.hashCode());
//8. Set -- > array: toArray()
Object[] arr = coll.toArray();
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}
//Extension: array -- > collection: call the static method asList() of the Arrays class
List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
System.out.println(list);
List arr1 = Arrays.asList(new int[]{123, 456});
System.out.println(arr1.size());//1
List arr2 = Arrays.asList(new Integer[]{123, 456});
System.out.println(arr2.size());//2
//9.iterator(): returns an instance of the iterator interface for traversing collection elements. Put it in iteratortest Testing in Java
}
}
The following shows some Collection call classes and toString overrides.
public class Person {
private String name;
private int age;
public Person() {
}
public Person(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 "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
System.out.println("Person equals()....");
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
Iterator iterator interface
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 during traversal. This method is different from the collection direct call remove()
The following shows the use of some Iterator iterator interfaces.
public class IteratorTest {
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
Iterator iterator = coll.iterator();
//Mode 1:
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// //Exception: NoSuchElementException
// System.out.println(iterator.next());
//Method 2: not recommended
// for(int i = 0;i < coll.size();i++){
// System.out.println(iterator.next());
// }
//Method 3: recommendation
hasNext():Determine if there is a next element
while(iterator.hasNext()){
//next(): ① move the pointer down ② return the elements at the collection position after moving down
System.out.println(iterator.next());
}
}
@Test
public void test2(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//Error mode 1:
// Iterator iterator = coll.iterator();
// while((iterator.next()) != null){
// System.out.println(iterator.next());
// }
//Error mode 2:
//Every time a collection object calls the iterator() method, it gets a new iterator object, and the default cursor is before the first element of the collection.
while (coll.iterator().hasNext()){
System.out.println(coll.iterator().next());
}
}
//Test remove() in Iterator
//If next() has not been called or the remove method has been called since the next method was last called,
// Calling remove again will report IllegalStateException.
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//Delete "Tom" in the collection
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
// iterator.remove();
Object obj = iterator.next();
if("Tom".equals(obj)){
iterator.remove();
// iterator.remove();
}
}
//Traversal set
iterator = coll.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
jdk 5.0 adds a foreach loop to traverse collections and arrays
Enhancing the foreach loop is equivalent to re creating the same array or collection, and the calling array or collection is still the original array or collection.
Here are some new foreach loops for traversing collections and arrays.
public class ForTest {
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//For (type of collection element local variable: collection object)
//The iterator is still called internally.
for(Object obj : coll){
System.out.println(obj);
}
}
@Test
public void test2(){
int[] arr = new int[]{1,2,3,4,5,6};
//For (type of array element, local variable: array object)
for(int i : arr){
System.out.println(i);
}
}
//Exercises
@Test
public void test3(){
String[] arr = new String[]{"MM","MM","MM"};
// //Method 1: ordinary for assignment
// for(int i = 0;i < arr.length;i++){
// arr[i] = "GG";
// }
//Mode 2: enhanced for loop
for(String s : arr){
s = "GG";
}
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}
}
}
Collection sub interface 1: List
- List interface framework
|----Collection interface: single column collection, used to store objects one by one
- |----List interface: store ordered and repeatable data. -- > "Dynamic" array, replacing the original array
- |----ArrayList: as the main implementation class of the List interface; Unsafe thread and high efficiency; The underlying layer uses Object[] elementData storage
- |----LinkedList: for frequent insert and delete operations, the efficiency of using this type is higher than that of ArrayList; The bottom layer uses two-way linked list storage
- |----Vector: as an ancient implementation class of the List interface; Thread safety and low efficiency; The underlying layer uses Object[] elementData storage
2. Source code analysis of ArrayList:
*2.1 jdk 7 cases
- 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 times of the original capacity, and the data in the original array needs to be copied to the new array.
- Conclusion: it is recommended to use a constructor with parameters in development: ArrayList = new ArrayList (int capacity)
*2.2 changes of ArrayList in JDK 8:
- ArrayList list = new ArrayList();// The underlying Object[] elementData is initialized to {} No array of length 10 was created
- list.add(123);// The first time add() is called, the underlying layer creates an array of length 10 and adds data 123 to elementData[0]
- ...
- The subsequent addition and expansion operations are the same as jdk 7.
*2.3 summary: the creation of ArrayList objects in jdk7 is similar to the starving type of singleton, while the creation of ArrayList objects in jdk8 is similar to the lazy type of singleton, delaying the creation of arrays and saving memory.
- Source code analysis of LinkedList:
*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.
- Node is defined as a two-way linked list that embodies LinkedList
- private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
4. Source code analysis of vector: when creating objects through the Vector() constructor in jdk7 and jdk8, the underlying 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.
Interview question: what are the similarities and differences among ArrayList, LinkedList and Vector?
Same: the three classes implement the List interface, and the characteristics of storing data are the same: storing orderly and repeatable data
Difference: | --- ArrayList: as the main implementation class of the List interface; Unsafe thread and high efficiency; The underlying layer uses Object[] elementData storage
|----LinkedList: for frequent insert and delete operations, the efficiency of using this type is higher than that of ArrayList; The bottom layer uses two-way linked list storage
|----Vector: as an ancient implementation class of the List interface; Thread safety and low efficiency; The underlying layer uses Object[] elementData storage
5. Common methods in list interface
void add(int index, Object ele): inserts an ele element at the index position
boolean addAll(int index, Collection eles): add all elements in eles from the index position
Object get(int index): gets the element at the specified index position
int indexOf(Object obj): returns the position where obj first appears in the collection
int lastIndexOf(Object obj): returns the last occurrence of obj in the current collection
Object remove(int index): removes the element at the specified index position and returns this element
Object set(int index, Object ele): sets the element at the specified index position to ele
List subList(int fromIndex, int toIndex): returns a subset from fromIndex to toIndex
Summary: common methods
Add: add at the end of add(Object obj)
Delete: remove(int index) / remove(Object obj)
Change: set(int index, Object ele)
Query: get(int index)
Insert: add(int index, Object ele)
Length: size()
Traversal: ① Iterator iterator mode
② Enhanced for loop
③ Ordinary cycle
Here are some common methods in the List interface.
public class ListTest {
/*
void add(int index, Object ele):Insert the ele element at the index position
boolean addAll(int index, Collection eles):Add all elements in eles from the index position
Object get(int index):Gets the element at the specified index location
int indexOf(Object obj):Returns the position where obj first appears in the collection
int lastIndexOf(Object obj):Returns the last occurrence of obj in the current collection
Object remove(int index):Removes the element at the specified index location and returns this element
Object set(int index, Object ele):Set the element at the specified index location to ele
List subList(int fromIndex, int toIndex):Returns a subset from fromIndex to toIndex
Summary: common methods
Add: add(Object obj)
Delete: remove(int index) / remove(Object obj)
Change: set(int index, Object ele)
Query: get(int index)
Insert: add(int index, Object ele)
Length: size()
Traversal: ① Iterator iterator mode
② Enhanced for loop
③ Ordinary cycle
*/
@Test
public void test3(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
//Mode 1: Iterator iterator mode
Iterator iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
System.out.println("***************");
//Mode 2: enhanced for loop
for(Object obj : list){
System.out.println(obj);
}
System.out.println("***************");
//Mode 3: normal for loop
for(int i = 0;i < list.size();i++){
System.out.println(list.get(i));
}
}
@Test
public void test2(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("Tom",12));
list.add(456);
//int indexOf(Object obj): returns the position where obj first appears in the collection. If it does not exist, - 1
int index = list.indexOf(4567);
System.out.println(index);
//int lastIndexOf(Object obj): returns the last occurrence of obj in the current collection. If it does not exist, - 1
System.out.println(list.lastIndexOf(456));
//Object remove(int index): removes the element at the specified index position and returns this element
Object obj = list.remove(0);
System.out.println(obj);
System.out.println(list);
//Object set(int index, Object ele): sets the element at the specified index position to ele
list.set(1,"CC");
System.out.println(list);
//List subList(int fromIndex, int toIndex): returns a subset of the left closed right open interval from fromIndex to toIndex
List subList = list.subList(2, 4);
System.out.println(subList);
System.out.println(list);
}
@Test
public void test1(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("Tom",12));
list.add(456);
System.out.println(list);
//void add(int index, Object ele): inserts an ele element at the index position
list.add(1,"BB");
System.out.println(list);
//boolean addAll(int index, Collection eles): add all elements in eles from the index position
List list1 = Arrays.asList(1, 2, 3);
list.addAll(list1);
// list.add(list1);
System.out.println(list.size());//9
//Object get(int index): gets the element at the specified index position
System.out.println(list.get(0));
}
}
Here are some small questions of list.
public class ListExer {
/*
Distinguish between remove(int index) and remove(Object obj) in the List
*/
@Test
public void testListRemove() {
List list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
updateList(list);
System.out.println(list);//
}
private void updateList(List list) {
// list.remove(2);// Delete the value of the corresponding index
list.remove(new Integer(2)); //Delete corresponding value
}
Collection sub interface 2: Set
1. Framework of set interface:
|----Collection interface: single column collection, used to store objects one by one
*|----Set interface: stores unordered and non repeatable data -- > high school's "set"
- |----HashSet: as the main implementation class of Set interface; Thread unsafe; null values can be stored
- |----LinkedHashSet: as a subclass of HashSet; When traversing its internal data, it can be traversed in the order of addition. For frequent traversal operations, the efficiency of LinkedHashSet is higher than that of HashSet
- |----TreeSet: you can sort according to the specified attributes of the added object.
- There are no new methods defined in the Set interface, but all the methods declared in the Collection are used.
- Requirement: the class of data added to set (mainly HashSet and LinkedHashSet) must override hashCode() and equals()
Requirement: the rewritten hashCode() and equals() should be consistent as much as possible: equal objects must have equal hash codes
Tip for rewriting two methods: the fields in the object used for the equals() method comparison should be used to calculate the hashCode value.
Rewriting of hashCode() in Eclipse/IDEA tool
Take Eclipse/IDEA as an example. In a custom class, you can call tools to automatically rewrite equals and hashCode. Question: why does Eclipse/IDEA copy the hashCode method with the number 31?
when selecting the coefficient, select the coefficient as large as possible. Because if the calculated hash address is larger, the so-called "conflicts" will be less, and the search efficiency will be improved. (conflict reduction)
moreover, 31 only occupies 5 bits, and the probability of data overflow caused by multiplication is small.
31 can be represented by I * 31 = = (I < < 5) - 1. Now many virtual machines are optimized. (improve algorithm efficiency)
31 is a prime number. The function of prime number is that if I multiply a number by this prime number, the final result can only be divided by the prime number itself, the multiplicand and 1! (conflict reduction)
Basic principles for overriding hashCode() methods
when the program is running, the same object calls the hashCode() method multiple times and should return the same value.
when the equals() method of two objects returns true, the return value of the hashCode() method of the two objects should also be equal.
the fields in the object used for the equals() method comparison should be used to calculate the hashCode value.
Basic principles for overriding the equals() method
Taking the custom Customer class as an example, when do I need to override equals()?
when a class has its own unique concept of "logical equality", when rewriting equals(), always rewrite hashCode(). According to the equals method of a class (after rewriting), two distinct instances may be logically equal, but according to object hashCode() method, which are just two objects.
therefore, it violates "equal objects must have equal hash codes".
conclusion: when copying the equals method, it is generally necessary to copy the hashCode method at the same time. Generally, the properties of the objects involved in the calculation of hashCode should also be involved in the calculation of equals().
1, Set: stores unordered and non repeatable data
Take HashSet as an example:
- Disorder: not equal to randomness. 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.
- Non repeatability: ensure that when the added element is judged according to equals(), it cannot return true That is, only one element can be added to the same element.
2, Process of adding elements: take HashSet as an example:
We add element a to the HashSet. First, we call the hashCode() method of the class where element a is located to calculate the hash value of element A. then, we use an algorithm to calculate the storage position (i.e. index position) in the underlying array of the HashSet, and judge whether there are elements in this position of the array:
If there are no other elements at this location, element a is added successfully. > Case 1
If there are other elements b (or multiple elements in the form of a linked list) at this position, compare the hash values of element a and element b:
If the hash values are different, element a is added successfully. > Case 2
If the hash values are the same, you need to call the equals() method of the class where element a is located:
- equals() returns true, element a addition failed
- If equals() returns false, element a is added successfully. > Case 2
For cases 2 and 3 where the addition is successful, element a and the data already existing at the specified index position are stored in a linked list.
jdk 7: put element a into the array and point to the original element.
jdk 8: the original element is in the array and points to element a
*Conclusion: seven up and eight down
HashSet bottom layer: array + linked list structure.
Here are some introductions to the set framework.
*/
@Test
public void test1(){
Set set = new HashSet();
set.add(456);
set.add(123);
set.add(123);
set.add("AA");
set.add("CC");
set.add(new User("Tom",12));
set.add(new User("Tom",12));
set.add(129);
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
Use of LinkedHashSet
LinkedHashSet is 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.
Advantages: LinkedHashSet is more efficient than HashSet for frequent traversal operations
The following shows the use of some linkedhashsets.
//Use of LinkedHashSet
//LinkedHashSet is a subclass of HashSet. While adding data, each data also maintains two references, recording the previous one of this data
//Data and the latter data.
//Advantages: LinkedHashSet is more efficient than HashSet for frequent traversal operations
@Test
public void test2(){
Set set = new LinkedHashSet();
set.add(456);
set.add(123);
set.add(123);
set.add("AA");
set.add("CC");
set.add(new User("Tom",12));
set.add(new User("Tom",12));
set.add(129);
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
Use of TreeSet method
1. The data added to TreeSet must be objects of the same class.
2. Two sorting methods: natural sorting (implementing Comparable interface) and custom sorting (Comparator)
3. In natural sorting, the standard for comparing whether two objects are the same is: compareTo() returns 0 No longer equals()
4. In custom sorting, the standard for comparing whether two objects are the same is: compare() returns 0 No longer equals()
The following shows some settings of User natural sorting (comparable interface) in TreeSet method.
//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");
}
}
The following shows the use of some TreeSet methods.
public class TreeSetTest {
@Test
public void test1(){
TreeSet set = new TreeSet();
//Failed: cannot add objects of different classes
// set.add(123);
// set.add(456);
// set.add("AA");
// set.add(new User("Tom",12));
//Example 1:
// set.add(34);
// set.add(-34);
// set.add(43);
// set.add(11);
// set.add(8);
//Example 2:
set.add(new User("Tom",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Mike",65));
set.add(new User("Jack",33));
set.add(new User("Jack",56));
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
@Test
public void test2(){
//Setting of custom sorting comparator
Comparator com = new Comparator() {
//Arranged from small to large according to age
@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());
}else{
throw new RuntimeException("The data types entered do not match");
}
}
};
TreeSet set = new TreeSet(com);
set.add(new User("Tom",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Mike",65));
set.add(new User("Mary",33));
set.add(new User("Jack",33));
set.add(new User("Jack",56));
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
Map interface
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; Store null key and value
- |----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 to sort according to the added key value pairs and realize sorting traversal. At this time, consider the natural sorting or customized sorting of keys, and the red black tree is used at the bottom
|----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)
Interview questions (important):
- The underlying implementation principle of HashMap?
- What are the similarities and differences between HashMap and Hashtable?
- What are the similarities and differences between CurrentHashMap and Hashtable? (not for the time being)
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: (important)
- 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. (different from Set method)
- 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:
- new HashMap(): the underlying layer does not create an array with a length of 16
- The array at the bottom of jdk 8 is Node [], not Entry []
- When the put() method is called for the first time, the underlying layer creates an array with a length of 16
- The jdk7 underlying structure is only: 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;//Comparing HashMap addition 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()
Here are some methods defined in the Map.
public class MapTest {
/*
Method of metaview operation:
Set keySet(): Returns the Set set composed of all key s
Collection values(): Returns a Collection of all value s
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 of element query:
Object get(Object key): Gets the value corresponding to the specified key
boolean containsKey(Object key): Whether to include the specified key
boolean containsValue(Object value): Whether to include the specified value
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());
}
/*
Add, delete and modify:
Object put(Object key,Object value): Add (or modify) 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): Remove the key value pair of the specified key and return 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);
}
@Test
public void test2(){
Map map = new HashMap();
map = new LinkedHashMap();
map.put(123,"AA");
map.put(345,"BB");
map.put(12,"CC");
System.out.println(map);
}
@Test
public void test1(){
Map map = new HashMap();
// map = new Hashtable();
map.put(null,123);
}
}
How to use TreeMap:
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
Here are some ways to use TreeMap.
public class TreeMapTest {
//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());
}
}
//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());
}
}
}
Map implementation class: Properties
The Properties class is a subclass of Hashtable, which is used to process property files
*Since the key and value in the Properties file are of string type, the key and value in Properties are of string type
*When accessing data, it is recommended to use setProperty(String key,String value) method and getProperty(String key) method
Here are some Properties: commonly used to process configuration files.
public class PropertiesTest {
//Properties: commonly used to process configuration files. Both key and value are String types
public static void main(String[] args) {
FileInputStream fis = null;
try {
Properties pros = new Properties();
fis = new FileInputStream("jdbc.properties");
pros.load(fis);//Load the file corresponding to the stream
String name = pros.getProperty("name");
String password = pros.getProperty("password");
System.out.println("name = " + name + ", password = " + password);
} catch (IOException e) {
e.printStackTrace();
} finally {
if(fis != null){
try {
fis.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
}
Collections tool class
*Collections is a tool class that operates on collections such as Set, List, and Map
*Collections provides a series of static methods to sort, query and modify collection elements. It also provides methods to set immutable collection objects and realize synchronous control over collection objects
1. Sorting: (all static methods)
reverse(List): reverse the order of elements in the List
shuffle(List): randomly sort the elements of the List set
sort(List): sort the elements of the specified List set in ascending order according to the natural order of the elements
sort(List, Comparator): sort the List set elements according to the order generated by the specified Comparator
swap(List, int, int): exchange the elements at i and j in the specified list set
2. Find and replace
Object max(Collection): returns the largest element in a given set according to the natural order of elements
Object max(Collection, Comparator): returns the largest element in a given set according to the order specified by the Comparator
Object min(Collection)
Object min(Collection， Comparator)
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, Object oldVal, Object newVal): replace all old values of the List object with new values
Collections common method: synchronization control
Multiple synchronizedXxx() methods are provided in the Collections class, which can wrap the specified collection into a thread synchronized collection, so as to solve the thread safety problem when multiple threads access the collection concurrently (commonly used in development)
The following shows the use of some Collections tool classes.
@Test
public void test2(){
List list = new ArrayList();
list.add(123);
list.add(43);
list.add(765);
list.add(-97);
list.add(0);
//Exception: IndexOutOfBoundsException("Source does not fit in dest")
// List dest = new ArrayList();
// Collections.copy(dest,list);
//correct:
List dest = Arrays.asList(new Object[list.size()]);
System.out.println(dest.size());//list.size();
Collections.copy(dest,list);
System.out.println(dest);
/*
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
*/
//The returned list1 is the thread safe List
List list1 = Collections.synchronizedList(list);
}
@Test
public void test1(){
List list = new ArrayList();
list.add(123);
list.add(43);
list.add(765);
list.add(765);
list.add(765);
list.add(-97);
list.add(0);
System.out.println(list);
// Collections.reverse(list);
// Collections.shuffle(list);
// Collections.sort(list);
// Collections.swap(list,1,2);
int frequency = Collections.frequency(list, 123);
System.out.println(list);
System.out.println(frequency);
}