the Java Collections Framework
Reference video: [QianFeng] Java Collection Framework Details BV1zD4y1Q7Fw
0. Overview of collections
Purpose: Container of object, which implements common operation on object
Differences from Arrays:
- Array length is fixed, set length is not fixed.
- Arrays deliberately store base and reference types, while collections can only store reference types
Location: java.util. *;
1.Colleection interface
Features: Represents a set of objects of any type, out of order, without subscripts, and cannot be repeated.
Common methods
boolean add(Object obj) //Add an object boolean addAll(Collection c) //Add all objects in a collection to this collection void clear() //Empty all objects boolean contaions(Object o) //Check if this collection type contains o objects boolean equals(Object o) //Compare whether this collection is equal to the specified object boolean isEmpty() //Determine if the set is empty boolean remove(Object o) //Move Objects Out of Collection o int size() //Number of elements in the current collection Object[] toArray() //Convert Collection to Array
Test 1
public class MainTest {
public static void main(String[] args) {
Collection testCollection=new ArrayList();
//Add Elements
System.out.println("==============Add Elements===============");
testCollection.add("A mandarin orange");
testCollectiwon.add("Zhang San");
testCollection.add("Terminal");
testCollection.add("e");
System.out.println("Number of elements:"+testCollection.size());
System.out.println(testCollection.toString());
//Delete element
System.out.println("==============Delete element===============");
testCollection.remove(1);
System.out.println("Number of elements:"+testCollection.size());
System.out.println(testCollection.toString());
//Ordinary traversal elements
System.out.println("=============Ordinary traversal elements=============");
System.out.println("Number of elements:"+testCollection.size());
for(Object x:testCollection){
System.out.println(x.toString());
}
//Iterator traverses elements
System.out.println("=============Iterator traverses elements=============");
System.out.println("Number of elements:"+testCollection.size());
Iterator it=testCollection.iterator();
while(it.hasNext()){
System.out.println(it.next().toString());
// Method cannot be used on testCollection during iterator traversal. Examples include testClooection.remove(e);
// But you can do it.remove()
}
//Determine if the set is empty
System.out.println("===========Determine if the set is empty===========");
System.out.println("Is the collection empty?"+testCollection.isEmpty());
System.out.println("implement clear Method");
testCollection.clear();
System.out.println("Is the collection empty?"+testCollection.isEmpty());
}
}
Test 2
/*
Student Class
*/
public class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
public void setName(String name) {
this.name = name;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" + "name='" + name + '\'' + ", age=" + age + '}';
}
}
public class MainTest {
public static void main(String[] args) {
Collection testCollection=new ArrayList();
Student s1=new Student("Zhang San",18);
Student s2=new Student("Li Si", 20);
Student s3=new Student("King Five", 19);
//Add data The same object can be added repeatedly
System.out.println("=============Add data================");
testCollection.add(s1);
testCollection.add(s2);
testCollection.add(s3);
System.out.println("Number of elements:"+testCollection.size());
System.out.println(testCollection.toString());
//Delete data
System.out.println("=============Delete data================");
testCollection.remove(s3);
System.out.println("Number of elements:"+testCollection.size());
System.out.println(testCollection.toString());
//Traversing data (iterator)
System.out.println("=============Iterator traversal================");
Iterator it=testCollection.iterator();
while(it.hasNext()){
System.out.println(it.next().toString());
}
}
}
2.List interface and implementation class
2.1 List interface
Features: Ordered, Subscript, Repeatable Elements
Common methods
void add(int index, Object o) //Insert object o at index position boolean addAll(index,Collection c) //Add all elements in collection c to the index location of the List collection Object get(int index) //Returns an element in a collection at a specified location List subList(int fromIndex, int toIndex) //Returns the collection element between fromIndex and toIndex
test
public class MainTest {
public static void main(String[] args) {
//Add data The same object can be added repeatedly
List testList=new ArrayList();
testList.add("a");
testList.add("b");
testList.add("d");
testList.add(0,"c");
System.out.println(testList.toString());
//Delete data
testList.remove(0); //Equivalent to testList.remove("c");
//Normal traversal
for(int i=0;i<testList.size();i++){
System.out.println(testList.get(i));
}
//Iterator traversal
System.out.println("Traverse from left to right");
ListIterator it=testList.listIterator();
while(it.hasNext()){
System.out.println(it.next().toString());
}
System.out.println("Traverse from right to left when the above traversal is complete");
while (it.hasPrevious()){
System.out.println(it.previous().toString());
}
//Determine if there is an element "c"
System.out.println(testList.contains("c"));
//Get Location
System.out.println("element b Location:"+testList.indexOf("b"));
//Get Substring
List subTest=testList.subList(1,3);
System.out.println(subTest.toString());
}
}
2.2 List Implementation Class
2.2.1 ArrayList
Array structure, fast query, slow increase. Continuous space needs to be created.
ArrayList Test
public class MainTest {
public static void main(String[] args) {
//Add data The same object can be added repeatedly
ArrayList test=new ArrayList();
Student s1=new Student("Tang", 21);
Student s2=new Student("What", 22);
Student s3=new Student("more than", 21);
test.add(s1);
test.add(s2);
test.add(s3);
System.out.println("Number of elements:"+test.size());
System.out.println(test.toString());
//Delete data
test.remove(s1);
//It cannot be written as a test here. Remove (new Student (Tang, 21));
//The new object here refers to a different object than s1
//Iterator traversal
System.out.println("Traverse from left to right");
ListIterator it=test.listIterator();
while(it.hasNext()){
System.out.println(it.next().toString());
}
System.out.println("Traverse from right to left when the above traversal is complete");
while (it.hasPrevious()){
System.out.println(it.previous().toString());
}
//judge
System.out.println(test.isEmpty());
//Getting location-1 means no locations were found
System.out.println(test.indexOf(s1));
}
}
Source Code Analysis
Default capacity size: private static final int DEFAULT_CAPACITY = 10;
Array holding elements: transient Object[] elementData;
Number of actual elements: private int size;
A parameterless constructor called when an object is created:
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
This source code indicates that when you do not add any elements to the collection, the collection capacity is 0.
The default 10 capacities are related to the following add methods:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Assuming new has an array, the current capacity is zero, and size is of course zero. This calls the add method to enter ensureCapacityInternal(size + 1)
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
elementData is an array of elements, the current capacity is 0, if condition is true, return default capacity DEFAULT_CAPACITY is 10. This value is passed as a parameter into the ensureExplicitCapacity() method, where the source code is viewed:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Known elementData.length=0, so if condition is true, call the grow() function
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
This method first declares an oldCapacity variable to assign it the length of the array with a value of 0. Also declared is a newCapacity variable with a value of oldCapacity+an increment, which you can see is related to the length of the original array, and of course 0 here.
The first if condition is satisfied and newCapacity has a value of 10.
The second if condition is not valid or should not be noticed because MAX_ARRAY_SIZE is defined as follows (very large values):
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
The last sentence is to give elementData a new length, Arrays. The array returned by the copyOf() method is a new array object, the original array object is unchanged, and the copy does not affect the original array. The second variable of copyOf() specifies the length of the new array to be created, and if the length of the new array exceeds the length of the original array, the default value of the array is preserved.
Now go back to the add method and execute elementData[size++] = e down;
2.2.2 Vector
The general content and features are similar to ArrayList and are now less commonly used.
2.2.3 LinkedList
Features: fast increase or delete, slow query. There is no need to open up continuous space.
The general approach is similar to ArrayList
LinkedList Test
public class MainTest {
public static void main(String[] args) {
LinkedList linkedList=new LinkedList<>();
Student s1=new Student("Tang", 21);
Student s2=new Student("What", 22);
Student s3=new Student("more than", 21);
//1. Add Elements
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
linkedList.add(s3);
System.out.println("Number of elements:"+linkedList.size());
System.out.println(linkedList.toString());
//2. Delete elements
/*
* linkedList.remove(new Student("Tang ", 21)";
* System.out.println(linkedList.toString());
*/
//3. Traversal
//3.1 Use for
for(int i=0;i<linkedList.size();++i) {
System.out.println(linkedList.get(i));
}
//3.2 Use enhanced for
for(Object object:linkedList) {
Student student=(Student) object;
System.out.println(student.toString());
}
//3.3 Using Iterators
Iterator iterator =linkedList.iterator();
while (iterator.hasNext()) {
Student student = (Student) iterator.next();
System.out.println(student.toString());
}
//3.4 Use list iterators (omitted)
//4. Judgment
System.out.println(linkedList.contains(s1));
System.out.println(linkedList.isEmpty());
System.out.println(linkedList.indexOf(s3));
}
}
Source Code Analysis
LinkedList first has three properties:
Chain list size: transient int size = 0;
(Pointing) First Node/Head Node: transient Node<E> first;
(Point to) Last Node/End: transient Node <E> last;
Node Type Definition
private static class Node<E> {
E item; //Data for current node
Node<E> next; //Next Node
Node<E> prev; //Last Node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Add elements:
public boolean add(E e) {
linkLast(e); //Tail interpolation
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null); //Initialize the new node to be added
last = newNode;
if (l == null) //Chain list is empty before adding nodes
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
3. Generics and Tool Classes
An overview of generics
Java generics are JDK1. A new feature introduced in 5 is essentially a parameterized type, which is passed as a parameter
Common forms: generic classes, generic interfaces, generic methods
Syntax: <T,...> T is called a placeholder and represents a reference type. It is customary to use letters such as T, E, K, V as placeholders.
Advantage:
- Improving code reuse
- Anti-epidemic type conversion exception to improve code security
3.1 Generic Class
/**
* generic class
* Syntax: Class name <T>
* T Is a type placeholder that represents a reference type and writes multiple entries separated by commas
*
*/
public class myGeneric<T>{
//1. Create generic variables
//You cannot create with new, such as T=new T(), because generics are indeterminate types and may have private construction methods.
T t;
//2. Generics as parameters of methods
public void show(T t) {
System.out.println(t);
}
//Generics as return values of methods
public T getT() {
return t;
}
}
import java.util.*;
import java.lang.*;
public class MainTest {
public static void main(String[] args) {
//Creating objects using generic classes
myGeneric<String> myGeneric1=new myGeneric<String>();
myGeneric1.t="tang";
myGeneric1.show("he");
myGeneric<Integer> myGeneric2=new myGeneric<Integer>();
myGeneric2.t=10;
myGeneric2.show(20);
Integer integer=myGeneric2.getT();
}
}
3.2 Generic Interface
3.2.1 Determining generic classes when implementing interfaces
/**
* generic interface
* Syntax: Interface name <T>
* Note: Generic static constants cannot be created
*/
public interface MyInterface<T> {
//Create Constant
String nameString="tang";
T server(T t);
}
/**
* Determining generic classes when implementing interfaces
*/
public class MyInterfaceImpl implements MyInterface<String>{
@Override
public String server(String t) {
System.out.println(t);
return t;
}
}
test
public class MainTest {
public static void main(String[] args) {
MyInterfaceImpl myInterfaceImpl=new MyInterfaceImpl();
myInterfaceImpl.server("xxx");
}
}
3.2.2 Uncertain generic classes when implementing interfaces
/**
* Uncertain generic class when implementing interface
*/
public class MyInterfaceImpl2<T> implements MyInterface<T>{
@Override
public T server(T t) {
System.out.println(t);
return t;
}
}
public class MainTest {
public static void main(String[] args) {
MyInterfaceImpl myInterfaceImpl=new MyInterfaceImpl();
myInterfaceImpl.server("xxx");
}
}
3.3 Generic Methods
/**
* generic method
* Syntax: <T>Return Type
*/
public class MyGenericMethod {
public <T> void show(T t) {
System.out.println("generic method"+t);
}
}
test
public class MainTest {
public static void main(String[] args) {
MyGenericMethod myGenericMethod=new MyGenericMethod();
myGenericMethod.show("bbbbb");
myGenericMethod.show(123);
myGenericMethod.show(3.14159);
}
}
3.4 Generic Sets
Definition: A parameterized type, type-safe collection, where elements of a mandatory collection must be of the same type
Characteristic:
- Check at compile time instead of throwing exceptions at run time
- There is no need for type conversion (i.e. unboxing) when accessing
- References between different generics cannot be mutually assigned. Generic does not exist polymorphism
public class MainTest {
public static void main(String[] args) {
LinkedList<String>list=new LinkedList<String>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
//list.add(3); Direct error will be reported
System.out.println(list.toString());
}
}
Related Statements
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{...}
If a generic set is used without declaring a relevant generic parameter, that is, new LinkedList<>();, Object types are passed by default.
4.Set interface and implementation class
4.1 Set Interface
Features: Unordered, no subscripts, non-repeatable elements
Method: All methods inherited from Collection
/**
* Test Set Interface Usage
* Features: 1. Unordered, no subscripts; 2. Repeat
* 1.Add data
* 2.Delete data
* 3.ergodic
* 4.judge
*/
public class Demo1 {
public static void main(String[] args) {
Set<String> set=new HashSet<String>();
//1. Add data
set.add("tang");
set.add("he");
set.add("yu");
System.out.println("Number of data:"+set.size());
System.out.println(set.toString());//Output out of order
//2. Delete data
set.remove("tang");
System.out.println(set.toString());
//3.1 Use enhanced for
for (String string : set) {
System.out.println(string);
}
//3.2 Using Iterators
Iterator<String> iterator=set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
//4. Judgment
System.out.println(set.contains("tang"));
System.out.println(set.isEmpty());
}
}
4.2 Set Implementation Class
4.2.1 HashSet
Compute element storage location based on HashCode
When the hashcode s stored in the elements are the same, equals is called to confirm, and if the result is true, storage is rejected
test
/**
* Person class
*/
public class Person {
private String name;
private int age;
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 "Peerson [name=" + name + ", age=" + age + "]";
}
}
/**
* HashSet Use of collections
* Storage structure: Hash table (array + Chain Table + red-black tree)
* 1.Add Elements
* 2.Delete element
* 3.ergodic
* 4.judge
*/
public class Demo3 {
public static void main(String[] args) {
HashSet<Person> hashSet=new HashSet<>();
Person p1=new Person("tang",21);
Person p2=new Person("he", 22);
Person p3=new Person("yu", 21);
//1. Add Elements
hashSet.add(p1);
hashSet.add(p2);
hashSet.add(p3);
//Repeat, add failed
hashSet.add(p3);
//It is not difficult to understand that an object directly new with the same properties will still be added.
//If the same attribute is considered the same object, how can I modify it?
hashSet.add(new Person("yu", 21));
System.out.println(hashSet.toString());
//2. Delete elements
hashSet.remove(p2);
//3. Traversal
//3.1 Enhancement for
for (Person person : hashSet) {
System.out.println(person);
}
//3.2 Iterator
Iterator<Person> iterator=hashSet.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
//4. Judgment
System.out.println(hashSet.isEmpty());
//It is not difficult to understand that the output of an object directly new with the same attribute is false.
//Note: What should I do if the same attribute is considered the same object?
System.out.println(hashSet.contains(new Person("tang", 21)));
}
}
Internal hash table stored procedures
-
Calculate the saved location based on hashCode. If the location is empty, save it directly, otherwise perform the second step.
-
Execute the equals method, and if it returns true, it is considered duplicate and storage is rejected, otherwise a chain table is formed (red-black tree storage is used when the chain table of a location is too long).
Array + Chain Table Form
Array + Red-Black Tree Form
When there are too many nodes for a single hash address, the storage of the same address node will be changed to a red-black tree for easy lookup.
To implement the two-step stored procedure described at the beginning, you can overload hashCode and equals code
@Override
public int hashCode() {
final int prime = 31;
/*Reasons for using 31:
* 1.31 Is a prime number that minimizes hash conflicts when calculating
* 2.Can improve execution efficiency, 31*i=(i< < 5) -i, 31 times a number can be converted to shift operation
*/
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
4.2.2 TreeSet
- Do not repeat based on sort order
- Implements the SortedSet interface to automatically sort collection elements
- Element object type must implement Comparable interface, specify collation
- Determine whether to repeat elements by CompareTo method
Test 1
public class Person implements Comparable<Person>{
private String name;
private int age;
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 +'}';
}
//Overloaded conpareTo method
@Override
public int compareTo(Person o) {
int n1=this.getName().compareTo(o.getName());
int n2=this.getAge()-o.getAge();
return n1==0?n2:n1;
}
}
public class MainTest {
public static void main(String[] args) {
TreeSet<Person> persons=new TreeSet<Person>(new Comparator<Person>() {
//Custom Sorting
@Override
public int compare(Person o1, Person o2) {
int n1=o1.getName().compareTo(o2.getName());
int n2=o1.getAge()-o2.getAge();
return n1==0?n2:n1;
}
});
Person p1=new Person("tang",21);
Person p2=new Person("he", 22);
Person p3=new Person("yu", 21);
persons.add(p1);
persons.add(p2);
persons.add(p3);
for(Person person:persons){
System.out.println(person.toString());
}
}
}
Test 2
/**
* Requirements: Use the TreeSet collection to sort strings by length
* helloworld tangrui hechengyang wangzixu yuguoming
* Comparator Interface implementation custom comparison
*/
public class Demo6 {
public static void main(String[] args) {
TreeSet<String> treeSet=new TreeSet<String>(new Comparator<String>() {
@Override
//Compare string length first
//Compare Strings Again
public int compare(String o1, String o2) {
int n1=o1.length()-o2.length();
int n2=o1.compareTo(o2);
return n1==0?n2:n1;
}
});
treeSet.add("helloworld");
treeSet.add("tangrui");
treeSet.add("hechenyang");
treeSet.add("yuguoming");
treeSet.add("wangzixu");
System.out.println(treeSet.toString());
}
}
5.Map interface and implementation class
5.1 Map interface
Characteristic:
- Used to store any key-value pair.
- Key: out of order, no subscript, no repetition allowed (unique).
- Value: out of order, no subscript, repetition allowed.
Common methods:
V put(K key,V value) //Store objects in a collection, associating key values. Repeated key overrides the original value. Object get(Object key) //Get the corresponding value based on the key. Set<K> //Return all key s Collection<V> values() //Returns a Collection collection containing all values. Set<Map.Entry<K,V>> //Set set set set with key-value matching
public class MainTest {
public static void main(String[] args) {
Map<String,Integer> map=new HashMap<String, Integer>();
//1. Add Elements
map.put("tang", 21);
map.put("he", 22);
map.put("fan", 23);
System.out.println(map.toString());
//2. Delete elements
map.remove("he");
System.out.println(map.toString());
//3. Traversal
//3.1 Use keySet();
for (String key : map.keySet()) {
System.out.println(key+" "+map.get(key));
}
//3.2 Use entrySet(); Higher efficiency
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey()+" "+entry.getValue());
}
}
}
5.2 Map implementation class
5.2.1 HashMap
JDK1. Version 2, thread insecurity, fast running; Allow null as key or value
test
/**
* Student class
*/
public class Student {
private String name;
private int id;
public Student(String name, int id) {
super();
this.name = name;
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
@Override
public String toString() {
return "Student [name=" + name + ", age=" + id + "]";
}
}
/**
* HashMap Use
* Storage structure: Hash table (array + Chain Table + red-black tree)
*/
public class MainTest {
public static void main(String[] args) {
HashMap<Student, String> hashMap=new HashMap<Student, String>();
Student s1=new Student("tang", 36);
Student s2=new Student("yu", 101);
Student s3=new Student("he", 10);
//1. Add Elements
hashMap.put(s1, "Chengdu");
hashMap.put(s2, "Hangzhou");
hashMap.put(s3, "Zhengzhou");
//Add failed, but value will be updated
hashMap.put(s3,"Shanghai");
//Added successfully, but the two attributes are identical;
//Note: If the same attribute is considered to be the same object, how can I modify it?
hashMap.put(new Student("he", 10),"Shanghai");
System.out.println(hashMap.toString());
//2. Delete elements
hashMap.remove(s3);
System.out.println(hashMap.toString());
//3. Traversal
//3.1 Traversal using keySet()
for (Student key : hashMap.keySet()) {
System.out.println(key+" "+hashMap.get(key));
}
//3.2 Traverse using entrySet()
for (Map.Entry<Student, String> entry : hashMap.entrySet()) {
System.out.println(entry.getKey()+" "+entry.getValue());
}
//4. Judgment
//Note: Ibid.
System.out.println(hashMap.containsKey(new Student("he", 10)));
System.out.println(hashMap.containsValue("Chengdu"));
}
}
Like HashSet, you can overload hashCode and equals to customize hash address operations and processing
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Student other = (Student) obj;
if (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
Source Code Analysis
The internal stored procedure looks back at the HashSet section, which is also implemented using map
Default Initialization Capacity: static final int DEFAULT_ INITIAL_ CAPACITY = 1 << 4; // Or 16
Array maximum capacity: static final int MAXIMUM_ CAPACITY = 1 << 30;
Default Load Factor: static final float DEFAULT_LOAD_FACTOR = 0.75f;
Chain list adjusted to chain length threshold of red-black tree (JDK1.8): static final int TREEIFY_THRESHOLD = 8;
Red-Black Tree adjusted to chain list length threshold (JDK1.8): static final int UNTREEIFY_THRESHOLD = 6;
Link list adjusted to array minimum threshold for red-black trees (JDK1.8): static final int MIN_TREEIFY_CAPACITY = 64;
Array stored in HashMap: transient Node<K, V>[] table;
Number of elements stored in HashMap: transient int size;
- What is the default load factor?
- Is a factor that determines whether an array is expanded or not. If the array capacity is 100, HashMap will be expanded if the number of storage elements exceeds 100*0.75=75.
- What is the chain length threshold when the chain list is adjusted to a red-black tree?
- Assuming that the data is already stored in the position subscripted to 3 in the array, and another 3 is obtained by hash code when new data is added, a chain table will be formed at that location. When the chain table is too long, it will be converted to a red-black tree to improve execution efficiency. This threshold is the shortest chain table length from a chain table to a red-black tree.
- What is the chain length threshold for red-black trees to be adjusted to chain lists?
- When the number of elements in a red-black tree is less than this threshold, it is converted to a chain table.
- What is the minimum threshold for arrays with linked lists adjusted to red-black trees?
- It is not possible to convert a chain list to a red-black tree as long as the length of the chain list is greater than 8. If the former is true, the capacity of the array must be greater than or equal to 64 to convert.
HashMap's array table s store one by one ode < K, V > type, clearly showing a pair of key values, and a pointer to the next:
static class Node<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Node<K,V> next;
}
The default size for the first HashMap creation is 0
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Add elements to HashMap
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//Determine if table is empty
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //resize() for resizing
//Determine if one of the locations in the tab to which hashcode arrives is empty, add elements directly for empty
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else{
//......
}
}
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; //Threshold is threshold
if (oldCap > 0){/*......*/};
else if (oldThr > 0){/*......*/};
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
return newTab;
}
When HashMap is just created, threshold=0, enters the third if branch, and the newCap value is initialized to the default of 16.
Next, an array of newCap sizes is created and assigned to the table, where the newly created HashMap object obtains its initial capacity.
Return to the putVal method to execute the second if.
Expansion occurs when more than 16*0.75=12 elements are added
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict){
if (++size > threshold)
resize();
}
final Node<K,V>[] resize() {
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//......
int newCap;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {/*slightly*/}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY){
newThr = oldThr << 1; // double threshold
}
}
//......
}
HashMap in HashSet Source
HashSet's storage structure is HashMap
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
Visibly, the add method in HashSet calls the map's put method, passing in the element as the map's key.
Hashtable
-
JDK1. Version 0, thread-safe and slow; null is not allowed as key or value.
-
Initial capacity 11, load factor 0.75.
This collection is no longer used in the development process, just a little bit more.
Properties
A subclass of Hashtable that requires both key and value to be String. Usually used for reading configuration files. It inherits Hashtable's methods and is closely related to streams, which are not detailed here.
5.2.2 TreeMap
test
/**
* Student class
*/
public class Student implements Comparable<Student>{
private String name;
private int id;
public Student(String name, int id) {
super();
this.name = name;
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
@Override
public String toString() {
return "Student [name=" + name + ", age=" + id + "]";
}
@Override
public int compareTo(Student o) {
int n1 = this.id - o.id;
return n1;
}
}
public class MainTest {
public static void main(String[] args) {
TreeMap<Student, Integer> treeMap=new TreeMap<Student, Integer>();
Student s1=new Student("tang", 36);
Student s2=new Student("yu", 101);
Student s3=new Student("he", 10);
//1. Add Elements
treeMap.put(s1, 21);
treeMap.put(s2, 22);
treeMap.put(s3, 21);
//Can't print directly, need to implement Comparable interface, because red and black trees need to compare sizes
System.out.println(treeMap.toString());
//2. Delete elements
treeMap.remove(new Student("he", 10));
System.out.println(treeMap.toString());
//3. Traversal
//3.1 Use keySet()
for (Student key : treeMap.keySet()) {
System.out.println(key+" "+treeMap.get(key));
}
//3.2 Use entrySet()
for (Map.Entry<Student, Integer> entry : treeMap.entrySet()) {
System.out.println(entry.getKey()+" "+entry.getValue());
}
//4. Judgment
System.out.println(treeMap.containsKey(s1));
System.out.println(treeMap.isEmpty());
}
}
TreeMap in TreeSet
Analogue HashSet and HasMap. The relationship between TreeSet and TreeMap is similar.
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
6.Collections Tool Class
Some commonly used static methods are integrated internally. You can recall the use of the Arrays class
public static void reverse(List<?> list)//Reverse the order of elements in a collection public static void shuffle(List<?> list)//Randomly reset the order of set elements public static void sort(List<T> list)//Ascending sort (element types must implement the Comparable interface)
test
/**
* Demonstrates the use of the Collections tool class
*
*/
public class MainTest {
public static void main(String[] args) {
List<Integer> list=new ArrayList<Integer>();
list.add(20);
list.add(10);
list.add(30);
list.add(90);
list.add(70);
//Sort sort
System.out.println(list.toString());
Collections.sort(list);
System.out.println(list.toString());
System.out.println("---------");
//Binary Search Binary Search
int i=Collections.binarySearch(list, 10);
System.out.println(i);
//copy Copy
List<Integer> list2=new ArrayList<Integer>();
for(int i1=0;i1<5;++i1) {
list2.add(0);
}
//This method requires that the target element capacity be greater than or equal to the source target
Collections.copy(list2, list);
System.out.println(list2.toString());
//reserve inversion
Collections.reverse(list2);
System.out.println(list2.toString());
//shuffle mess
Collections.shuffle(list2);
System.out.println(list2.toString());
//Supplement: list to array
Integer[] arr=list.toArray(new Integer[0]);
System.out.println(arr.length);
//Supplement: Array to set
String[] nameStrings= {"tang","he","yu"};
//Restricted set, cannot add and delete
List<String> list3=Arrays.asList(nameStrings);
System.out.println(list3);
//Note: Basic types need to be modified to wrapper classes when converting to collections
}
}
boolean add(E e) {
return m.put(e, PRESENT)==null;
}
6.Collections Tool Class
Some commonly used static methods are integrated internally. You can recall the use of the Arrays class
public static void reverse(List<?> list)//Reverse the order of elements in a collection public static void shuffle(List<?> list)//Randomly reset the order of set elements public static void sort(List<T> list)//Ascending sort (element types must implement the Comparable interface)
test
/**
* Demonstrates the use of the Collections tool class
*
*/
public class MainTest {
public static void main(String[] args) {
List<Integer> list=new ArrayList<Integer>();
list.add(20);
list.add(10);
list.add(30);
list.add(90);
list.add(70);
//Sort sort
System.out.println(list.toString());
Collections.sort(list);
System.out.println(list.toString());
System.out.println("---------");
//Binary Search Binary Search
int i=Collections.binarySearch(list, 10);
System.out.println(i);
//copy Copy
List<Integer> list2=new ArrayList<Integer>();
for(int i1=0;i1<5;++i1) {
list2.add(0);
}
//This method requires that the target element capacity be greater than or equal to the source target
Collections.copy(list2, list);
System.out.println(list2.toString());
//reserve inversion
Collections.reverse(list2);
System.out.println(list2.toString());
//shuffle mess
Collections.shuffle(list2);
System.out.println(list2.toString());
//Supplement: list to array
Integer[] arr=list.toArray(new Integer[0]);
System.out.println(arr.length);
//Supplement: Array to set
String[] nameStrings= {"tang","he","yu"};
//Restricted set, cannot add and delete
List<String> list3=Arrays.asList(nameStrings);
System.out.println(list3);
//Note: Basic types need to be modified to wrapper classes when converting to collections
}
}
