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
Iterator
Objects 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)