Collections in Java
Overview of the collection framework
1. Collections and arrays are structures that store multiple data, referred to as Java containers for short
Note: storage at this time only refers to memory level storage, and does not involve persistent storage
2. Array features 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;
2.2. Disadvantages of array in storing multiple data:
- Once initialized, the 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
- Characteristics of array storage data: orderly and repeatable. For unnecessary and non repeatable requirements, they cannot be met.
Java collections can be divided into two systems: Collection and Map
Collection interface: single column data, which defines the collection of methods to access a group of objects
- List: an ordered and repeatable collection of elements
- Set: an unordered and non repeatable set of elements
Map interface: double column data, which saves the set with mapping relationship "key value pair"
Common methods in Collection (with code understanding)
package com.haust.java1;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Date;
public class CollectionTest {
@Test
public void test1(){
Collection collection = new ArrayList();
//add(Object e): adds the element e to the collection
collection.add("AA");
collection.add("BB");
collection.add(123);
collection.add(new Date());
//size(): gets the number of added elements
System.out.println(collection.size());//4
//addAll(): add the elements in collection1 collection to the collection collection
Collection collection1 = new ArrayList();
collection1.add("AA");
collection1.add("BB");
collection1.add(123);
collection1.add(new Date());
collection.addAll(collection1);
System.out.println(collection);
//isEmpty(): judge whether the current collection is empty
System.out.println(collection.isEmpty());//false
//clear(): clear collection elements
collection.clear();
System.out.println(collection.isEmpty());//true
}
}
package com.haust.java;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
/*Collection Testing of methods declared in interfaces
* When adding data obj to the object of the implementation class of the Collection interface, the class of obj is required to override equals()
* */
public class CollectionTest {
@Test
public void test1(){
Collection collection = new ArrayList();
collection.add(123);
collection.add(456);
collection.add(new String("Tom"));
collection.add(false);
collection.add(new Person("Jerry",13));
//contains(Object obj): judge whether the current collection contains obj. When judging, equals() of the class where the obj object is located will be called.
boolean contains = collection.contains(123);
System.out.println(contains);
System.out.println(collection.contains(new String("Tom")));
boolean contains1 = collection.contains(new Person("Jerry", 13));
System.out.println(contains1);
//containsAll(Collection coll1): judge whether all elements in the formal parameter coll1 are in the current collection
Collection collection1 = Arrays.asList(123);
boolean containsAll = collection.containsAll(collection1);
System.out.println(containsAll);
}
@Test
public void test2(){
//remove(Object obj)
Collection collection = new ArrayList();
collection.add(123);
collection.add(456);
collection.add(new String("Tom"));
collection.add(false);
collection.add(new Person("Jerry",13));
collection.remove(123);
System.out.println(collection);
collection.remove(new Person("Jerry",13));
System.out.println(collection);
//Remove all (collection coll1): removes all elements in coll1 from the current collection
Collection collection1 = Arrays.asList(123,456);
collection.removeAll(collection1);
System.out.println(collection);
}
@Test
public void test3(){
Collection collection = new ArrayList();
collection.add(123);
collection.add(456);
collection.add(new String("Tom"));
collection.add(false);
collection.add(new Person("Jerry",13));
//retainAll(Collection collection1) finds the intersection, obtains the intersection of the current collection and collel1 collection, and returns it to the current collection
Collection collection1 = Arrays.asList(123,456,789);
collection.retainAll(collection1);
System.out.println(collection);
// equals(Object obj): to return true, the elements of the current set and the parameter set must be the same
Collection collection2 = new ArrayList();
collection2.add(123);
collection2.add(456);
boolean equals = collection.equals(collection2);
System.out.println(equals);
}
@Test
public void test4(){
Collection collection = new ArrayList();
collection.add(123);
collection.add(456);
collection.add(new String("Tom"));
collection.add(false);
collection.add(new Person("Jerry",13));
//hashCode(): returns the hash value of the current object
System.out.println(collection.hashCode());
//toArray(): convert a collection to an array
Object[] arr = collection.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"});
System.out.println(list);
}
}
Iterator iterators traverse the Collection collection
package com.haust.java;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
/*Collection, using the Iterator iterator interface
* Internal method: use with hasNext() and next() methods*/
public class IteratorTest {
@Test
public void test1(){
Collection collection = new ArrayList();
collection.add(123);
collection.add(456);
collection.add(new String("Tom"));
collection.add(false);
collection.add(new Person("Jerry",13));
Iterator iterator = collection.iterator();
// Mode 1:
// for (int i = 0; i < collection.size(); i++) {
// System.out.println(iterator.next());
// }
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
One of the Collection sub interfaces: List interface
The elements in the List collection are ordered and repeatable, and each element in the collection has its corresponding sequential index.
Interview questions: similarities and differences among ArrayList, LinkedList and Vector
Same as:
- The three classes all implement the List interface. They have the same characteristics of storing data and store orderly and repeatable data
Different:
- ArrayList: as the main implementation class of the List interface; The thread is unsafe and efficient. 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, and the bottom layer uses two-way linked list storage
- Vector: as an ancient implementation class of the List interface, it is thread safe and inefficient. The underlying layer uses Object[] elementData storage
Common methods in List
package com.haust.java;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
/*List Common methods in interfaces
* void add(int index, Object ele): Insert the ele element at the index position
* boolean addAll(int index,Collection eles):Starting from the index position, all elements in eles are added
* Object get(int index): Gets the element at the specified index position. If it does not exist, it returns - 1
* 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):Set the element of the specified Index position to ele
* List subList(int fromIndex,int toIndex):Returns a subset from fromIndex to toIndex
* */
public class ListTest {
@Test
public void test1(){
List list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("Tom",13));
System.out.println(list);
//add()
list.add(1,"bb");
System.out.println(list);
//addAll()
List list1 = Arrays.asList(1,2,3);
list.addAll(list1);
System.out.println(list);
//get()
System.out.println(list.get(0));
int indexOf = list.indexOf(456);
System.out.println(indexOf);
//remove()
Object remove = list.remove(0);
System.out.println(remove);
System.out.println(list);
//set()
list.set(0,"cc");
System.out.println(list);
//subList()
List list2 = list.subList(2, 4);
System.out.println(list2);
}
}
Collection sub interface 2: Set interface
The Set interface stores unordered and non repeatable data
HashSet: as the main implementation class of Set interface; Thread unsafe, can store null value
LinkedHashSet: as a subclass of HashSet, when traversing its internal data, it can be traversed in the order of addition
TreeSet: you can sort according to the specified attributes of the added object.
Process of adding elements: take HashSet as an example:
We want to 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 underlying array of HashSet, find the storage location (i.e. index location) of that array, and judge whether there are elements in this location of the array
If there are no other elements in this position, element a is added successfully - > case 1
If there are other elements (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
equals() returns false, element a is added successfully - > case 3
For cases 2 and 3 where the addition is successful, element a and the data at the existing index position are stored in a linked list
jdk7: element a is placed in the array and points to the original element
jdk8: the original element is in the array, pointing to element a
Conclusion: seven up and eight down
HashSet bottom layer: array + linked list structure
Requirement: the class of the data added to the Set must override the hashCode() and equals() methods
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
Advantages: LinkedHashSet is more efficient than HashSet for frequent traversal operations
TreeSet
package com.haust.java1;
import org.junit.Test;
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
/*TreeSet
* The data added to the TreeSet must be objects of the same class
* Two sorting methods: natural sorting (implementing Comparable interface) and custom sorting
* In natural sorting, the criterion for comparing whether two objects are the same is that compareTo() returns 0 instead of equals()
* In natural sorting, the criterion for comparing whether two objects are the same is that compare() returns 0 instead of equals()
* */
public class TreeSetTest {
@Test
public void test1(){
TreeSet set = new TreeSet();
set.add(123);
set.add(456);
set.add(34);
set.add(-34);
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
@Test
public void test2(){
TreeSet set = new TreeSet();
set.add(new User("Tom",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Jack",65));
set.add(new User("Jack",56));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
@Test
public void test3(){
Comparator comparator = 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());
}
else {
throw new RuntimeException("The data types entered do not match");
}
}
};
TreeSet set = new TreeSet(comparator);
set.add(new User("Tom",12));
set.add(new User("Tom1",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Jack",65));
set.add(new User("Jack",56));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
Map interface
Implementation class structure of Map:
HashMap: as the main implementation class of Map, the thread is unsafe and efficient. It can store null key s and value s
LinkedHashMap: ensure that the map elements can be traversed in the order of addition. Reason: on the basis of the original HashMap, a pile of pointers are added to point to the previous and subsequent elements. For frequent traversal operations, this kind of execution efficiency is higher than that of HashMap.
TreeMap: ensure to sort according to the added key value pairs and realize sorting traversal. In this case, consider the natural sorting or natural sorting of keys. Red and black trees are used at the bottom.
Hashtable: as an ancient implementation class, it is thread safe and inefficient. It cannot store null key s and value s
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 (jdk8)
Understanding of Map structure
Keys in Map: unordered and non repeatable. Use Set to store all key s, ---- > 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
Entry in Map: unordered and non repeatable. Set is used to store the required entry
Interview questions:
1. The underlying implementation principle of HashMap?
JDK7:
- HashMap map = new HashMap(); After instantiation, the bottom layer creates a one-dimensional array with a length of 16 Entry[] table. ...It may have been performed multiple times put... map.put(key1,value1); First, calculate key1 Class hashCode()calculation key1 Hash value, which is calculated by some algorithm Entry The storage location in the array. If the data at this location is empty, at this time, key1-value1 Added successfully——>Situation 1 If the data in this location is not empty, (it means that there are one or more data in this location (in the form of linked list)), compare key1 Hash value with one or more existing data: If key1 Both the hash value of and the hash value of the existing data are unsuccessful. At this time key1-value1 Added successfully——>Situation II If key1 The hash value of is the same as that of an existing data. Continue to compare: call key1 Class equals()Method, comparison: If equals()return false,here key1-value1 Added successfully——>Situation III If equals()return true，Use at this time value1 replace value2. Add: about case 2 and case 3: at this time key1-value1 And the original data are stored in a linked list In the process of continuous addition, capacity expansion will be involved. When the critical value is exceeded (and the storage location is not empty), capacity expansion will be carried out. The default capacity expansion method is to double the original capacity and copy the original data
The underlying implementation of JDK8 is different from that of jdk7:
1. new HashMap(): the underlying layer does not create an array with a length of 16
2. The array at the bottom of jdk8 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 has only array + linked list at the bottom. Underlying data structure in JDK8: array + linked list + red black tree
When the data format of an element at an index position of a macro in the array in the form of a linked list is > 8 and the length of the current array is > 64, all data at this index position will be stored using a red black tree.
2. What are the similarities and differences between HashMap and Hashtable?
See above
Methods defined in Map
package com.haust.java;
/*Map:Double column data, storing data of key value pairs -- similar to the function y = f(x) of high school*/
import org.junit.Test;
import java.util.*;
/*
* Map Methods defined in
* 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
* 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
*
* Methods of meta view 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
* */
public class MapTest {
@Test
public void test1(){
Map map = new HashMap();
//add to
map.put("AA",123);
map.put("BB",123);
map.put("CC",562);
//modify
map.put("AA",89);
Map map1 = new HashMap();
map1.put("DD",123);
map1.put("EE",123);
map.putAll(map1);
System.out.println(map);
Object value = map.remove("AA");
System.out.println(value);
System.out.println(map);
//clear()
map1.clear();
System.out.println(map1);
//get()
Object ee = map.get("EE");
System.out.println(ee);
boolean bb = map.containsKey("BB");
System.out.println(bb);
boolean b = map.containsValue(123);
System.out.println(b);
int size = map.size();
System.out.println(size);
}
@Test
public void test2(){
Map map = new HashMap();
//add to
map.put("AA",123);
map.put("BB",123);
map.put("CC",562);
//Traverse all key sets: keySet()
Set set = map.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
//Traverse all value sets: values()
Collection values = map.values();
Iterator iterator1 = values.iterator();
while (iterator1.hasNext()){
System.out.println(iterator1.next());
}
//Traverse all key values
//entrySet()
Set set1 = map.entrySet();
Iterator iterator2 = set1.iterator();
while (iterator2.hasNext()){
System.out.println(iterator2.next());
}
}
}
Collections are utility classes that operate on lists, sets, and maps
Interview question: what is the difference between Collection and Collections?
Collection is a collection interface, and Collections is a tool class for operating List, Set and Map
Common methods in Collections:
package com.haust.java;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
/*Collection It is a tool class for operating List, Set and Map
* Interview question: what is the difference between Collection and Collections?
*reverse(List): Reverse the order of elements in the List
* shuffle(List):Random sorting of List collection elements
* sort(List):Sorts the specified List collection elements in ascending order according to the natural ordering of the elements
* sort(List,Comparator):Sorts the List collection elements according to the order generated by the specified Comparator
* swap(List,int,int):Exchange the i element and j element of the specified list set
*
* Object max(Collection):Returns the largest element in a given set based on the natural ordering of elements
* Object max(Collection,Comparator):Returns the largest element in a given collection in the order specified by the Comparator
* Object min(Collection):Returns the smallest element in a given set according to the natural ordering of elements
* Object min(Collection,Comparator):Returns the smallest element in a given collection in the order specified by the 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 list,Object oldVal,Object newVal):Replace the old value corresponding to the list with the new value
*
* 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
*
* */
public class CollectionsTest {
@Test
public void test1(){
List list = new ArrayList();
list.add(123);
list.add(123);
list.add(43);
list.add(765);
list.add(-97);
list.add(0);
System.out.println(list);
System.out.println("*****reverse()*****");
Collections.reverse(list);
System.out.println(list);
System.out.println("****shuffle()*****");
Collections.shuffle(list);
System.out.println(list);
System.out.println("*******sort()****");
Collections.sort(list);
System.out.println(list);
System.out.println("*******max()********");
Comparable max = Collections.max(list);
System.out.println(max);
System.out.println("*******min()********");
Comparable min = Collections.min(list);
System.out.println(min);
System.out.println("*******frequenct()********");
int frequency = Collections.frequency(list, 123);
System.out.println(frequency);
System.out.println("******copy()******");
List list1 = new ArrayList();
list1.add(132);
list1.add(56);
list1.add(88);
list1.add(45);
Collections.copy(list,list1);
System.out.println(list);
}
}