Java collection introduction and in-depth learning, see this article is almost

Java City Conqueror 2020-11-10 11:24:58
java collection introduction in-depth depth


One 、 Collection introduction summary

《2020 newest Java Basic video tutorial and learning route !》

Collections framework :

Java The set framework in can be divided into Collection and Map; The difference between the two :

1、Collection Is a single column set ;Map Is a two column set

2、Collection There are only Set Series requires elements to be unique ;Map The middle key needs to be unique , Values can be repeated

3、Collection The data structure of is for elements ;Map The data structure of is key specific .

Generic :

Before we talk about the two systems of sets, let's talk about generics , Because we will use it in the following sets ; The so-called generics are : Parameterization of type

Generics are part of a type , Class name + Generics are a whole

If there are generics , When not in use , The type of the parameter is automatically promoted to Object type , If you take it out again, you need to force it down , A type conversion exception may occur (ClassCaseException); Without generics, you can't add the type of an element to a compile time directed collection , Lead to the trouble of later processing .
Here's the difference between adding generics and not adding generics :

package Study hard java;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
public static void main(String[] args) {
// Without generics , Add and traverse
List list = new ArrayList<>();
list.add(1);
list.add("123");
list.add("hello");
Iterator it = list.iterator();
while(it.hasNext()){
// No generics added , Only... Can be used here Object receive
Object obj = it.next();
System.out.println(obj);
}
}
}
package Study hard java;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
public static void main(String[] args) {
// Add generics , Add and traverse
List<String> list = new ArrayList<String>();
list.add("123");
list.add("hello");
Iterator<String> it = list.iterator();
while(it.hasNext()){
// Because of the addition of generics , It means that all the contents in the collection are String Data of type
// So here we use String Type reception , No exceptions , And you can use String Methods
String str = it.next();
System.out.println(str.length());
}
}
}
Copy code 

Custom classes with generics :

package Study hard java;
public class Test {
// Customize a generic class with one parameter , You can pass in whatever type you can
public static void main(String[] args) {
// To test , Pass in a String object
Person<String> perStr = new Person<String>();
perStr.setT(" I'm a string ");
String str = perStr.getT();
System.out.println(str);
// To test , Pass in a Integer object
Person<Integer> perInt = new Person<Integer>();
perInt.setT(100);
Integer intVal = perInt.getT();
System.out.println(intVal);
}
}
// Customize a generic class with one parameter
class Person<T>{
private T t;
void setT(T t){
this.t = t;
}
T getT(){
return t;
}
}
Copy code 

Implement interface types with generics :

While implementing the interface , Specifies the generic type in the interface . ( Determine when defining a class );

public class GenericImpl1 implements GenericInter<String> {}
Copy code 

When implementing the interface , The generic type in the interface was not specified . here , The implementation class of the interface needs to be defined as a generic class . The type of the interface needs to be determined when the implementation class object is created . ( Always uncertain about the type , Until the object is created, the type is determined );

public class GenericImpl2<T> implements GenericInter<T> {}
Copy code 

Generic wildcards (?):

The upper limit is : For example, when defining methods ,public void getFunc(List<? extends Animal> an),

Then it means that the parameters here can be passed in Animal, perhaps Animal Subclasses of

Lower limit limit : For example, when defining methods ,public void getFunc(Set<? super Animal> an ),

Then it means that the parameters here can be passed in Animal, perhaps Animal Parent class of

Note on using generics :

1、 Generics do not support basic data types

2、 Generics don't support inheritance , It has to be consistent ( For example, this is wrong :List<Object> list = new ArrayList<String>();

Collection system :

ollection There are two systems ,List and Set

List Characteristics :

Access is in order , There is an index , You can take values according to the index , Elements can be repeated

Set Characteristics :

Access disorder , Elements cannot be repeated

List:

There is ArrayList,LinkedList,Vector( Deprecated )

The biggest purpose of a collection is to access ;List Collection is characterized by orderly access , Can store duplicate elements , You can use subscripts to manipulate elements

ArrayList: The bottom layer is implemented using arrays , So the query speed is fast , The speed of adding and deleting is slow

package Study hard java;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
// Use ArrayList Add and traverse
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add(" Interface 1");
list.add(" Interface 2");
list.add(" Interface 3");
// The first way to traverse , Using Iterators
Iterator<String> it = list.iterator();
while(it.hasNext()){
String next = it.next();
System.out.println(next);
}
System.out.println("-------------------");
// The second way to traverse , Use foreach
for (String str : list){
System.err.println(str);
}
}
}
Copy code 

LinkedList: It is based on the linked list structure , So the query speed is slow , The speed of adding and deleting is fast , Provides a special way , Operations on the elements of the head and tail ( Add, delete and check ).

Use LinkedList To implement stacks and queues ; Stack is first in first out , And the queue is first in, first out

package com.xiaoshitou.classtest;
import java.util.LinkedList;
/**
* utilize LinkedList To simulate stack
* The characteristics of the stack : First in, then out
* @author Beck
*
*/
public class MyStack {
private LinkedList<String> linkList = new LinkedList<String>();
// Pressing stack
public void push(String str){
linkList.addFirst(str);
}
// Out of the stack
public String pop(){
return linkList.removeFirst();
}
// see
public String peek(){
return linkList.peek();
}
// Determine whether it is null
public boolean isEmpty(){
return linkList.isEmpty();
}
}
package Study hard java;
public class Test {
public static void main(String[] args) {
// Test stack
StackTest stack = new StackTest();
stack.push(" I am the first 1 One went in ");
stack.push(" I am the first 2 One went in ");
stack.push(" I am the first 3 One went in ");
stack.push(" I am the first 4 One went in ");
stack.push(" I am the first 5 One went in ");
// Take out
while (!stack.isEmpty()){
String pop = stack.pop();
System.out.println(pop);
}
// Print the results
/* I am the first 5 One went in
I am the first 4 One went in
I am the first 3 One went in
I am the first 2 One went in
I am the first 1 One went in */
}
}
Copy code 

LinkedList Realization Queue:

package Study hard java;
import java.util.LinkedList;
/**
* utilize linkedList To implement the queue
* queue : fifo
* @author Beck
*
*/
public class QueueTest {
private LinkedList<String> link = new LinkedList<String>();
// Put in
public void put(String str){
link.addFirst(str);
}
// obtain
public String get(){
return link.removeLast();
}
// Determine whether it is null
public boolean isEmpty(){
return link.isEmpty();
}
}
package Study hard java;
public class Test {
public static void main(String[] args) {
// Test queue
QueueTest queue = new QueueTest();
queue.put(" I am the first 1 People in the queue ");
queue.put(" I am the first 2 People in the queue ");
queue.put(" I am the first 3 People in the queue ");
queue.put(" I am the first 4 People in the queue ");
// Traverse the queue
while (!queue.isEmpty()){
String str = queue.get();
System.out.println(str);
}
// Print the results
/* I am the first 1 People in the queue
I am the first 2 People in the queue
I am the first 3 People in the queue
I am the first 4 People in the queue */
}
}
Copy code 

Vector: Because it's out of date , By ArrayList To replace the ; It also has an iterator through vector.elements() obtain , The method of judging whether there are elements and getting elements is :hasMoreElements(),nextElement().

package Study hard java;
import java.util.Enumeration;
import java.util.Vector;
public class Test {
public static void main(String[] args) {
Vector<String> vector = new Vector<String>();
vector.add(" Search for ");
vector.add("vector");
vector.add("list");
Enumeration<String> elements = vector.elements();
while (elements.hasMoreElements()){
String nextElement = elements.nextElement();
System.out.println(nextElement);
}
}
}
Copy code 

Set:

Set Set characteristics : Elements do not repeat , Access disorder , No subscript Set There's :HashSet,LinkedHashSet,TreeSet

HashSet Store string :

package Study hard java;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Test {
public static void main(String[] args) {
// utilize HashSet To access
Set<String> set = new HashSet<String>();
set.add(" My day, ");
set.add(" I repeat ");
set.add(" I repeat ");
set.add("welcome");
// Traverse The first way iterator
Iterator<String> it = set.iterator();
while(it.hasNext()){
String str = it.next();
System.out.println(str);
}
System.out.println("--------------");
for (String str : set){
System.out.println(str);
}
// Print the results , The repetition has been removed
/* My day,
welcome
I repeat
--------------
My day,
welcome
I repeat */
}
Copy code 

How does hash table guarantee the uniqueness of elements , Hash table is through hashCode and equals Methods to jointly guarantee .

Hash table stored data procedures ( The underlying hash table also maintains an array ):

Calculate from the stored elements hashCode value , And then according to the calculation hashCode Value and the length of the array to calculate the stored subscript ; If the position of the subscript has no element , So direct storage ; If there are elements , Then use the element to be stored and the element equals Method , If the result is true , There are already the same elements , So it doesn't exist ; If it turns out to be false , So store it , In the form of a linked list .

demonstration HashSet To store custom objects :

package Study hard java;
public class Person {
// attribute
private String name;
private int age;
// Construction method
public Person() {
super();
}
public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}
// Let the hash table store non duplicate elements , It has to be rewritten hasCode and equals Method
@Override
public int hashCode() {
final int prime = 31;
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;
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
// getter & setter
...
}
package Study hard java;
import java.util.HashSet;
import java.util.Set;
public class Test {
public static void main(String[] args) {
// utilize HashSet To access custom objects Person
Set<Person> set = new HashSet<Person>();
set.add(new Person(" Zhang San ", 12));
set.add(new Person(" Li Si ", 13));
set.add(new Person(" Wang Wu ", 22));
set.add(new Person(" Zhang San ", 12));
// Traverse
for (Person p : set){
System.out.println(p);
}
// result : Store two Zhang San objects in the collection , But one of them is successfully stored in the collection
/*Person [name= Wang Wu , age=22]
Person [name= Li Si , age=13]
Person [name= Zhang San , age=12]*/
}
}
Copy code 

So in the HashSet When a custom object is stored in a collection , In order to ensure set The uniqueness of sets , So you have to rewrite hashCode and equals Method .

LinkedHashSet:

It is based on linked list and hash table , So it has access order , Element uniqueness

package Study hard java;
import java.util.LinkedHashSet;
public class Test {
public static void main(String[] args) {
// utilize LinkedHashSet To access custom objects Person
LinkedHashSet<Person> set = new LinkedHashSet<Person>();
set.add(new Person(" Zhang San ", 12));
set.add(new Person(" Li Si ", 13));
set.add(new Person(" Wang Wu ", 22));
set.add(new Person(" Zhang San ", 12));
// Traverse
for (Person p : set){
System.out.println(p);
}
// result : Store two Zhang San objects in the collection , But one of them is successfully stored in the collection ,
// And the order in which they are stored , It's consistent with the order in which it's taken out
/*Person [name= Zhang San , age=12]
Person [name= Li Si , age=13]
Person [name= Wang Wu , age=22]*/
}
}
Copy code 

TreeSet:

characteristic : Access disorder , Element uniqueness , You can sort ( Sorting is to sort when adding ).

TreeSet It's a data structure based on binary tree , Binary tree : You can't have more than two nodes under a node .

Binary tree stored procedures :

If it's the first element , Then deposit it directly , As root node , The next element will be compared with the node , If it's larger than the node on the right , Smaller than the node on the left ; Equals a node, it doesn't store . The following elements will be compared in turn , Until there's a location to store

TreeSet Collective storage String object

package Study hard java;
import java.util.TreeSet;
public class Test {
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<String>();
treeSet.add("abc");
treeSet.add("zbc");
treeSet.add("cbc");
treeSet.add("xbc");
for (String str : treeSet){
System.out.println(str);
}
// result : The results are sorted
/*
abc
cbc
xbc
zbc*/
}
}
Copy code 

TreeSet There are two ways to ensure the uniqueness of an element :

1、 Custom object implementations Comparable Interface , rewrite comparaTo Method , This method returns 0 It means equal , Less than 0 Indicates that the element to be stored is smaller than the element being compared , Otherwise, it is greater than 0;

2、 Creating TreeSet The comparator is passed into the constructor Comparator Interface implementation class object , Realization Comparator Interface rewriting compara Method .

If to TreeSet When saving a custom object , The custom class does not implement Comparable Interface , Or it didn't come in Comparator When comparator , There will be ClassCastException abnormal

Here are two ways to store custom objects

package Study hard java;
public class Person implements Comparable<Person>{
// attribute
private String name;
private int age;
// Construction method
public Person() {
super();
}
public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}
// Let the hash table store non duplicate elements , It has to be rewritten hasCode and equals Method
@Override
public int hashCode() {
final int prime = 31;
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;
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
// getter & setter
...
@Override
public int compareTo(Person o) {
int result = this.age - o.age;
if (result == 0){
return this.name.compareTo(o.name);
}
return result;
}
}
package Study hard java;
import java.util.TreeSet;
public class Test {
public static void main(String[] args) {
// utilize TreeSet To store custom classes Person object
TreeSet<Person> treeSet = new TreeSet<Person>();
// Person Class implements the Comparable Interface , And rewrite comparaTo Method
// The rule of comparison is first according to Age ranking , Age equality is ranked by age
treeSet.add(new Person(" Zhang Shan 1", 20));
treeSet.add(new Person(" Zhang Shan 2", 16));
treeSet.add(new Person(" Zhang Shan 3", 13));
treeSet.add(new Person(" Zhang Shan 4", 17));
treeSet.add(new Person(" Zhang Shan 5", 20));
for (Person p : treeSet){
System.out.println(p);
}
// result : according to comparaTo Method to sort
/*
Person [name= Zhang Shan 3, age=13]
Person [name= Zhang Shan 2, age=16]
Person [name= Zhang Shan 4, age=17]
Person [name= Zhang Shan 1, age=20]
Person [name= Zhang Shan 5, age=20]
*/
}
}
Copy code 

Another way : Using a comparator Comparator

package Study hard java;
public class Person{
// attribute
private String name;
private int age;
// Construction method
public Person() {
super();
}
public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}
// Let the hash table store non duplicate elements , It has to be rewritten hasCode and equals Method
@Override
public int hashCode() {
final int prime = 31;
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;
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
// getter & setter
...
}
package Study hard java;
import java.util.Comparator;
import java.util.TreeSet;
public class Test {
public static void main(String[] args) {
// utilize TreeSet To store custom classes Person object
// establish TreeSet When the object is passed in Comparator The comparator , Using anonymous inner classes
// The rule of comparison is first according to Age ranking , Age equality is ranked by age
TreeSet<Person> treeSet = new TreeSet<Person>(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
if (o1 == o2){
return 0;
}
int result = o1.getAge() - o2.getAge();
if (result == 0){
return o1.getName().compareTo(o2.getName());
}
return result;
}
});
treeSet.add(new Person(" Zhang Shan 1", 20));
treeSet.add(new Person(" Zhang Shan 2", 16));
treeSet.add(new Person(" Zhang Shan 3", 13));
treeSet.add(new Person(" Zhang Shan 4", 17));
treeSet.add(new Person(" Zhang Shan 5", 20));
for (Person p : treeSet){
System.out.println(p);
}
// result : according to compara Method to sort
/*
Person [name= Zhang Shan 3, age=13]
Person [name= Zhang Shan 2, age=16]
Person [name= Zhang Shan 4, age=17]
Person [name= Zhang Shan 1, age=20]
Person [name= Zhang Shan 5, age=20]
*/
}
}
Copy code 

Comparator summary :

Collection System summary :

  • List : " characteristic :" Access is in order , Element has index , Elements can be repeated .
  • ArrayList : Array structure , Quick query , Add or delete slowly , Thread unsafe , So it's efficient .
  • Vector : Array structure , Quick query , Add or delete slowly , Thread safety , So it's inefficient .
  • LinkedList : Chain table structure , Slow query , Additions and deletions quickly , Thread unsafe , So it's efficient .
 addFirst() removeFirst() getFirst()
Copy code 
  • Set :" characteristic :" Access disorder , Element has no index , Elements cannot be repeated .
  • HashSet : Storage disorder , Element has no index , Elements cannot be repeated . At the bottom is the hash table .
Excuse me, : How does a hash table ensure that the elements are unique ? At the bottom is dependence hashCode and equals Method .

When storing elements , First, according to hashCode + The length of the array Calculate an index , Determine whether there are elements in the index position .

If there is no element , Direct storage , If there are elements , First judge equals Method , Compare whether the two elements are the same , If it's different, store it , If you are the same, you give up .

The elements stored in our custom objects must be implemented hashCode and equals.

  • LinkedHashSet : Storage order , Elements cannot be repeated .
  • TreeSet : Access disorder , But it can be sorted ( Natural ordering ), Elements cannot be repeated .

There are two ways to sort :

  • Natural ordering :

Our elements must implement Comparable Interface . Comparable . Realization CompareTo Method .

  • Comparator sort :

We need custom classes , Realization Comparetor Interface , This class is the comparator implementation compare Method .

And then in creating TreeSet When , Pass the comparator object as an argument to TreeSet.

Map:

Map Is a two column set , What is saved is the key value pair , The key requires uniqueness , Values can be repeated

Key values are one-to-one , A key can only correspond to one value

Map Characteristics : It's access disorder , Key is not repeatable

Map At the time of storage , Pass the key value in Entry, Then store Entry object

There are the following HashMap,LinkedHashMap and TreeMap

HashMap:

It is based on hash table structure , So when you store a custom object as a key , Must be rewritten hasCode and equals Method . Access is out of order

The following demonstration HashMap Take the custom object as the key :

package Study hard java;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;
public class Test {
public static void main(String[] args) {
// utilize HashMap Storage , Custom object Person As key
// In order to guarantee the uniqueness of the key , Must be rewritten hashCode and equals Method
HashMap<Person,String> map = new HashMap<Person,String>();
map.put(new Person(" Zhang San ", 12), "JAVA");
map.put(new Person(" Li Si ", 13), "IOS");
map.put(new Person(" floret ", 22), "JS");
map.put(new Person(" Little black ", 32), "PHP");
map.put(new Person(" Zhang San ", 12), "C++");
Set<Entry<Person, String>> entrySet = map.entrySet();
Iterator<Entry<Person, String>> it = entrySet.iterator();
while (it.hasNext()){
Entry<Person, String> entry = it.next();
System.out.println(entry.getKey() + "---" + entry.getValue());
}
// result : Two cards were added to the deposit , If Map When the middle keys are the same , When the latter value will override the previous value
/*
Person [name= Li Si , age=13]---IOS
Person [name= Zhang San , age=12]---C++
Person [name= Little black , age=32]---PHP
Person [name= floret , age=22]---JS
*/
}
}
Copy code 

LinkedHashMap:

Usage follows HashMap Almost the same , It is based on the structure of linked list and hash table, so it has access order , The fact that the key doesn't repeat

Let's show you how to use LinkedHashMap Storage , Note that the order of storage is consistent with the order of traversal :

package Study hard java;
import java.util.LinkedHashMap;
import java.util.Map.Entry;
public class Test {
public static void main(String[] args) {
// utilize LinkedHashMap Storage , Custom object Person As key
// In order to guarantee the uniqueness of the key , Must be rewritten hashCode and equals Method
LinkedHashMap<Person,String> map = new LinkedHashMap<Person,String>();
map.put(new Person(" Zhang San ", 12), "JAVA");
map.put(new Person(" Li Si ", 13), "IOS");
map.put(new Person(" floret ", 22), "JS");
map.put(new Person(" Little black ", 32), "PHP");
map.put(new Person(" Zhang San ", 12), "C++");
// foreach Traverse
for (Entry<Person,String> entry : map.entrySet()){
System.out.println(entry.getKey()+"==="+entry.getValue());
}
// result : Two cards were added to the deposit , If Map When the middle keys are the same , When the latter value will override the previous value
// Be careful :LinkedHashMap It is characterized by orderly access , The order of extraction is consistent with the order of deposit
/*
Person [name= Zhang San , age=12]===C++
Person [name= Li Si , age=13]===IOS
Person [name= floret , age=22]===JS
Person [name= Little black , age=32]===PHP
*/
}
}
Copy code 

TreeMap:

to TreeMap Collection to save custom objects , Custom object as TreeMap A collection of key value . because TreeMap The binary tree used at the bottom , All the data stored in it needs to be sorted , To sort , The object is required to have the function of comparison . The class that the object belongs to needs to implement Comparable Interface . Or to TreeMap Set passes a Comparator Interface object .

utilize TreeMap Save custom object as key :

package Study hard java;
import java.util.Comparator;
import java.util.Map.Entry;
import java.util.TreeMap;
public class Test {
public static void main(String[] args) {
// utilize TreeMap Storage , Custom object Person As key
// Custom object implementations Comparable Interface or pass in Comparator The comparator
TreeMap<Person,String> map = new TreeMap<Person,String>(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
if (o1 == o2){
return 0;
}
int result = o1.getAge() - o2.getAge();
if (result == 0){
return o1.getName().compareTo(o2.getName());
}
return result;
}
});
map.put(new Person(" Zhang San ", 12), "JAVA");
map.put(new Person(" Li Si ", 50), "IOS");
map.put(new Person(" floret ", 32), "JS");
map.put(new Person(" Little black ", 32), "PHP");
map.put(new Person(" Zhang San ", 12), "C++");
// foreach Traverse
for (Entry<Person,String> entry : map.entrySet()){
System.out.println(entry.getKey()+"==="+entry.getValue());
}
// result : Two cards were added to the deposit , If Map When the middle keys are the same , When the latter value will override the previous value
// Be careful :TreeMap The order is sorted , It's based on compara Method ordered
/*
Person [name= Zhang San , age=12]===C++
Person [name= floret , age=32]===JS
Person [name= Little black , age=32]===PHP
Person [name= Li Si , age=50]===IOS
*/
}
}
Copy code 

Two 、 Set advanced summary

Arrays and first class objects

No matter what type of array is used , Array identifier is actually a handle to the real object . Those objects themselves are in memory “ Pile up ” Created in . Heap objects can be “ Implicit ” establish ( By default ), Yes “ Explicit ” establish ( That is to say, to specify , Use one new expression ). Part of the heap object ( It's actually the only field or method we can access ) Is read-only length( length ) member , It tells How many elements can we hold in that array object . For array objects ,“ []” Syntax is the only alternative access method we can use .

Object array and basic data type array are almost identical in usage . The only difference is that the array of objects holds handles , And the basic data type array holds specific values

public class ArraySize {
public static void main(String[] args) {
// Arrays of objects:
Weeble[] a; // Null handle
Weeble[] b = new Weeble[5]; // Null handles
Weeble[] c = new Weeble[4];
for (int i = 0; i < c.length; i++)
c[i] = new Weeble();
Weeble[] d = { new Weeble(), new Weeble(), new Weeble() };
// Compile error: variable a not initialized:
// !System.out.println("a.length=" + a.length);
System.out.println("b.length = " + b.length);
// The handles inside the array are
// automatically initialized to null:
for (int i = 0; i < b.length; i++)
System.out.println("b[" + i + "]=" + b[i]);
System.out.println("c.length = " + c.length);
System.out.println("d.length = " + d.length);
a = d;
System.out.println("a.length = " + a.length);
// Java 1.1 initialization syntax:
a = new Weeble[] { new Weeble(), new Weeble() };
System.out.println("a.length = " + a.length);
// Arrays of primitives:
int[] e; // Null handle
int[] f = new int[5];
int[] g = new int[4];
for (int i = 0; i < g.length; i++)
g[i] = i * i;
int[] h = { 11, 47, 93 };
// Compile error: variable e not initialized:
// !System.out.println("e.length=" + e.length);
System.out.println("f.length = " + f.length);
// The primitives inside the array are
// automatically initialized to zero:
for (int i = 0; i < f.length; i++)
System.out.println("f[" + i + "]=" + f[i]);
System.out.println("g.length = " + g.length);
System.out.println("h.length = " + h.length);
e = h;
System.out.println("e.length = " + e.length);
// Java 1.1 initialization syntax:
e = new int[] { 1, 2 };
System.out.println("e.length = " + e.length);
}
}
Copy code 
Output is as follows : b.length = 5 b[0]=null b[1]=null b[2]=null b[3]=null b[4]=null c.length = 4 d.length = 3 a.length = 3 a.length = 2 f.length = 5 f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=0 g.length = 4 h.length = 3 e.length = 3 e.length = 2

among , Array a It's just initialized to a null Handle . here , The compiler will prohibit us from doing any actual operations on this handle , Unless it is already It's really initialized . Array b Is initialized to point to by Weeble An array of handles , But that array doesn't actually put any Weeble object . However , We can still query the size of that array , because b It's pointing to a legitimate object .

In other words , We only know the size or capacity of array objects , I don't know how many elements it actually contains .

For all that , Since array objects are automatically initialized to null, So check whether it is null, Judging a specific array “ vacancy ” Whether to hold an object . Similarly , An array of basic data types is automatically initialized to zero ( For numeric types )、 null( Character type ) perhaps false( Boolean type )

Array c It shows that we first create an array object , then Weeble Object is assigned to all of the “ vacancy ”. Array d Revealed “ Set initialization ” grammar , To create an array object ( use new The order was made clear , It's like an array c), And then use Weeble Object to carry out initialization , All the work is done in one sentence . The following expression :

a = d;
Copy code 

Shows us how to get a handle to the same array of objects , Then assign it to another array object , Shows us how to get a handle to the same array of objects , Then assign it to another array object

1. Set of basic data types Collection classes can only hold object handles . But for an array , However, it can directly accommodate the basic types of data , It can also hold sentences pointing to objects Handle . Use the image Integer、 Double And so on. “ wrapper ” class , You can put the values of a basic data type into a set .

Whether you put basic types of data into arrays , Or encapsulate it into a class in the collection , It's all about efficiency . display however , If you can create and access an array of basic data types , So rather than accessing a collection of encapsulated data , The former is much more efficient .

Array return

Suppose we want to write a method now , And don't want it to return just one thing , It's about returning a series of things . here , like C and C++ Such language can complicate the problem , Because we can't return an array , Only one pointer to an array can be returned . This is very troublesome , Because it's hard to control the array of “ Time to live ”, It's easy to create memory “ Loophole ” Appearance .

Java It's a similar approach , But we can “ Returns an array ”. Of course , At this point, the actual return is still the pointer to the array . But in Java in , We never have to worry about the availability of that array —— As long as you need , It will exist automatically . And the garbage collector will automatically clear it after we finish

public class IceCream {
static String[] flav = { "Chocolate", "Strawberry", "Vanilla Fudge Swirl",
"Mint Chip", "Mocha Almond Fudge", "Rum Raisin", "Praline Cream",
"Mud Pie" };
static String[] flavorSet(int n) {
// Force it to be positive & within bounds:
n = Math.abs(n) % (flav.length + 1);
String[] results = new String[n];
int[] picks = new int[n];
for(int i = 0; i < picks.length; i++)
picks[i] = -1;
for(int i = 0; i < picks.length; i++) {
retry:
while(true) {
int t =(int)(Math.random() * flav.length);
for(int j = 0; j < i; j++)213
if(picks[j] == t) continue retry;
picks[i] = t;
results[i] = flav[t];
break;
}
}
return results;
}
public static void main(String[] args) {
for (int i = 0; i < 20; i++) {
System.out.println("flavorSet(" + i + ") = ");
String[] fl = flavorSet(flav.length);
for (int j = 0; j < fl.length; j++)
System.out.println("t" + fl[j]);
}
}
}
Copy code 

flavorSet() Method creates a named results Of String Array . The size of the array is n—— The exact value depends on the independent variable we pass to the method . And then , It comes from the array flav I'll pick some at random “ spice ”( Flavor), And put them in results in , And finally back to results. Returning an array is no different than returning any other object —— The final return is a handle .

On the other hand , Pay attention to when flavorSet() When choosing spices at random , It needs to make sure that a random selection that happened before doesn't happen again . To this end , It uses an infinite while loop , Constantly making random choices , Until we found out that it wasn't there picks Until an element in the array appears ( Of course , You can also compare strings , Check if random selection is in results In the array , But string comparison is less efficient ). If successful , Just add this element , And break the loop ( break), Find the next one ( i The value is incremented ). But if t It's one who's already in picks The array that appears in , Just label it continue Jump back two levels , Force the selection of a new t. You can see this process clearly with a debugger .

aggregate

To accommodate a set of objects , The best choice should be an array . And if it holds a set of basic data types , It is necessary to use arrays .

shortcoming : Type unknown

Use Java A collection of “ shortcoming ” It is the loss of type information when putting objects into a collection . The reason why this happens , It's because when you wrote the collection , The programmer of that collection has no idea what type of set the user wants to put into the collection . If it is indicated that only specific types are allowed for a collection , Will prevent it from becoming a “ Conventional use ” Tools for , Bring trouble to users . To solve this problem , The collection actually holds the type Object Handle to some objects of .

Of course , Also note that the set does not include basic data types , Because they don't come from “ Anything ” inherited . Java People are not allowed to abuse the objects placed in the set . If you throw a dog into a collection of cats , Then you still think of everything in the collection as a cat , So when you use that dog, you get a “ Violation ” error . In the same sense , If you try to put a dog's handle “ modelling ” To a cat , Then you still get a “ Violation ” error

class Cat {
private int catNumber;
Cat(int i) {
catNumber = i;
}
void print() {
System.out.println("Cat #" + catNumber);
}
}
class Dog {
private int dogNumber;
Dog(int i) {
dogNumber = i;
}
void print() {
System.out.println("Dog #" + dogNumber);
}
}
public class CatsAndDogs {
public static void main(String[] args) {
Vector cats = new Vector();
for (int i = 0; i < 7; i++)
cats.addElement(new Cat(i));
// Not a problem to add a dog to cats:
cats.addElement(new Dog(7));
for (int i = 0; i < cats.size(); i++)
((Cat) cats.elementAt(i)).print();
// Dog is detected only at run-time
}
}
Copy code 
  • Mistakes sometimes don't show up In some cases , The program seems to work correctly , No styling back to our original type . The first is quite special : String Class gets additional help from the compiler , Make it work . As long as the compiler expects a String object , But it didn't get one , It will automatically call in Object It defines 、 And can be done by any Java Class toString() Method . This method can generate String object , And then use it when we need it . therefore , In order to show the objects of your own class , All you have to do is cover toString() Method .
class Mouse {
private int mouseNumber;
Mouse(int i) {
mouseNumber = i;
}
// Magic method:
public String toString() {
return "This is Mouse #" + mouseNumber;
}
void print(String msg) {
if (msg != null)
System.out.println(msg);
System.out.println("Mouse number " + mouseNumber);
}
}
class MouseTrap {
static void caughtYa(Object m) {
Mouse mouse = (Mouse) m; // Cast from Object
mouse.print("Caught one!");
}
}
public class WorksAnyway {
public static void main(String[] args) {
Vector mice = new Vector();
for(int i = 0; i < 3; i++)
mice.addElement(new Mouse(i));
for(int i = 0; i < mice.size(); i++) {
// No cast necessary, automatic call
// to Object.toString():
System.out.println(
"Free mouse: " + mice.elementAt(i));
MouseTrap.caughtYa(mice.elementAt(i));
}
}
}
Copy code 

Can be found in Mouse I see right toString() Redefinition code for . stay main() The second for In circulation , The following statements can be found :

System.out.println("Free mouse: " +
mice.elementAt(i));
Copy code 

stay “ +” after , What the compiler expects to see is a String object . elementAt() It generates a Object, So for the sake of hope String, By default, the compiler calls toString(). But unfortunately , Only for String To get results like this ; No other type will do this conversion .

The second way to hide shapes is already in Mousetrap It's got applications in . caughtYa() Method does not receive a Mouse, It is a Object. And then it's shaped like a Mouse. Of course , It's very presumptuous to do so , Because by receiving a Object, Anything can be passed on to a method . However , If the shape is not correct —— If we pass on the wrong type —— You'll get a violation error during runtime . This, of course, is not checked at compile time , But it can still prevent problems from happening . Note that there is no need to shape when using this method : MouseTrap.caughtYa(mice.elementAt(i));

  • Generate automatic type discrimination Vector One is more “ robust ” The solution is to use Vector Create a new class , Make it accept only what we specify type , It only generates the type we want .
class Gopher {
private int gopherNumber;
Gopher(int i) {
gopherNumber = i;
}
void print(String msg) {
if (msg != null)
System.out.println(msg);
System.out.println("Gopher number " + gopherNumber);
}
}
class GopherTrap {
static void caughtYa(Gopher g) {
g.print("Caught one!");
}
}
class GopherVector {
private Vector v = new Vector();
public void addElement(Gopher m) {
v.addElement(m);
}
public Gopher elementAt(int index) {
return (Gopher) v.elementAt(index);
}
public int size() {
return v.size();
}
public static void main(String[] args) {
GopherVector gophers = new GopherVector();
for (int i = 0; i < 3; i++)
gophers.addElement(new Gopher(i));
for (int i = 0; i < gophers.size(); i++)
GopherTrap.caughtYa(gophers.elementAt(i));
}
}
Copy code 

new GopherVector Class has a type of Vector Of private member ( from Vector There's some trouble with inheriting , The reason will be known later ), And the method is also the same as Vector similar . However , It doesn't receive and produce ordinary Object, Only right Gopher object Interested in . because GopherVector Receive only one Gopher( Gophers ), So if we use : gophers.addElement(new Pigeon()); You get an error message during compilation . In this way , Although it's more boring from a coding point of view , But you can immediately tell if the right type is used . Pay attention to use elementAt() You don't have to shape —— It must be a Gopher

Enumerator

Accommodating a variety of objects is the primary task of a collection . stay Vector in , addElement() That's how we insert objects , and elementAt() yes The only way to extract objects . Vector Very flexible , We can choose anything at any time , And you can use different indexes to select multiple elements . If you look at the problem from a higher point of view , You'll find a flaw in it : You need to know the exact type of set in advance , Otherwise it won't work . At first glance , That doesn't seem to matter . But if you decide to use it in the first place Vector, Later, it was decided in the procedure that ( Consider the reasons for execution efficiency ) Change it into a List( Belong to Java1.2 Part of the collection library ), What should I do now ? We usually think of the repeater as a kind of “ Lightweight ” object ; in other words , It costs very little to create it . But that's why , We often find that there are some strange restrictions on repeaters . for example , Some repeaters can only move in one direction . Java Of Enumeration( enumeration , notes ②) An example of a repeater with these limitations . In addition to the following , Don't use it again Do anything else : (1) Use a name elements() The method requires the collection to provide us with a Enumeration. We called it for the first time nextElement() when , This Enumeration Returns the first element in the sequence . (2) use nextElement() Get the next object . (3) use hasMoreElements() Check if there are more objects in the sequence

class Hamster {
private int hamsterNumber;
Hamster(int i) {
hamsterNumber = i;
}
public String toString() {
return "This is Hamster #" + hamsterNumber;
}
}
class Printer {
static void printAll(Enumeration e) {
while (e.hasMoreElements())
System.out.println(e.nextElement().toString());
}
}
public class HamsterMaze {
public static void main(String[] args) {
Vector v = new Vector();
for (int i = 0; i < 3; i++)
v.addElement(new Hamster(i));
Printer.printAll(v.elements());
}
}
Copy code 

Study the printing method carefully :

static void printAll(Enumeration e) {
while(e.hasMoreElements())
System.out.println(
e.nextElement().toString());
}
Copy code 

Note that there is no information about the sequence type . All we have is Enumeration. To learn about the sequence , One Enumeration That's enough : You can get the next object , We can also know if we have reached the end . Take a series of objects , And then traverse through it , To perform a specific operation —— This is a valuable programming concept

Type of collection

V e c t o r

collapse Java Java The standard set contains toString() Method , So they can generate their own String The way of expression , Including the objects they hold . For example, in Vector in , toString() Will be in Vector Step and traverse through the elements of , And call... For each element toString(). Suppose we want to print out the address of our class now . It seems as if simply quoting this that will do ( especially C++ Programmers have a tendency to do this ):

public class CrashJava {
public String toString() {
return "CrashJava address: " + this + "n";
}
public static void main(String[] args) {
Vector v = new Vector();
for (int i = 0; i < 10; i++)
v.addElement(new CrashJava());
System.out.println(v);
}
}
Copy code 

What happens here is the automatic type conversion of the string . When we use the following statements : “CrashJava address: ” + this The compiler found a string right after it “ +” And other things that don't seem to be strings , So it will try to put this Convert to a string . The conversion calls toString(), The latter generates a recursive call . If it's in one Vector This kind of thing happens inside , It looks like the stack will overflow , At the same time, the violation control mechanism has no chance to respond . If you really want to print out the address of the object in this case , The solution is to call Object Of toString Method . There's no need to add this, Just use super.toString(). Of course , There is also a premise for this approach : We have to go from Object Direct inheritance , Or there is no parent class that covers toString Method .

B i t S e t

BitSet It's actually from “ Binary digit ” It's made up of Vector. If you want to save a lot of “ open - Turn off ” Information , It should be used BitSet. It only makes sense in terms of size ; If you want efficient access , Then it's going to be slower than using arrays of some intrinsic type . BitSet The minimum length of is a long integer ( Long) The length of : 64 position . That means if we're going to save smaller data than this , Such as 8 Bit data , that BitSet It's wasteful . So it's better to create your own classes , Use it to hold your own logo .

S t a c k

Stack Sometimes it can also be called “ After the first out ”( LIFO) aggregate . In other words , We end up in the stack “ Push the ” What will be the next One “ eject ” Of . And everything else Java Like a collection , What we press in and pop out is “ object ”, So you have to do something you pop up Conduct “ modelling ”. Here's a simple example of a stack , It can read every line of the array , And push it on the stack as a string .

public class Stacks {
static String[] months = { "January", "February", "March", "April", "May",
"June", "July", "August", "September", "October", "November",
"December" };
public static void main(String[] args) {
Stack stk = new Stack();
for (int i = 0; i < months.length; i++)
stk.push(months[i] + " ");
System.out.println("stk = " + stk);
// Treating a stack as a Vector:
stk.addElement("The last line");
System.out.println("element 5 = " + stk.elementAt(5));
System.out.println("popping elements:");
while (!stk.empty())
System.out.println(stk.pop());
}
}
Copy code 

months Each row of the array passes through push() Inheritance goes into the stack , Later on pop() Take it out of the top of the stack . One thing to make clear is ,Vector The operation can also be directed at Stack Object to carry out . This may be determined by the nature of inheritance —— Stack“ Belong to ” A kind of Vector. therefore , Be able to Vector The operation can also be carried out for Stack Conduct , for example elementAt() Method

H a s h t a b l e

Vector Allows us to choose from a series of objects with a number , So it actually associates numbers with objects . But what if we want to choose a range of objects based on other criteria ? The stack is an example of this : Its selection criteria are “ The last thing on the stack ”. such “ Choose from a list of objects ” The concept of is also called a “ mapping ”、“ Dictionaries ” perhaps “ Associative array ”. conceptually , It looks like a Vector, But it's not looking for objects by numbers , It's using another object to find them ! This usually belongs to an important process in a program . stay Java in , This concept is reflected in the abstract class Dictionary On the body . The interface of this class is very intuitive size() Tell us how many elements it contains ; isEmpty() Determine whether elements are included ( Yes, it is true); put(Object key, Object value) Add a value ( What we want ), And associate it with a key ( What you want to use to search for it ); get(Object key) Get the value corresponding to a key ; and remove(Object Key) Used to remove from the list “ key - value ” Yes . You can also use enumeration techniques : keys() Generate an enumeration of keys ( Enumeration); and elements() Produces an enumeration of all values . This is a Dict ionary( Dictionaries ) All .

public class AssocArray extends Dictionary {
private Vector keys = new Vector();
private Vector values = new Vector();
public int size() {
return keys.size();
}
public boolean isEmpty() {
return keys.isEmpty();
}
public Object put(Object key, Object value) {
keys.addElement(key);
values.addElement(value);
return key;
}
public Object get(Object key) {
int index = keys.indexOf(key);
// indexOf() Returns -1 if key not found:
if (index == -1)
return null;
return values.elementAt(index);
}
public Object remove(Object key) {
int index = keys.indexOf(key);
if (index == -1)
return null;
keys.removeElementAt(index);
Object returnval = values.elementAt(index);
values.removeElementAt(index);
return returnval;
}
public Enumeration keys() {
return keys.elements();
}
public Enumeration elements() {
return values.elements();
}
// Test it:
public static void main(String[] args) {
AssocArray aa = new AssocArray();
for (char c = 'a'; c <= 'z'; c++)
aa.put(String.valueOf(c), String.valueOf(c).toUpperCase());
char[] ca = { 'a', 'e', 'i', 'o', 'u' };
for (int i = 0; i < ca.length; i++)
System.out.println("Uppercase: " + aa.get(String.valueOf(ca[i])));
}
}
Copy code 

In the face of AssocArray The definition of , The first problem we noticed was that it “ Expand ” Dictionary . It means AssocArray Belong to Dictionary A type of , So it can be sent out with Dictionary The same request . If you want to make your own Dictionary, And it's happening right here , So all you have to do is just fill in Dictionary All the methods in ( And it has to cover all methods , because they —— In addition to the builder —— It's all abstract ). standard Java The library contains only Dictionary A variation of , be known as Hashtable( Hash table , notes ③). Java The hash table of has and AssocArray Same interface ( Because both are derived from Dictionary inherited ). But one aspect reflects the difference : Execution efficiency . If you think about it, it has to be for a get() Do the things , You'll find in a Vector The search key is much slower . But using hash table can speed up a lot . You don't have to use lengthy linear search techniques to find a key , But with a special value , be known as “ Hash code ”. Hash code can get the information in the object , And then convert it to that object “ Relatively unique ” The integer of ( int). All objects have a hash code , and hashCode() It's the root class Object One way . Hashtable Get the object's hashCode(), And then use it to quickly find the key .

class Counter {
int i = 1;
public String toString() {
return Integer.toString(i);
}
}
class Statistics {
public static void main(String[] args) {
Hashtable ht = new Hashtable();
for (int i = 0; i < 10000; i++) {
// Produce a number between 0 and 20:
Integer r = new Integer((int) (Math.random() * 20));
if (ht.containsKey(r))
((Counter) ht.get(r)).i++;
else
ht.put(r, new Counter());
}
System.out.println(ht);
}
}
Copy code 
  • establish “ The key ” class But when you use hash tables , Once we create our own class as a key to make use , There is a very common problem . for example , Suppose a weather forecast system will Groundhog( Earth suckling mice ) Object matches to Prediction( prediction ) . It looks very intuitive : We create two classes , And then Groundhog Use as a key , And will be Prediction Use as a value . As shown below :
class Groundhog {
int ghNumber;
Groundhog(int n) {
ghNumber = n;
}
}
class Prediction {
boolean shadow = Math.random() > 0.5;
public String toString() {
if (shadow)
return "Six more weeks of Winter!";
else
return "Early Spring!";
}
}
public class SpringDetector {
public static void main(String[] args) {
Hashtable ht = new Hashtable();
for (int i = 0; i < 10; i++)
ht.put(new Groundhog(i), new Prediction());
System.out.println("ht = " + ht + "n");
System.out.println("Looking up prediction for groundhog #3:");
Groundhog gh = new Groundhog(3);
if (ht.containsKey(gh))
System.out.println((Prediction) ht.get(gh));
}
}
Copy code 

The problem lies in Groundhog It's from universal Object The root class inherits ( If you didn't mean Base class , Then all classes end up from Object inherited ). In fact, it's with Object Of hashCode() Method to generate a hash code for each object , And by default, only the address of its object is used . therefore , Groundhog(3) The first instance of does not produce a relationship with Groundhog(3) The second example is the equivalent hash code , And we use the second instance to retrieve Maybe think that all that needs to be done at this time is to correctly cover hashCode(). But it still works , Unless you do something else : Covering also belongs to Object Part of equals(). When the hash table tries to determine whether our key is equal to a key in the table , You will use this method . similarly , default Object.equals() It's just a simple comparison of object addresses , So a Groundhog(3) Is not the same as the other one Groundhog(3). therefore , To use your own class as a key in a hash table , Must cover... At the same time hashCode() and equals(), As shown below :

class Groundhog {
int ghNumber;
Groundhog(int n) {
ghNumber = n;
}
}
class Prediction {
boolean shadow = Math.random() > 0.5;
public String toString() {
if (shadow)
return "Six more weeks of Winter!";
else
return "Early Spring!";
}
}
public class SpringDetector {
public static void main(String[] args) {
Hashtable ht = new Hashtable();
for (int i = 0; i < 10; i++)
ht.put(new Groundhog(i), new Prediction());
System.out.println("ht = " + ht + "n");
System.out.println("Looking up prediction for groundhog #3:");
Groundhog gh = new Groundhog(3);
if (ht.containsKey(gh))
System.out.println((Prediction) ht.get(gh));
}
}
Copy code 

Groundhog2.hashCode() Returns the woodchuck number as an identifier ( In this case , Programmers need to make sure that no two marmots use the same ID Numbers coexist ). To return a unique identifier , It doesn't need to hashCode(), equals() Method must be able to strictly determine whether two objects are equal . equals() There are two kinds of tests : Check whether the object is null; If not null , Then continue to check whether it is Groundhog2 An example of ( Want to use instanceof keyword ). Even in order to carry on equals(), It should also be a Groundhog2. As you can see , This comparison is based on the fact that ghNumber On the basis of . This time, once we run the program , You'll see that it's finally producing the right output ( many Java The classes of the library are covered with hashcode() and equals() Method , In order to adapt to the content provided by oneself ).

On enumerator again

Separate operations that traverse a sequence from the infrastructure of that sequence . In the following example , PrintData Class uses one Enumeration Moving through a sequence , And call... For each object toString() Method . Two different types of collections are created : One Vector And a Hashtable. And fill in them separately charge Mouse and Hamster object , because Enumeration Hiding the structure of the base set , therefore PrintData Don't know or care about Enumeration From what kind of collection :

class PrintData {
static void print(Enumeration e) {
while (e.hasMoreElements())
System.out.println(e.nextElement().toString());
}
}
class Enumerators2 {
public static void main(String[] args) {
Vector v = new Vector();
for (int i = 0; i < 5; i++)
v.addElement(new Mouse(i));
Hashtable h = new Hashtable();
for (int i = 0; i < 5; i++)
h.put(new Integer(i), new Hamster(i));
System.out.println("Vector");
PrintData.print(v.elements());
System.out.println("Hashtable");
PrintData.print(h.elements());
}
}
Copy code 

Be careful PrintData.print() Using the objects in these collections to belong to Object This is the fact that , So it calls toString(). But in When you solve your own practical problems , Always make sure you have your own Enumeration Through a particular type of collection . for example , May require a collection of All elements in are one Shape( Geometry ), And it contains draw() Method . If this happens , Must be from Enumeration.nextElement() Back to Object Do the backtracking modeling , In order to produce a Shape.

Sort

When writing general sort code , One of the problems is that the comparison must be performed according to the actual type of the object , In order to achieve the right sort . Of course , One way is to write a different sort method for each different type . However , It should be recognized that if this is done , It is not easy to reuse the code when new types are added later . One of the main goals of programming is “ Separate what has changed from what remains unchanged ”. ad locum , The immutable code is a general sort algorithm , What changes every time it is used is the actual comparison method of the object . therefore , We can't compare code “ Hard encoding ” Into several different sort routines , instead “ Callback ” technology . Using callbacks , The part of the code that often changes is encapsulated in its own class , And always keep the same code “ Callback ” Changed code . thus , Different objects can express different ways of comparison , And pass them the same sort code . The following “ Interface ”( Interface) Shows how to compare two objects , It will take those “ Something to change ” It's packaged in :

interface Compare {
boolean lessThan(Object lhs, Object rhs);
boolean lessThanOrEqual(Object lhs, Object rhs);
}
Copy code 

For both methods , lhs This is for the comparison “ left hand ” object , and rhs representative “ one 's right hand ” object . Can create Vector A subclass of , adopt Compare Realization “ Quick sort ”. For this algorithm , Including its speed and principle and so on

public class SortVector extends Vector {
private Compare compare; // To hold the callback
public SortVector(Compare comp) {
compare = comp;
}
public void sort() {
quickSort(0, size() - 1);
}
private void quickSort(int left, int right) {
if (right > left) {
Object o1 = elementAt(right);
int i = left - 1;
int j = right;
while (true) {
while (compare.lessThan(elementAt(++i), o1))
;
while (j > 0)
if (compare.lessThanOrEqual(elementAt(--j), o1))
break; // out of while
if (i >= j)
break;
swap(i, j);
}
swap(i, right);
quickSort(left, i - 1);
quickSort(i + 1, right);
}
}
private void swap(int loc1, int loc2) {
Object tmp = elementAt(loc1);
setElementAt(elementAt(loc2), loc1);
setElementAt(tmp, loc2);
}
}
Copy code 

For the use of SortVector, You have to create a class , Make it ready for us to sort the object implementation Compare. Inner classes are not particularly important at this point , But it's good for the organization of the code . The following is for String An example of an object

public class StringSortTest {
static class StringCompare implements Compare {
public boolean lessThan(Object l, Object r) {
return ((String) l).toLowerCase().compareTo(
((String) r).toLowerCase()) < 0;
}
public boolean lessThanOrEqual(Object l, Object r) {
return ((String) l).toLowerCase().compareTo(
((String) r).toLowerCase()) <= 0;
}
}
public static void main(String[] args) {
SortVector sv = new SortVector(new StringCompare());
sv.addElement("d");
sv.addElement("A");
sv.addElement("C");
sv.addElement("c");
sv.addElement("b");
sv.addElement("B");
sv.addElement("D");
sv.addElement("a");
sv.sort();
Enumeration e = sv.elements();
while (e.hasMoreElements())
System.out.println(e.nextElement());
}
}
Copy code 

Once the framework is set up , It's very easy to reuse a design like this —— Simply write a class , take “ It needs to change ” We're going to wrap it in , Then pass an object to SortVector that will do Inherit ( extends) Used here to create a new type of Vector—— in other words , SortVector Belong to a kind of Vector, And with some additional features . Inheritance can play a big role here , But it brings problems . It makes some methods have final attribute , So you can't cover them . If you want to create an ordered Vector, Make it only receive and generate String object , You'll get into trouble . because addElement() and elementAt() All have final attribute , And they're all methods that we have to cover , Otherwise, it can't be realized, only receive and produce String object . But on the other hand , Please consider using “ synthesis ” Method : Put an object inside a new class . here , It's not rewriting the code to do this , It's a simple use of a new class SortVector. under these circumstances , Used to implement Compare The inner class of the interface can be “ anonymous ” Create

import java.util.*;
public class StrSortVector {
private SortVector v = new SortVector(
// Anonymous inner class:
new Compare() {
public boolean lessThan(Object l, Object r) {
return ((String) l).toLowerCase().compareTo(
((String) r).toLowerCase()) < 0;
}
public boolean lessThanOrEqual(Object l, Object r) {
return ((String) l).toLowerCase().compareTo(
((String) r).toLowerCase()) <= 0;
}
});
private boolean sorted = false;
public void addElement(String s) {
v.addElement(s);
sorted = false;
}
public String elementAt(int index) {
if(!sorted) {
v.sort();232
sorted = true;
}
return (String)v.elementAt(index);
}
public Enumeration elements() {
if (!sorted) {
v.sort();
sorted = true;
}
return v.elements();
}
// Test it:
public static void main(String[] args) {
StrSortVector sv = new StrSortVector();
sv.addElement("d");
sv.addElement("A");
sv.addElement("C");
sv.addElement("c");
sv.addElement("b");
sv.addElement("B");
sv.addElement("D");
sv.addElement("a");
Enumeration e = sv.elements();
while (e.hasMoreElements())
System.out.println(e.nextElement());
}
}
Copy code 

New collection

 Picture description here

This picture may be a little confusing at the beginning , I believe you will really understand that it actually has only three collection components : Map, List and Set. And each component actually has only two 、 Three ways of implementation The dotted box represents “ Interface ”, Dot and wireframe represent “ abstract ” class , And solid wireframes represent ordinary ( actual ) class . The dotted arrow indicates that a specific class is ready to implement an interface ( In the case of abstract classes , It is “ part ” Implement an interface ). The double arrow indicates that a class can generate objects of the class that the arrow points to . The interface dedicated to holding objects is Collection, List, Set and Map. In traditional circumstances , We need to write a lot of code to deal with these interfaces . And in order to specify the exact type you want to use , It must be set at the beginning of creation . So it's possible to create the following one individual List:

List x = new LinkedList();
Copy code 

Of course , You can also decide to x As a LinkedList Use ( Not an ordinary List), And use x Load accurate type information . The benefit of using interfaces is that once you decide to change your implementation details , All you have to do is change it as you create it , It's like this :

List x = new ArrayList();
Copy code 

In the hierarchical structure of a class , You can see a lot of “ Abstract ”( abstract ) Initial class , This can be confusing at first . They are actually tools , be used for “ part ” Implement a specific interface . For example , If you want to create your own Set, Not from Set Interface start , And then implement all the methods on your own . contrary , We can AbstractSet Inherit , You can get your own new class with very little work . For all that , The new collection library still contains enough functionality , It can meet almost all our needs . So considering our purpose , All can be ignored with “ Abstract” Initial class . therefore , When you look at this diagram , The only thing that really needs to be concerned about is at the top “ Interface ” And ordinary ( actual ) class —— They are surrounded by solid line boxes . You usually need to generate an object of the actual class , It is modeled as the corresponding interface . You can then use that interface anywhere in the code . Here is a simple example , It USES String Objects fill a collection , Then print out each element in the collection :

public class SimpleCollection {
public static void main(String[] args) {
Collection c = new ArrayList();
for (int i = 0; i < 10; i++)
c.add(Integer.toString(i));
Iterator it = c.iterator();
while (it.hasNext())
System.out.println(it.next());
}
}
Copy code 

main() The first line of creates a ArrayList object , And then we can shape it up into a collection . Because this example only uses Collection Method , So from Collection Any object of an inherited class can work properly . but ArrayList It's a typical Collection, It replaces Vector The location of . add() The function of the method is to put a new element into the set . However , The user documentation carefully points out that add()“ Ensure that the collection contains the specified elements ”. This is for Set To pave the way , The latter will only add that element if it doesn't exist . about ArrayList And any other form of List, add() It must mean “ Directly to join ”. utilize iterator() Method , All sets can generate a “ Repeater ”( Iterator). The repeater is actually like a “ enumeration ”( Enumeration), It's a substitute for the latter , It's just : (1) It uses a historical default 、 And as early as OOP A widely adopted name in ( Repeater ). (2) It used the ratio Enumeration Shorter names : hasNext() Instead of hasMoreElement(), and next() Instead of nextElement(). (3) Added a name called remove() New method of , Can be deleted by Iterator The last element generated . So every time I call next() When , Just call remove() once

Use C o l l e c t i o n s

The following table summarizes all the things you can do with a set ( And it can be true Set and List Do the same thing , Even though List It also provides a Some extra features ). Map Not from Collection inherited , So treat... Alone

boolean add(Object) * Ensure that the set contains the arguments . If it doesn't add arguments , Just go back to false( false ) boolean addAll(Collection) * Add all the elements in the argument . If you don't add elements , Then return to true( really ) void clear() * Delete all elements in the collection boolean contains(Object) If the set contains arguments , Just go back to “ really ” boolean containsAll(Collection) If the set contains all the elements in the argument , Just go back to “ really ” boolean isEmpty() If there are no elements in the set , Just go back to “ really ” Iterator iterator() Return to a repeater , To traverse the elements of a collection boolean remove(Object) * If the independent variable is in a set , Just delete an instance of that element . If a deletion has been made , Just go back to “ really ” boolean removeAll(Collection) * Delete all the elements in the argument . If any deletions have been made , Just go back to “ really ” boolean retainAll(Collection) * Keep only the elements contained in an argument ( A theoretical “ intersection ”). If you have entered Any changes made , Just go back to “ really ” int size() Returns the number of elements in the collection Object[] toArray() Returns an array containing all the elements in the collection * This is a “ Optional ” Method , Some collections may not implement it . If so , This method will encounter a UnsupportedOperatiionException, That is, a “ Operation does not support ” Violation .

The following example shows you all the methods . similarly , They are only valid for things inherited from a collection , One ArrayList As a kind of “ An unusual denominator ” Use

public class Collection1 {
// Fill with 'size' elements, start
// counting at 'start':
public static Collection fill(Collection c, int start, int size) {
for (int i = start; i < start + size; i++)
c.add(Integer.toString(i));
return c;
}
// Default to a "start" of 0:
public static Collection fill(Collection c, int size) {
return fill(c, 0, size);
}
// Default to 10 elements:
public static Collection fill(Collection c) {
return fill(c, 0, 10);
}
// Create & upcast to Collection:
public static Collection newCollection() {
return fill(new ArrayList());
// ArrayList is used for simplicity, but it's
// only seen as a generic Collection
// everywhere else in the program.
}
// Fill a Collection with a range of values:
public static Collection newCollection(int start, int size) {
return fill(new ArrayList(), start, size);
}
// Moving through a List with an iterator:
public static void print(Collection c) {
for (Iterator x = c.iterator(); x.hasNext();)
System.out.print(x.next() + " ");
System.out.println();
}
public static void main(String[] args) {
Collection c = newCollection();
c.add("ten");
c.add("eleven");
print(c);
// Make an array from the List:
Object[] array = c.toArray();
// Make a String array from the List:
String[] str = (String[]) c.toArray(new String[1]);
// Find max and min elements; this means
// different things depending on the way
// the Comparable interface is implemented:
System.out.println("Collections.max(c) = " + Collections.max(c));
System.out.println("Collections.min(c) = " + Collections.min(c));
// Add a Collection to another Collection
c.addAll(newCollection());
print(c);
c.remove("3"); // Removes the first one
print(c);
c.remove("3"); // Removes the second one
print(c);
// Remove all components that are in the
// argument collection:
c.removeAll(newCollection());
print(c);
c.addAll(newCollection());
print(c);
// Is an element in this Collection?
System.out.println("c.contains("4") = " + c.contains("4"));
// Is a Collection in this Collection?
System.out.println("c.containsAll(newCollection()) = "
+ c.containsAll(newCollection()));
Collection c2 = newCollection(5, 3);
// Keep all the elements that are in both
// c and c2 (an intersection of sets):
c.retainAll(c2);
print(c);
// Throw away all the elements in c that
// also appear in c2:
c.removeAll(c2);
System.out.println("c.isEmpty() = " + c.isEmpty());
c = newCollection();
print(c);
c.clear(); // Remove all elements
System.out.println("after c.clear():");
print(c);
}
} Copy code 

newCollection() Both versions of created ArrayList, Used to contain different datasets , And return them as collection objects . So obviously , except Collection Beyond the interface , It won't use anything else .

Use L i s t s

List( Interface ) The order is List The most important feature ; It ensures that the elements are arranged in the specified order . List by Collection Added a lot of methods , So that we can List Insert and delete elements in the middle ( Only recommend to LinkedList To do so ). List It will also generate a ListIterator( List repeater ), It can be used to traverse in two directions in a list , Insert and delete elements in the middle of the list at the same time ( similarly , It's only recommended that you treat LinkedList To do so ) ArrayList Derived from an array List. Use as a general purpose object container , Used to replace the original Vector. Allows us to quickly access elements , But when you insert and delete elements from the middle of the list , It's a little slow . Generally, you should only use ListIterator To a ArrayList Traverse forward and backward , Don't use it to delete and insert elements ; And LinkedList comparison , It's much less efficient LinkedList Provides optimized sequential access performance , At the same time, it can efficiently insert and delete in the middle of the list . But in random access , It's quite slow , At this time, we should use ArrayList. Also provided addFirst(), addLast(), getFirst(),getLast(), removeFirst() as well as removeLast()( Is not defined in any interface or underlying class ), In order to make it a specification 、 Queues and a two-way queue use

public class List1 {
// Wrap Collection1.fill() for convenience:
public static List fill(List a) {
return (List) Collection1.fill(a);
}
// You can use an Iterator, just as with a
// Collection, but you can also use random
// access with get():
public static void print(List a) {
for (int i = 0; i < a.size(); i++)
System.out.print(a.get(i) + " ");
System.out.println();
}
static boolean b;
static Object o;
static int i;
static Iterator it;
static ListIterator lit;
public static void basicTest(List a) {
a.add(1, "x"); // Add at location 1
a.add("x"); // Add at end
// Add a collection:
a.addAll(fill(new ArrayList()));
// Add a collection starting at location 3:
a.addAll(3, fill(new ArrayList()));
b = a.contains("1"); // Is it in there?
// Is the entire collection in there?
b = a.containsAll(fill(new ArrayList()));
// Lists allow random access, which is cheap
// for ArrayList, expensive for LinkedList:
o = a.get(1); // Get object at location 1
i = a.indexOf("1"); // Tell index of object
// indexOf, starting search at location 2:
i = a.indexOf("1", 2);
b = a.isEmpty(); // Any elements inside?
it = a.iterator(); // Ordinary Iterator
lit = a.listIterator(); // ListIterator
lit = a.listIterator(3); // Start at loc 3
i = a.lastIndexOf("1"); // Last match
i = a.lastIndexOf("1", 2); // ...after loc 2
a.remove(1); // Remove location 1
a.remove("3"); // Remove this object
a.set(1, "y"); // Set location 1 to "y"
// Keep everything that's in the argument
// (the intersection of the two sets):
a.retainAll(fill(new ArrayList()));
// Remove elements in this range:
a.removeRange(0, 2);
// Remove everything that's in the argument:
a.removeAll(fill(new ArrayList()));
i = a.size(); // How big is it?
a.clear(); // Remove all elements
}
public static void iterMotion(List a) {
ListIterator it = a.listIterator();
b = it.hasNext();
b = it.hasPrevious();
o = it.next();
i = it.nextIndex();
o = it.previous();
i = it.previousIndex();
}
public static void iterManipulation(List a) {
ListIterator it = a.listIterator();
it.add("47");
// Must move to an element after add():
it.next();
// Remove the element that was just produced:
it.remove();
// Must move to an element after remove():
it.next();
// Change the element that was just produced:
it.set("47");
}
public static void testVisual(List a) {
print(a);
List b = new ArrayList();
fill(b);
System.out.print("b = ");
print(b);
a.addAll(b);
a.addAll(fill(new ArrayList()));
print(a);
// Shrink the list by removing all the
// elements beyond the first 1/2 of the list
System.out.println(a.size());
System.out.println(a.size() / 2);
a.removeRange(a.size() / 2, a.size() / 2 + 2);
print(a);
// Insert, remove, and replace elements
// using a ListIterator:
ListIterator x = a.listIterator(a.size() / 2);
x.add("one");
print(a);
System.out.println(x.next());
x.remove();
System.out.println(x.next());
x.set("47");
print(a);
// Traverse the list backwards:
x = a.listIterator(a.size());
while (x.hasPrevious())
System.out.print(x.previous() + " ");
System.out.println();
System.out.println("testVisual finished");
}
// There are some things that only
// LinkedLists can do:
public static void testLinkedList() {
LinkedList ll = new LinkedList();
Collection1.fill(ll, 5);
print(ll);
// Treat it like a stack, pushing:
ll.addFirst("one");
ll.addFirst("two");
print(ll);
// Like "peeking" at the top of a stack:
System.out.println(ll.getFirst());
// Like popping a stack:
System.out.println(ll.removeFirst());
System.out.println(ll.removeFirst());
// Treat it like a queue, pulling elements
// off the tail end:
System.out.println(ll.removeLast());
// With the above operations, it's a dequeue!
print(ll);
}
public static void main(String args[]) {
// Make and fill a new list each time:
basicTest(fill(new LinkedList()));
basicTest(fill(new ArrayList()));
iterMotion(fill(new LinkedList()));
iterMotion(fill(new ArrayList()));
iterManipulation(fill(new LinkedList()));
iterManipulation(fill(new ArrayList()));
testVisual(fill(new LinkedList()));
testLinkedList();
}
} Copy code 

stay basicTest() and iterMotiion() in , Just simply make the call , In order to reveal the correct grammar . And despite the capture, the return value , But it's not used . In some cases , The reason why the return value is not captured , It's because they don't have any particular use . In official use Before them , You should study your online documents carefully , Master these methods completely 、 The right way to use .

ArrayList Using examples

import java.awt.List;
import java.util.ArrayList;
import java.util.Iterator;
/**
* @author sihai
* @time 2018/4/19
* ArrayList Examples of usage illustrate
*
*/
public class Main {
public static void main(String[] args) {
//ArrayList Usage examples
ArrayList<String> m_ArrayList=new ArrayList<String>();
m_ArrayList.add("Evankaka");
m_ArrayList.add("sihai");
m_ArrayList.add(" De, De ");
m_ArrayList.add("Evankaka");
m_ArrayList.add(" Xiaohong ");
m_ArrayList.set(2,"sihai2");// Place the index at 2 Object modification of
m_ArrayList.add(3," Study hard java");// Add the object to the index at 3 The location of
//ArrayList Traversal methods 1
Iterator<String> it_ArrayList = m_ArrayList.iterator();
System.out.println("ArrayList Traversal methods 1");
while (it_ArrayList.hasNext()) {
System.out.println(it_ArrayList.next());
}
//ArrayList Traversal methods 2
System.out.println("ArrayList Traversal methods 2");
for(Object o:m_ArrayList){
System.out.println(o);
}
//ArrayList Traversal methods 2
System.out.println("ArrayList Traversal methods 3");
for(int i = 0; i<m_ArrayList.size(); i++){
System.out.println(m_ArrayList.get(i));
}
// Remove elements
m_ArrayList.remove("Evankaka");
it_ArrayList = m_ArrayList.iterator();
System.out.println("ArrayList Traversal after deleting elements ");
while (it_ArrayList.hasNext()) {
String m_String=it_ArrayList.next();
if(m_String.equals(" Study hard java")){
it_ArrayList.remove();
}else{
System.out.println(m_String);
}
}
}
}
Copy code 

Output results :

ArrayList Traversal methods 1 Evankaka sihai sihai2 Study hard java Evankaka Xiaohong ArrayList Traversal methods 2 Evankaka sihai sihai2 Study hard java Evankaka Xiaohong ArrayList Traversal methods 3 Evankaka sihai sihai2 Study hard java Evankaka Xiaohong ArrayList Traversal after deleting elements sihai sihai2 Evankaka Xiaohong

ArrayList Be careful

(1) Use Iterator In the iterative set process , Set elements cannot be modified , Otherwise an exception will be thrown . also Iterator You can only iterate backwards (2) If you want to remove an element in the loop , Can only call it.remove Method , Out of commission list.remove Method , Otherwise, there must be a concurrent access error .

Use S e t s

Set It's just a Collection, It's just having different behaviors ( This is the ideal application of instance and polymorphism : Used to express different behaviors ). ad locum , One Set Only one instance per object is allowed ( As you'll see later , Of an object “ value ” The composition of is quite complicated ) Set( Interface ) Add to Set Each element of must be unique ; otherwise Set You don't add duplicate elements . Add to Set The object in must be defined equals(), To establish the uniqueness of the object . Set Have and Collection Exactly the same interface . One Set There is no guarantee that you can maintain your elements in any particular order HashSet For all but very small ones Set. Objects must also be defined hashCode() ArraySet Derived from an array Set. For very small Set Design , Especially those that need to be created and deleted frequently . For small Set, And HashSet comparison , ArraySet The cost of creation and repetition is much less . But as the Set The increase of , Its performance is also There will be a big discount . Unwanted HashCode() TreeSet By a “ Red and black trees ” The order that we get back Set( notes ⑦). thus , We can start with a Set There is a reference to Sequence set

public class Set1 {
public static void testVisual(Set a) {
Collection1.fill(a);
Collection1.fill(a);
Collection1.fill(a);
Collection1.print(a); // No duplicates!
// Add another set to this one:
a.addAll(a);
a.add("one");
a.add("one");
a.add("one");
Collection1.print(a);
// Look something up:
System.out.println("a.contains("one"): " + a.contains("one"));
}
public static void main(String[] args) {
testVisual(new HashSet());
testVisual(new TreeSet());
}
}
Copy code 

Duplicate values are added to Set, But when it comes to printing , We will find that Set Only one instance of each value is accepted . When you run this program , You'll notice by HashSet The order of maintenance and ArraySet Is different . This is because they use different methods to preserve elements , So that they can be positioned in the future . ArraySet Keep them in order , and HashSet Use a hash function , This is especially designed for fast retrieval ).

class MyType implements Comparable {
private int i;
public MyType(int n) {
i = n;
}
public boolean equals(Object o) {
return (o instanceof MyType) && (i == ((MyType) o).i);
}
public int hashCode() {
return i;
}
public String toString() {
return i + " ";
}
public int compareTo(Object o) {
int i2 = ((MyType) o).i;
return (i2 < i ? -1 : (i2 == i ? 0 : 1));
}
}
public class Set2 {
public static Set fill(Set a, int size) {
for (int i = 0; i < size; i++)
a.add(new MyType(i));
return a;
}
public static Set fill(Set a) {
return fill(a, 10);
}
public static void test(Set a) {
fill(a);
fill(a); // Try to add duplicates
fill(a);
a.addAll(fill(new TreeSet()));
System.out.println(a);
}
public static void main(String[] args) {
test(new HashSet());
test(new TreeSet());
}
}
Copy code 

But you have to put the class into a HashSet Under the premise of , It's necessary to use hashCode()—— It is entirely possible that , Because usually you should first choose as a Set Realization .

Use M a p s

Map( Interface ) maintain “ key - value ” Corresponding relation ( Yes ), In order to find the corresponding value through a key HashMap Based on a hash table ( Replace it with Hashtable). in the light of “ key - value ” Insertion and retrieval of , This form has the most stable performance . This performance can be tuned through the builder , In order to set the hash table “ Ability ” and “ Loading factor ” ArrayMap By a ArrayList It was pushed back Map. Provides precise control over the sequence of repetitions . For very small Map Design , Especially those that need to be created and deleted frequently . For very small Map, Creation and repetition cost more than HashMap Much lower . But in Map When you get bigger , The performance will be greatly reduced accordingly TreeMap In a “ red - black ” Tree based implementation . View key or “ key - value ” Right time , They will be arranged in a fixed order ( Depending on Comparable or Comparator, I'll talk about it later ). TreeMap The biggest advantage is that we get the results that have been ordered .TreeMap Contains subMap() The only way Map, You can use it to return a part of the tree

public class Map1 {
public final static String[][] testData1 = {
{ "Happy", "Cheerful disposition" },
{ "Sleepy", "Prefers dark, quiet places" },
{ "Grumpy", "Needs to work on attitude" },
{ "Doc", "Fantasizes about advanced degree" },
{ "Dopey", "'A' for effort" },
{ "Sneezy", "Struggles with allergies" },
{ "Bashful", "Needs self-esteem workshop" }, };
public final static String[][] testData2 = {
{ "Belligerent", "Disruptive influence" },
{ "Lazy", "Motivational problems" },
{ "Comatose", "Excellent behavior" } };
public static Map fill(Map m, Object[][] o) {
for (int i = 0; i < o.length; i++)
m.put(o[i][0], o[i][1]);
return m;
}
// Producing a Set of the keys:
public static void printKeys(Map m) {
System.out.print("Size = " + m.size() + ", ");
System.out.print("Keys: ");
Collection1.print(m.keySet());
}
// Producing a Collection of the values:
public static void printValues(Map m) {
System.out.print("Values: ");
Collection1.print(m.values());
}
// Iterating through Map.Entry objects (pairs):
public static void print(Map m) {
Collection entries = m.entries();
Iterator it = entries.iterator();
while (it.hasNext()) {
Map.Entry e = (Map.Entry) it.next();
System.out.println("Key = " + e.getKey() + ", Value = "
+ e.getValue());
}
}
public static void test(Map m) {
fill(m, testData1);
// Map has 'Set' behavior for keys:
fill(m, testData1);
printKeys(m);
printValues(m);
print(m);
String key = testData1[4][0];
String value = testData1[4][1];
System.out.println("m.containsKey("" + key + ""): "
+ m.containsKey(key));
System.out.println("m.get("" + key + ""): " + m.get(key));
System.out.println("m.containsValue("" + value + ""): "
+ m.containsValue(value));
Map m2 = fill(new TreeMap(), testData2);
m.putAll(m2);
printKeys(m);
m.remove(testData2[0][0]);
printKeys(m);
m.clear();
System.out.println("m.isEmpty(): " + m.isEmpty());
fill(m, testData1);
// Operations on the Set change the Map:
m.keySet().removeAll(m.keySet());
System.out.println("m.isEmpty(): " + m.isEmpty());
}
public static void main(String args[]) {
System.out.println("Testing HashMap");
test(new HashMap());
System.out.println("Testing TreeMap");
test(new TreeMap());
}
}
Copy code 

Traverse map example

package com.test;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Test {
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("first", "linlin");
map.put("second", " Study hard java");
map.put("third", "sihai");
map.put("first", "sihai2");
// The first one is : adopt Map.keySet Traverse key and value
System.out.println("=================== adopt Map.keySet Traverse key and value:===================");
for (String key : map.keySet()) {
System.out.println("key= " + key + " and value= " + map.get(key));
}
// The second kind : adopt Map.entrySet Use iterator Traverse key and value
System.out.println("=================== adopt Map.entrySet Use iterator Traverse key and value:===================");
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= "
+ entry.getValue());
}
// The third kind of : adopt Map.entrySet Traverse key and value
System.out.println("=================== adopt Map.entrySet Traverse key and value:===================");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= "
+ entry.getValue());
}
// A fourth : adopt Map.values() Traverse all value, But you can't traverse the key key
System.out.println("=================== adopt Map.values() Traverse all value:===================");
for (String v : map.values()) {
System.out.println("value= " + v);
}
}
}
Copy code 

The output is as follows :

=================== adopt Map.keySet Traverse key and value:=================== key= third and value= sihai key= first and value= sihai2 key= second and value= Study hard java =================== adopt Map.entrySet Use iterator Traverse key and value:=================== key= third and value= sihai key= first and value= sihai2 key= second and value= Study hard java =================== adopt Map.entrySet Traverse key and value:=================== key= third and value= sihai key= first and value= sihai2 key= second and value= Study hard java =================== adopt Map.values() Traverse all value:=================== value= sihai value= sihai2 value= Study hard java

Decide which set to use

ArrayList, LinkedList as well as Vector( Roughly equivalent to ArrayList) It's all done List Interface , So whatever you choose , Our programs all get similar results . However , ArrayList( as well as Vector) It's derived from an array ; and LinkedList It is based on the conventional double link list , Because each individual object contains data and handles to the front and back elements of the list . That's why , If you want to do a lot of insert and delete operations in the middle of a list , that LinkedList No doubt the most appropriate choice ( LinkedList There are some extra features , Built on AbstractSequentialList in ). If it is not so , I'd rather choose ArrayList, It may be faster . As another example , Set It can be used as a ArraySet Realization , It can also be used as HashSet Realization . ArraySet Is written by a ArrayList It was pushed back , Designed to support only a few elements , It is especially suitable for the requirement of creating and deleting a large number of Set The object of the occasion to use . However , Once needed in their own Set Contains a lot of elements , ArraySet The performance will be greatly reduced . Write a need for Set When , You should choose by default HashSet. And only in some special cases ( There is an urgent need for performance improvement ), You should switch to ArraySet.

  1. Decide what to use List

To experience all kinds of List The differences between the implementation schemes , The easiest way to do it is to take a one-time aptitude test .

public class ListPerformance {
private static final int REPS = 100;
private abstract static class Tester {
String name;
int size; // Test quantity
Tester(String name, int size) {
this.name = name;
this.size = size;
}
abstract void test(List a);
}
private static Tester[] tests = { new Tester("get", 300) {
void test(List a) {
for (int i = 0; i < REPS; i++) {
for (int j = 0; j < a.size(); j++)
a.get(j);
}
}
}, new Tester("iteration", 300) {
void test(List a) {
for (int i = 0; i < REPS; i++) {
Iterator it = a.iterator();
while (it.hasNext())
it.next();
}
}
}, new Tester("insert", 1000) {
void test(List a) {
int half = a.size() / 2;
String s = "test";
ListIterator it = a.listIterator(half);
for (int i = 0; i < size * 10; i++)
it.add(s);
}
}, new Tester("remove", 5000) {
void test(List a) {
ListIterator it = a.listIterator(3);
while (it.hasNext()) {
it.next();
it.remove();
}
}
}, };
public static void test(List a) {
// A trick to print out the class name:
System.out.println("Testing " + a.getClass().getName());
for (int i = 0; i < tests.length; i++) {
Collection1.fill(a, tests[i].size);
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(a);
long t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
}
}
public static void main(String[] args) {
test(new ArrayList());
test(new LinkedList());
}
}
Copy code 

Inner class Tester Is an abstract class , Used to provide a base class for specific tests . It contains a string to be printed at the beginning of the test 、 One used to calculate the number of tests or the number of elements size Parameters 、 A constructor for initializing fields and an abstract method test(). test() It's the most practical testing work . All kinds of tests are concentrated in one place : tests Array . We inherit from Tester To initialize the array with different anonymous inner classes . Add or remove a test project for , Simply add or remove an inner class definition in the array , All the other work is done automatically .

Type Get Iteration Insert Remove
A r r a y L i s t 110 490 3790 8730
LinkedList 1980 220 110 110
Copy code 

stay ArrayList Random access to ( namely get()) And cycling is the best way to do it ; But for the LinkedList It's a big expense . But on the other hand , Insert and delete in the middle of the list for LinkedList But it is better than ArrayList It's much more cost-effective . The best thing we can do is to choose one first ArrayList As your default starting point . In the future, if it is found that the performance is reduced due to a large number of inserts and deletions , Think about changing it to LinkedList Not later .

  1. Decide what to use Set

Can be found in ArraySet as well as HashSet Make a choice between , Depending on Set Size ( If you need to get from a Set To get an ordered list of , Please use TreeSet;)

public class SetPerformance {
private static final int REPS = 200;
private abstract static class Tester {
String name;
Tester(String name) {
this.name = name;
}
abstract void test(Set s, int size);
}
private static Tester[] tests = { new Tester("add") {
void test(Set s, int size) {
for (int i = 0; i < REPS; i++) {
s.clear();
Collection1.fill(s, size);
}
}
}, new Tester("contains") {
void test(Set s, int size) {
for (int i = 0; i < REPS; i++)
for (int j = 0; j < size; j++)
s.contains(Integer.toString(j));
}
}, new Tester("iteration") {
void test(Set s, int size) {
for (int i = 0; i < REPS * 10; i++) {
Iterator it = s.iterator();
while (it.hasNext())
it.next();
}
}
}, };
public static void test(Set s, int size) {
// A trick to print out the class name:
System.out.println("Testing " + s.getClass().getName() + " size "
+ size);
Collection1.fill(s, size);
for (int i = 0; i < tests.length; i++) {
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(s, size);
long t2 = System.currentTimeMillis();
System.out.println(": " + ((double) (t2 - t1) / (double) size));
}
}
public static void main(String[] args) {
// Small:
test(new TreeSet(), 10);
test(new HashSet(), 10);
// Medium:
test(new TreeSet(), 100);
test(new HashSet(), 100);
// Large:
test(new HashSet(), 1000);
test(new TreeSet(), 1000);
}
}
Copy code 

Conduct add() as well as contains() In operation , HashSet Obviously more than ArraySet Much better , And the properties obviously have little to do with the amount of elements . When you write a program , Almost never use ArraySet

3. Decide what to use Map

Choose different Map When implementing the plan , Be careful Map The size of has the biggest impact on performance , This is clearly illustrated in the following test procedure One o'clock :

public class MapPerformance {
private static final int REPS = 200;
public static Map fill(Map m, int size) {
for (int i = 0; i < size; i++) {
String x = Integer.toString(i);
m.put(x, x);
}
return m;
}
private abstract static class Tester {
String name;
Tester(String name) {
this.name = name;
}
abstract void test(Map m, int size);
}
private static Tester[] tests = { new Tester("put") {
void test(Map m, int size) {
for (int i = 0; i < REPS; i++) {
m.clear();
fill(m, size);
}
}
}, new Tester("get") {
void test(Map m, int size) {
for (int i = 0; i < REPS; i++)
for (int j = 0; j < size; j++)
m.get(Integer.toString(j));
}
}, new Tester("iteration") {
void test(Map m, int size) {
for (int i = 0; i < REPS * 10; i++) {
Iterator it = m.entries().iterator();
while (it.hasNext())
it.next();
}
}
}, };
public static void test(Map m, int size) {
// A trick to print out the class name:
System.out.println("Testing " + m.getClass().getName() + " size "
+ size);
fill(m, size);
for (int i = 0; i < tests.length; i++) {
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(m, size);
long t2 = System.currentTimeMillis();
System.out.println(": " + ((double) (t2 - t1) / (double) size));
}
}
public static void main(String[] args) {
// Small:
test(new Hashtable(), 10);
test(new HashMap(), 10);
test(new TreeMap(), 10);
// Medium:
test(new Hashtable(), 100);
test(new HashMap(), 100);
test(new TreeMap(), 100);
// Large:
test(new HashMap(), 1000);
test(new Hashtable(), 1000);
test(new TreeMap(), 1000);
}
}
Copy code 

because Map The size of is the most serious problem , So the timing test of the program is Map Size ( Or capacity ) To divide the time , In order to get people Convincing test results . Here's a list of results ( It may be different on your machine ): Even if the size is 10, ArrayMap The performance of HashMap Bad —— Except for repeated cycles . But in the use of Map when , The effect of repetition is usually not important ( get() It's usually where we spend the most time ). TreeMap Provides excellent put() And the repetition time , but get() The performance is not good . however , Why do we still need to use TreeMap Well ? thus , We can not treat it as Map Use , And as a way to create a sequential list . Once filled with a TreeMap, You can call keySet() To get one of the keys Set“ scene ”. And then use toArray() Generate an array containing those keys . And then , You can use static Method Array.binarySearch() Quickly find the contents of an ordered array . Of course , Maybe only in HashMap When your behavior is unacceptable , That's what you need to do . because HashMap The purpose of the design is to carry out fast retrieval operation . Last , When we use Map when , The first choice should be HashMap. Only in very few cases do you need to consider other methods

public class MapCreation {
public static void main(String[] args) {
final long REPS = 100000;
long t1 = System.currentTimeMillis();
System.out.print("Hashtable");
for (long i = 0; i < REPS; i++)
new Hashtable();
long t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
t1 = System.currentTimeMillis();
System.out.print("TreeMap");
for (long i = 0; i < REPS; i++)
new TreeMap();
t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
t1 = System.currentTimeMillis();
System.out.print("HashMap");
for (long i = 0; i < REPS; i++)
new HashMap();
t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
}
}
Copy code 

TreeMap Is significantly faster than the other two types ( But you should try it yourself , Because it is said that the new version may improve ArrayMap Performance of ). For this reason , At the same time, because of the foregoing TreeMap Outstanding put() performance , So like If you need to create a lot of Map, And it's only in the future that a lot of retrieval operations need to be involved , So the best strategy is : Create and fill in TreeMap; When the search volume increases in the future , And then the important TreeMap convert to HashMap—— Use HashMap(Map) Builder .

Unsupported operation

utilize static( static state ) Array Arrays.toList(), Maybe you can convert an array to List

public class Unsupported {
private static String[] s = { "one", "two", "three", "four", "five", "six",
"seven", "eight", "nine", "ten", };
static List a = Arrays.toList(s);
static List a2 = Arrays.toList(new String[] { s[3], s[4], s[5] });
public static void main(String[] args) {
Collection1.print(a); // Iteration
System.out.println("a.contains(" + s[0] + ") = " + a.contains(s[0]));
System.out.println("a.containsAll(a2) = " + a.containsAll(a2));
System.out.println("a.isEmpty() = " + a.isEmpty());
System.out.println("a.indexOf(" + s[5] + ") = " + a.indexOf(s[5]));
// Traverse backwards:
ListIterator lit = a.listIterator(a.size());
while (lit.hasPrevious())
System.out.print(lit.previous());
System.out.println();
// Set the elements to different values:
for (int i = 0; i < a.size(); i++)
a.set(i, "47");
Collection1.print(a);
// Compiles, but won't run:
lit.add("X"); // Unsupported operation
a.clear(); // Unsupported
a.add("eleven"); // Unsupported
a.addAll(a2); // Unsupported
a.retainAll(a2); // Unsupported
a.remove(s[0]); // Unsupported
a.removeAll(a2); // Unsupported
}
} Copy code 

It can be seen from it that , In fact, only Collection and List Part of the interface . The rest of the method leads to an unpopular situation , be known as UnsupportedOperationException. In the collection class that implements those interfaces , Or offer 、 Or there is no support for those methods . If you call an unsupported method , It will lead to a UnsupportedOperationException( Operation does not support violation ), This indicates a programming error . Arrays.toList() There is a List( list ), The list is derived from an array of fixed lengths . So the only thing that can be supported is those operations that don't change the length of the array . per contra , If you request a new interface to express different kinds of behavior ( It may be called “ FixedSizeList” —— Fixed length list ), There's a risk of greater complexity . thus , When you try to use the library later , Soon you will find that you don't know where to start . For those who use Collection, List, Set perhaps Map Methods as parameters , Their documentation should indicate which alternative methods must be implemented . For example , Sorting requires the implementation of set() and Iterator.set() Method , But does not include add() and remove().

Sort and search

Array

Arrays Class provides an overloaded sort() and binarySearch(), They can also be used for String and Object.

public class Array1 {
static Random r = new Random();
static String ssource = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+ "abcdefghijklmnopqrstuvwxyz";
static char[] src = ssource.toCharArray();
// Create a random String
public static String randString(int length) {
char[] buf = new char[length];
int rnd;
for (int i = 0; i < length; i++) {
rnd = Math.abs(r.nextInt()) % src.length;
buf[i] = src[rnd];
}
return new String(buf);
}
// Create a random array of Strings:
public static String[] randStrings(int length, int size) {
String[] s = new String[size];
for (int i = 0; i < size; i++)
s[i] = randString(length);
return s;
}
public static void print(byte[] b) {
for (int i = 0; i < b.length; i++)
System.out.print(b[i] + " ");
System.out.println();
}
public static void print(String[] s) {
for (int i = 0; i < s.length; i++)
System.out.print(s[i] + " ");
System.out.println();
}
public static void main(String[] args) {
byte[] b = new byte[15];
r.nextBytes(b); // Fill with random bytes
print(b);
Arrays.sort(b);
print(b);
int loc = Arrays.binarySearch(b, b[10]);
System.out.println("Location of " + b[10] + " = " + loc);
// Test String sort & search:
String[] s = randStrings(4, 10);
print(s);
Arrays.sort(s);
print(s);
loc = Arrays.binarySearch(s, s[4]);
System.out.println("Location of " + s[4] + " = " + loc);
}
}
Copy code 

stay main() in , Random.nextBytes() Fill array arguments with randomly selected bytes ( There is no counterpart Random Method is used to create arrays of other basic data types ). After getting an array , You can see that in order to execute sort() perhaps binarySearch(), Just make a method call once . And binarySearch() There is also an important warning about it : If you're doing it once binarySearch() We didn't call sort(), Unpredictable behavior will occur , It even includes infinite loops . Yes String The sort and search of are similar , But when you run the program , We'll notice an interesting phenomenon : Sorting follows the dictionary order , In other words, the uppercase letter precedes the lowercase letter in the character set . therefore , All uppercase letters are at the top of the list , Followed by lowercase letters —— Z It was actually in a In front of . It seems that even phonebooks are sorted in this way .

  • Can be compared with a comparator If you want to talk to a Object Array to sort , So there's a problem that has to be solved . According to what to judge two Object The order of ? Unfortunately , The original Java Designers don't think this is an important issue , Otherwise, it's already in the root class Object It's defined in . One consequence of this is : It has to be done from the outside Object Sort , And the new collection library provides a standard way to do this ( The ideal is in Object It is defined in ). in the light of Object Array ( as well as String, Of course it belongs to Object A kind of ), One can be used sort(), And make it accept another parameter : Realized Comparator Interface ( namely “ The comparator ” Interface , Part of the new collection library ) An object of , And use its single compare() Methods for comparison . This method takes two objects to be compared as its own parameters —— If the first parameter is less than the second , Returns a negative integer ; If equal , Return to zero ; If the first parameter is greater than the second , Then return a positive integer . Based on this rule , In the example above String The part can be rewritten , Put it in a really alphabetical order : By modeling it as String, compare() The method will carry out “ Hint ” Sex testing , The only thing you can guarantee is String object —— The shipping system will catch any errors . After forcing both strings to lowercase , String.compareTo() Methods will produce the desired results if you use your own Comparator Let's do it once sort(), So in use binarySearch() You have to use the same Comparator. Arrays Class provides another sort() Method , It takes a single argument : One Object Array , But there is no Comparator. This sort() The method has to compare two in the same way Object. By implementing Comparable Interface , It takes the “ Natural comparison method ”. This interface contains a single method —— compareTo(), According to the fact that it is less than 、 Returns a negative number equal to or greater than an argument 、 Zero or positive , So as to realize the comparison of objects .
public class CompClass implements Comparable {
private int i;
public CompClass(int ii) {
i = ii;
}
public int compareTo(Object o) {
// Implicitly tests for correct type:258
int argi = ((CompClass) o).i;
if (i == argi)
return 0;
if (i < argi)
return -1;
return 1;
}
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
public String toString() {
return i + "";
}
public static void main(String[] args) {
CompClass[] a = new CompClass[20];
for (int i = 0; i < a.length; i++)
a[i] = new CompClass((int) (Math.random() * 100));
print(a);
Arrays.sort(a);
print(a);
int loc = Arrays.binarySearch(a, a[3]);
System.out.println("Location of " + a[3] + " = " + loc);
}
}
Copy code 
  • list You can sort and search a list in the same way as an array ( List). Static methods for sorting and searching lists are contained in the class Collections in , But they have something to do with Arrays A similar signature in : sort(List) Used to implement Comparable The list of objects to sort ; binarySearch(List,Object) Used to find an object in a list ; sort(List,Comparator) Using a “ The comparator ” Sort a list ; and binarySearch(List,Object,Comparator) Is used to find an object in that list
public class ListSort {
public static void main(String[] args) {
final int SZ = 20;
// Using "natural comparison method":
List a = new ArrayList();
for(int i = 0; i < SZ; i++)
a.add(new CompClass(
(int)(Math.random() *100)));
Collection1.print(a);
Collections.sort(a);
Collection1.print(a);
Object find = a.get(SZ/2);259
int loc = Collections.binarySearch(a, find);
System.out.println("Location of " + find +
" = " + loc);
// Using a Comparator:
List b = new ArrayList();
for(int i = 0; i < SZ; i++)
b.add(Array1.randString(4));
Collection1.print(b);
AlphaComp ac = new AlphaComp();
Collections.sort(b, ac);
Collection1.print(b);
find = b.get(SZ/2);
// Must use the Comparator to search, also:
loc = Collections.binarySearch(b, find, ac);
System.out.println("Location of " + find +
" = " + loc);
}
}
Copy code 

The usage of these methods is similar to that in Arrays The usage of in is exactly the same , It's just a list instead of an array . TreeMap It must also be based on Comparable perhaps Comparator Sort your own objects Collections Class : enumeration(Collection) Producing primitive style for independent variables Enumeration( enumeration ) max(Collection), min(Collection) In the independent variable, the maximum or minimum element is generated by the natural comparison of objects in the set max(Collection,Comparator), min(Collection,Comparator) Use a comparator to produce the largest or smallest element in a set nCopies(int n, Object o) Return length is n An immutable list of , All its handles point to o subList(List,int min,int max) Returns a new list derived from the specified parameter list . Think of this list as a “ window ”, It's self indexed to min The place to start , Just ended at max In front of Be careful min() and max() All with you Collection The object works , Not with List, So don't worry about Collection Do you need to sort ( As pointed out earlier , In the execution of a binarySearch()—— Binary search —— Before , You have to deal with a List Or an array to execute sort())

  1. send Collection or Map Do not modify the

Usually , establish Collection or Map One of the “ read-only ” The version seems more advantageous . Collections Class allows us to achieve this goal , The method is to pass the original container into a method , And have it return a read-only version . There are four variations of this method , for Collection( If you don't want to treat the set as a more special type )、 List、 Set as well as Map.

public class ReadOnly {
public static void main(String[] args) {
Collection c = new ArrayList();
Collection1.fill(c); // Insert useful data
c = Collections.unmodifiableCollection(c);
Collection1.print(c); // Reading is OK
// ! c.add("one"); // Can't change it
List a = new ArrayList();
Collection1.fill(a);
a = Collections.unmodifiableList(a);
ListIterator lit = a.listIterator();
System.out.println(lit.next()); // Reading OK
// ! lit.add("one"); // Can't change it
Set s = new HashSet();
Collection1.fill(s);
s = Collections.unmodifiableSet(s);
Collection1.print(s); // Reading OK
// ! s.add("one"); // Can't change it
Map m = new HashMap();
Map1.fill(m, Map1.testData1);
m = Collections.unmodifiableMap(m);
Map1.print(m); // Reading OK
// ! m.put("Ralph", "Howdy!");
}
} Copy code 

For each case , Before officially making it read-only , Must be filled with valid data . Once the load is successful , The best way is to use “ Do not modify the ” Call the generated handle to replace the existing handle . By doing so, it can effectively avoid changing the contents of it after making it unmodifiable . per contra , The tool also allows us to keep the container that can be modified as private state , It can return a read-only handle to that container from a method call . thus , Although we can modify it in the class , But anyone else can only read . Call... For a specific type “ Do not modify the ” Does not cause checks during compilation , But once anything changes , A call to a method that modifies a particular container produces a UnsupportedOperationException Violation .

2.Collection or Map Synchronization of

Here it is , You just need to notice Collections Class provides a way to automatically synchronize the entire container . Its grammar and “ Do not modify the ” The method is similar :

public class Synchronization {
public static void main(String[] args) {
Collection c = Collections.synchronizedCollection(new ArrayList());
List list = Collections.synchronizedList(new ArrayList());
Set s = Collections.synchronizedSet(new HashSet());
Map m = Collections.synchronizedMap(new HashMap());
}
}
Copy code 

summary

(1) The array contains the digital index of the object . It holds an object of known type , So when looking for an object , There is no need to shape the results . Arrays can be multidimensional , And it can accommodate basic data types . however , Once you've created it , Urine and urine can't change . (2) Vector( vector ) It also contains a numeric index of the object —— You can combine arrays with Vector Think of it as a random access collection . When we add more elements , Vector Can automatically change their own size . but Vector Can only hold handles to objects , So it can't contain basic data types ; And when you take an object handle out of a collection , The results have to be shaped . (3) Hashtable( Hash table ) Belong to Dictionary( Dictionaries ) A type of , It's a way of putting objects ( Not Numbers ) How to associate with other objects . Hash tables also support random access to objects , in fact , Its entire design highlights the access to “ high velocity ”. (4) Stack( Stack ) It's a kind of “ After the first out ”( LIFO) Queues about Hashtable, You can put anything in it , And retrieve it very quickly ; about Enumeration( enumeration ), Can traverse a sequence , And take a specific action on each of these elements . It's a tool that's powerful enough . but Hashtable No, “ The order ” The concept of . Vector And arrays give us a linear order , But to insert an element in the middle of any of them , Generally, you have to pay “ It's a terrible thing ” The price of . in addition to , queue 、 Break up the queue 、 Both the priority queue and the tree are related to the element “ Sort ” —— It's not just putting them in , So that you can find or move them in linear order later .

3、 ... and 、 Comparison and summary of each set class

Set (Set): The objects in the set are not arranged in any particular way , Manipulate data by index values , There can be no repeating elements list (List): Objects in a sequence are stored linearly , Manipulate data by index values , There can be repeating elements mapping (Map): Each term of the mapping is “ name — The number ” Yes , The name cannot be repeated , Values can be repeated , A name corresponds to a unique value

iterator Iterator

An iterator is to get all the objects in a collection one by one in order , Is the standard mechanism for accessing each element in the collection . Creation of iterators :Collection Interface iterator() Method returns a Iterator Iterator it=test.iterator(); // take test Collection objects become iterators Common methods of iterators :

hasNext() // Determine if there is the next element in the iterator next() // Returns the next element of the iteration Remove() // Remove the new returned element from the iterator
public interface Iterator {
boolean hasNext();
Object next();
void remove(); // Optional
}
Copy code 

Calling remove() Method time , Must call once next() Method . remove() Method is actually to delete the last returned element .

List Common methods

void add(int index, Object element) : Add object element To the position index On boolean addAll(int index, Collection collection) : stay index Add container after position collection All the elements in Object get(int index) : Take out the subscript index The elements of location int indexOf(Object element) : Look for objects element stay List The first place in int lastIndexOf(Object element) : Look for objects element stay List The last position in Object remove(int index) : Delete index Elements in position ListIterator listIterator(int startIndex) : Return to one ListIterator Down the machine , The starting position is startIndex List subList(int fromIndex, int toIndex) : Return a sublist List , Elements are stored as from fromIndex To toIndex The previous element

ArrayList

Think of it as an array that can grow capacity automatically . utilize ArrayList Of toArray() Returns an array . Arrays.asList() Return a list . iterator (Iterator) It gives us a general way to access the elements in the collection . ArrayList Can automatically expand capacity ArrayList.ensureCapacity(int minCapacity) First get the current elementData The length of the property oldCapacity. And then by judgment oldCapacity and minCapacity Which parameter is larger to decide whether expansion is needed , If minCapacity Greater than oldCapacity, So let's talk about the current List Object to expand . The strategy of expansion is : take (oldCapacity * 3)/2 + 1 and minCapacity The bigger one between . And then use arrays to copy The way of shellfish , Transfer the previously stored data to a new array object if minCapacity No more than oldCapacity So we don't have to expand .

LinkedList

LinkedList It is realized by two-way circular list . utilize LinkedList Stack can be implemented (stack)、 queue (queue)、 The bidirectional queue (double-ended queue ). It has a way addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast() etc. .

ArrayList and LinkedList Comparison

1.ArrayList Is the implementation of a dynamic array based data structure ,LinkedList Data structures based on linked lists . 2. For random access get and set,ArrayList Feel superior to LinkedList, because LinkedList To move the pointer . 3. For new and delete operations add and remove,LinedList predominance , because ArrayList To move data . Try to avoid traversing and deleting collections at the same time . Because it changes the size of the set ;

for( Iterator<ComType> iter = ComList.iterator(); iter.hasNext();){
ComType com = iter.next();
if ( !com.getName().contains("abc")){
ComList.remove(com);}
}
Copy code 

recommend :

for( Iterator<ComType> iter = ComList.iterator(); iter.hasNext();){
ComType com = iter.next();
if ( !com.getName().contains("abc")){
iter.remove(com); }
Copy code 

Unlimited in lst in add element, Is bound to cause lst Too much memory

Map Common methods

Common methods :

Object put(Object key,Object value): Used to store a key - It's worth it Map in Object remove(Object key): according to key( key ), Remove key - It's worth it , And return the value to void putAll(Map mapping) : Will another one Map The elements in are stored in the current Map in void clear() : To empty the current Map The elements in Object get(Object key) : according to key( key ) Get the corresponding value boolean containsKey(Object key) : Judge Map Whether there is a key in (key) boolean containsValue(Object value): Judge Map Whether there is a value in (value) public Set keySet() : Back to all the keys (key), And use Set Container storage public Collection values() : Return all values (Value), And use Collection Deposit public Set entrySet() : Return an implementation Map.Entry The elements of the interface Set

HashMap

Map It is mainly used to store keys (key) value (value) Yes , Get the value from the key , So the key is not allowed to repeat , But the values are allowed to repeat . HashMap Is one of the most commonly used Map, It depends on the HashCode Value store data , According to the key, you can get its value directly , Fast access speed . HashMap Only one record can have a key of Null; Multiple records are allowed to have a value of Null; HashMap Synchronization of threads is not supported , That is, multiple threads can write at any time HashMap; May cause data inconsistency . If synchronization is needed , It can be used Collections Of synchronizedMap Method makes HashMap Ability to synchronize , Or use ConcurrentHashMap Use HashMap , When an object is treated as a key value, it is necessary to equals() and hashCode() At the same time, rewrite

LinkedHashMap and HashMap,TreeMap contrast

Hashtable And HashMap similar , It is inherited from Dictionary class , The difference is : It does not allow the recorded key or value to be empty ; It supports thread synchronization , That is, only one thread can write at any time Hashtable, So it also led to Hashtable It's slower to write . Hashmap Is one of the most commonly used Map, It depends on the HashCode Value store data , According to the key, you can get its value directly , Fast access speed , Ergodic time , The order of data acquisition is completely random . LinkedHashMap Saved the insertion order of records , In use Iterator Traverse LinkedHashMap when , The first records must have been inserted first . We can also use the belt parameter in the construction , Sort by number of applications . When traversing, it will be better than HashMap slow , But there is an exception , When HashMap A lot of capacity , When the actual data is small , Ergodically, it might be LinkedHashMap slow , because LinkedHashMap The traversal speed of is only related to the actual data , Independent of capacity , and HashMap The ergodic speed of is related to its capacity . TreeMap Realization SortMap Interface , It can sort its saved records by key , The default is to sort keys in ascending order , You can also specify a comparator for sorting , When used Iterator Traverse TreeMap when , The records are sorted . What we use most is HashMap,HashMap The key value pairs stored in it are random when they are taken out , stay Map Insert 、 Delete and locate elements ,HashMap Is the best choice . TreeMap The sorted key value pairs are retrieved . But if you want to press Natural order or custom order traversal key , that TreeMap Will be better . LinkedHashMap yes HashMap A subclass of , If you need the output in the same order as the input , Then use LinkedHashMap Can achieve , It can also be arranged in read order , Like connection pool can be applied .

Set Use

Duplicate elements are not allowed Yes add()、equals() and hashCode() Method added restrictions HashSet and TreeSet yes Set The implementation of the Set—》HashSet LinkedHashSet SortedSet —》 TreeSet

HashSet

public boolean contains(Object o) : If set Contains the specified elements , return true public Iterator iterator() return set Iterators of elements in public Object[] toArray() : Return contains set Array of all elements in public Object[] toArray(Object[] a) : Return contains set Array of all elements in , The runtime type of the returned array is the runtime type of the specified array public boolean add(Object o) : If set The specified element does not exist in , to set Join in public boolean remove(Object o) : If set There is a specified element in , From set Delete in public boolean removeAll(Collection c) : If set Contains the specified set , From set Delete all the elements of the specified collection public boolean containsAll(Collection c) : If set Contains all elements of the specified collection , return true. If the specified set is also a set, Only now set A subset of , Method returns true

Realization Set Interface HashSet, rely on HashMap To achieve . We should define hashCode() and equals(). HashSet How to filter repeating elements Call element HashCode Get hash code –》 Determine whether hash codes are equal , If not, enter —》 Equality is the judgment equals() Whether the latter is equal or not , There is no equality in progress hashcode entry , Equality is not entered

TreeSet

TreeSet Depend on TreeMap To achieve . TreeSet Is an ordered set ,TreeSet The elements in the list will be in ascending order , The default is to arrange in natural order , signify TreeSet In order to realize Comparable Interface , We can construct TreeSet Object time , The transmission realizes Comparator The comparator object of the interface .

HashSet And TreeSet And LinkedHashSet contrast

HashSet There is no guarantee of the order of elements , The order is likely to change , It's not synchronous , The set element can be null, But only one null TreeSet yes SortedSet The unique implementation class of the interface ,TreeSet You can ensure that the collection elements are in a sorted state .TreeSet Two sorts are supported , Natural ordering And custom sort , The natural sort is the default sort . towards TreeSet Should be the object of the same class . TreeSet The way to judge that two objects are not equal is that two objects pass through equals Method returns false, Or by CompareTo Method comparison did not return 0 Natural ordering Natural sorting uses the CompareTo(Object obj) Method to compare the size relationships between elements , Then arrange the elements in ascending order . Custom sort Natural ordering is based on the size of the set elements , Arrange in ascending order , If you want to customize the sorting , You should use Comparator Interface , Realization int compare(To1,To2) Method LinkedHashSet Sets are also based on elements hashCode Value to determine where the element is stored , But it also uses linked lists to maintain the order of elements . This makes the elements look like It's like inserting in order Ordered , in other words , When traversing the collection ,LinkedHashSet The elements of the collection will be accessed in the order in which they are added . LinkedHashSet In the iteration visit Set When all the elements in , Performance ratio HashSet good , But the insertion performance is slightly worse than HashSet.

版权声明
本文为[Java City Conqueror]所创,转载请带上原文链接,感谢

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云