Chapter 11 Java aggregate
Arrays and collections
Collection and array storage data overview
aggregate 、 Arrays are structures that store multiple data , abbreviation Java Containers .
explain ： The storage at this time , Mainly refers to memory level storage , It doesn't involve persistent storage （.txt,.jpg,.avi, In the database )
The characteristics of array storage
- Once initialized , The length is determined
- Once the array is defined , The type of its elements is determined . We can only manipulate the data of the specified type .
- such as ：String[] arr;int[] arr1;Object[] arr2
The disadvantages of array storage
- Once initialized , Its length cannot be modified .
- There are very limited methods available in arrays , For adding 、 Delete 、 Insert data and so on , Very inconvenient , At the same time, the efficiency is not high .
- Get the number of actual elements in the array , Arrays have no ready-made properties or methods available
- Array storage data characteristics ： Orderly 、 repeatable . For disorder 、 Non repeatable requirements , Can't meet .
The advantages of collective storage
Solve the problem of array storage data .
Collection Interface
Single column set frame structure
Collection Interface common methods
add(Object obj),addAll(Collection coll),size(),isEmpty(),clear();
contains(Object obj),containsAll(Collection coll),remove(Object obj),removeAll(Collection coll),retainsAll(Collection coll),equals(Object obj);
hasCode(),toArray(),iterator();
Collection Conversion between sets and arrays
// aggregate ---> Array ：toArray()
Object[] arr = coll.toArray();
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}
// expand ： Array ---> aggregate : call Arrays Class static methods asList(T ... t)
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
Use Collection Collection store objects , The class to which the object belongs must satisfy
towards Collection Add data to the object of the implementation class of the interface obj when , requirement obj The class in which you want to override equals().
Iterator Interface and foreach Interface
Traverse Collection Two ways
① Using Iterators Iterator ② foreach loop （ Or enhance for loop ）
java.utils The iterator interface defined under package ：Iterator
IteratorObjects are called iterators ( One of the design patterns ), It's mainly used to traverse Collection The elements in the collection .- GOF The iterator pattern is defined as ： Provides a way to access a container (container) Object , Without exposing the internal details of the object . Iterator pattern , It's made for containers .
effect ： Ergodic set Collectiton Elements
Iterator iterator = coll.iterator();
//hasNext(): Decide whether to return the next element
while(iterator.hasNext()){
//next():① The pointer moves down ② Returns the element at the position of the collection after it is moved down
System.out.println(iterator.next());
}
Book description
remove() Use
// test Iterator Medium remove()
// If not already called next() Or in the last call next Method has been called remove Method , Call again remove Metropolitan newspaper IllegalStateException.
// The interior defines remove(), It can be traversed , Delete elements from the collection . This method is different from a collection calling directly remove()
@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... From the collection "Tom"
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
// iterator.remove();
Object obj = iterator.next();
if("Tom".equals(obj)){
iterator.remove();
// iterator.remove();
}
}
// Ergodic set
iterator = coll.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
jdk5.0 New characteristics -- enhance for loop ：(foreach loop )
@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( The type of collection element local variable : A collection of objects )
for(Object obj : coll){
System.out.println(obj);
}
}
explain ：
The iterator is still called internally .
Examples of traversing arrays ：
@Test
public void test2(){
int[] arr = new int[]{1,2,3,4,5,6};
//for( The type of array element local variable : Array objects )
for(int i : arr){
System.out.println(i);
}
}
Collection A subinterface ：List Interface
Stored data features ： Storage order 、 Repeatable data .
Common methods
increase ：add(Object obj)
Delete ：remove(int index) / remove(Object obj)
Change ：set(int index, Object ele)
check ：get(int index)
insert ：add(int index, Object ele)
length ：size()
Traverse ：① Iterator Iterator mode
② enhance for loop
③ The normal cycle
Common implementation classes
|----Collection Interface ： Single column set , Objects used to store one object after another
* |----List Interface ： Storage order 、 Repeatable data . -->“ dynamic ” Array , Replace the original array
* |----ArrayList： As List The main implementation class of the interface ; Thread unsafe , Efficient ; Bottom use Object[] elementData Storage
* |----LinkedList： For frequent inserts 、 Delete operation , Using this kind of efficiency ratio ArrayList high ; The bottom layer uses bidirectional linked list storage
* |----Vector： As List The old implementation class of the interface ; Thread safe , Low efficiency ; Bottom use Object[] elementData Storage
- ArrayList Is the most commonly used , But the thread is upset
Some source code analysis
ArrayList Source code analysis
//jdk 7
ArrayList list = new ArrayList();// The bottom layer creates a length of 10 Of Object[] Array elementData
list.add(123);//elementData[0] = new Integer(123);
...
list.add(11);// If this addition leads to the underlying elementData The array capacity is not enough , Then expand the capacity
// By default , Expand to the original capacity 1.5 times , At the same time, you need to copy the data from the original array to the new array .
// Conclusion ： It is recommended that constructors with parameters be used in development ：ArrayList list = new ArrayList(int capacity)
//jdk 8 in ArrayList The change of
ArrayList list = new ArrayList();// Bottom Object[] elementData Initialize to {}. It didn't create a length of 10 Array of
list.add(123);// First call add() when , The bottom layer creates the length 10 Array of , And put the data 123 Add to elementData[0]
...// The subsequent addition and expansion operations and jdk 7 It's no different .
// Summary ：jdk7 Medium ArrayList The creation of the object is similar to that of the singleton , and jdk8 Medium ArrayList The creation of an object for is similar to the lazy singleton , Delayed array creation , Save memory .
LinkedList Source code analysis
LinkedList list = new LinkedList(); // Internal statement Node Type of first and last attribute , The default value is null
list.add(123);// take 123 Package to Node in , Created Node object .
// among ,Node Defined as ： Embodies the LinkedList Two way linked list
//
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Vector Source code analysis
jdk7 and jdk8 Pass through Vector() When the constructor creates an object , The bottom layers are created with a length of 10 Array of .
In terms of capacity expansion , The default expansion is the original array length 2 times .
Requirements for stored elements
Added objects , The class in which you want to override equals() Method
* Interview questions ：ArrayList、LinkedList、Vector The similarities and differences between them ？
* Same as ： All three classes implement List Interface , The characteristics of stored data are the same ： Storage order 、 Repeatable data
* Different ： See above （ The first 3 part + The first 4 part ）
Collection A subinterface ：Set Interface
Stored data features ： A disorderly 、 Non repeatable elements
With HashSet For example, ：
- Disorder ： It's not equal to randomness . The stored data is not added to the underlying array in the order of the array index , It depends on the hash value of the data .
- Non repeatability ： Make sure the added elements are as follows equals() When judging , Can't return true. namely ： Only one can be added to the same element .
Element addition process ：( With HashSet For example )
We ask HashSet Add elements to it a, First call the element a Of the class hashCode() Method , Calculated element a Hash value of ,
This hash value is then calculated by some algorithm in HashSet The storage location in the underlying array （ That is to say ： Index position , Judge
Array whether the element already exists at this position ：
If there are no other elements in this position , The element a Add success . ---> situation 1
If there are other elements in this position b( Or multiple elements in the form of a linked list , Compare elements a And element b Of hash value ：
If hash The value is different , The element a Add success .---> situation 2
If hash Same value , In turn, you need to call the element a Of the class equals() Method ：
equals() return true, Elements a Add failure
equals() return false, The element a Add success .---> situation 2
For successful additions 2 And circumstances 3 for ： Elements a And the existing data at the specified index position are stored in the form of linked list .
jdk 7 : Elements a Put it in the array , Point to the original element .
jdk 8 : The original element is in the array , Point to elements a
summary ： an unsettled state of mind
HashSet Bottom ： Array + The structure of the list .（ Premise ：jdk7）
Common methods
Set No new methods are defined in the interface , All of them are Collection The method declared in .
Common implementation classes
|----Collection Interface ： Single column set , Objects used to store one object after another
* |----Set Interface ： Storage out of order 、 Non repeatable data --> High school said “ aggregate ”
* |----HashSet： As Set The main implementation class of the interface ; Thread unsafe ; Can be stored null value
* |----LinkedHashSet： As HashSet Subclasses of ; When traversing its internal data , You can traverse it in the order you add it
* While adding data , Each data also maintains two references , Record this data, the previous data and the next data . For frequent traversal operations ,LinkedHashSet Efficiency is higher than HashSet.
* |----TreeSet： You can add the specified properties of the object as follows , Sort .
- HashSet Most used
The requirements of the class where the object is stored
HashSet/LinkedHashSet:
requirement ： towards Set( Mainly refers to ：HashSet、LinkedHashSet) Data added in , Its class must be overridden hashCode() and equals()
requirement ： Rewrite the hashCode() and equals() Be as consistent as possible ： Equal objects must have equal hash codes
* Tips for rewriting two methods ： Object to be used as equals() Method comparison Field, Should be used to calculate hashCode value .
TreeSet:
- In natural order , The criterion for comparing whether two objects are the same is ：compareTo() return 0. No more equals().
- Custom sorting , The criterion for comparing whether two objects are the same is ：compare() return 0. No more equals().
TreeSet Use
- towards TreeSet Data added in , Requirements are objects of the same class .
- Two ways of sorting ： Natural ordering （ Realization Comparable Interface and Custom sort （Comparator）
@Test
public void test1(){
TreeSet set = new TreeSet();
// Failure ： 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(){
Comparator com = new Comparator() {
// In order of age, from small to large
@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(" Input data type does 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
Common implementation class structure
|----Map: Double column data , Storage key-value Right data --- It's like a high school function ：y = f(x)
* |----HashMap: As Map The main implementation class of ; Thread unsafe , Efficient ; Storage null Of key and value
* |----LinkedHashMap: Make sure to traverse map Element time , You can traverse 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 you follow the added key-value To sort , Implement sort traversal . Consider... At this time key Natural sort or custom sort of
* Use black and red trees at the bottom
* |----Hashtable: As an ancient implementation class ; Thread safe , Low efficiency ; Can't store null Of key and value
* |----Properties: It is often used to process configuration files .key and value All are String type
*
*
* HashMap The bottom of the ： Array + Linked list （jdk7 And before )
* Array + Linked list + Red and black trees （jdk 8)
Understanding of storage structure
>Map Medium key: A disorderly 、 Non repeatable , Use Set The store's 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 The store's 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 The store's entry
Common methods
* add to ：put(Object key,Object value)
* Delete ：remove(Object key)
* modify ：put(Object key,Object value)
* Inquire about ：get(Object key)
* length ：size()
* Traverse ：keySet() / values() / entrySet()
Memory structure description
HashMap stay jdk7 Principle of implementation in
HashMap map = new HashMap():
* After instantiation , The bottom layer creates a length of 16 One dimensional array of Entry[] table.
* ... It may have been executed many times put...
* 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
* 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
* 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
* If equals() return true: Use value1 Replace value2.
*
* Add ： About the situation 2 And circumstances 3： here key1-value1 And the original data is stored in a linked list .
*
* 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 .
HashMap stay jdk8 Compared with jdk7 The difference in the underlying implementation
1. new HashMap(): The bottom layer did not create a length of 16 Array of
2. jdk 8 The underlying array is ：Node[], Instead of Entry[]
3. Call for the first time put() When the method is used , The length of the bottom layer creation is 16 Array of
4. jdk7 The underlying structure is just ： Array + Linked list .jdk8 Middle bottom structure ： Array + Linked list + Red and black trees .
4.1 When you form a linked list , an unsettled state of mind （jdk7: The new element points to the old element .jdk8： The old element points to the new element ）
4.2 The number of data in the form of linked list when the elements in an index position of an array exist > 8 And the length of the current array > 64 when , At this time, all the data in this index position is stored in the red black tree .
TreeMap Use
- towards TreeMap Add key-value, requirement key Must be an object created by the same class
- Because we have to take pictures of key Sort ： Natural ordering 、 Custom sort
Use Properties Read configuration file
//Properties: It is often used to process configuration files .key and value All are String type
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
Common methods
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 Sort collection elements 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
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 The old value of the object
explain ：ArrayList and HashMap It's all thread unsafe , If the program requires thread safety , We can ArrayList、HashMap Convert to thread . Use synchronizedList(List list） and synchronizedMap(Map map）