A summary of collection introduction
Collection framework:
The Collection framework classes in Java can be divided into Collection and Map. The difference between the two:
1. A Collection is a single column. A Map is a collection of bicolumns
2. Only Set elements are required in Collection; The Map must have unique keys and duplicate values
3. The data structure of Collection is for elements; The Map data structure is key-specific.
Generics:
I’m going to talk about generics before I talk about the two sets, because we’re going to use them all in the next set; That’s what generics are: parameterization of types
A generic is part of a type, and the class name + generic is the whole thing
If there is a generic type, the type of the parameter is automatically promoted to Object when it is not used. If it is retrieved, it needs to be forcefully cast down, resulting in a ClassCaseException. Without generics, you can’t add the type of an element to a compile-time directed collection, resulting in late processing trouble.
Here’s how generics are different with and without generics:
Package learn Java well; import java.util.ArrayList; import java.util.Iterator; import java.util.List; Public class Test {public static void main(String[] args) {List List = new ArrayList<>(); list.add(1); list.add("123");
list.add("hello");
Iterator it = list.iterator();
while(it.hasNext()){// Without adding generics, we can only accept Object obj = it.next(); System.out.println(obj); }}} package import java.util.ArrayList; import java.util.Iterator; import java.util.List; Public class Test {public static void main(String[] args) {public static void main(String[] args) {List<String> List = new ArrayList<String>(); list.add("123");
list.add("hello");
Iterator<String> it = list.iterator();
while(it.hasNext()){// We can use String STR = it.next(); // We can use String STR = it. System.out.println(str.length()); }}}Copy the codeCustom generic class:
Package learn Java well; Public static void main(String[] args) {public static void main(String[] args) {public static void main(String[] args) { Person<String> perStr = new Person<String>(); perStr.setT("I'm a string"); String str = perStr.getT(); System.out.println(str); Person<Integer> perInt = new Person<Integer>(); perInt.setT(100); Integer intVal = perInt.getT(); System.out.println(intVal); Class Person<T>{private T T; voidsetT(T t){
this.t = t;
}
T getT() {returnt; }}Copy the codeImplement interface types with generics:
When you implement the interface, you specify the generic type in the interface (defined when defining the class).
public class GenericImpl1 implements GenericInter<String> {}
Copy the codeWhen you implement an interface, you do not specify a generic type in the interface. In this case, the implementation class of the interface needs to be defined as a generic class. The type of an interface needs to be truly determined when the implementation-class object is created (the type is never determined until the object is created).
public class GenericImpl2<T> implements GenericInter<T> {}
Copy the codeWildcards for generics (?) :
Public void getFunc(List
an),
So this argument here can be passed to Animal, or a subclass of Animal
Public void getFunc(Set
an ),
So this argument here can be passed to Animal, or Animal’s parent
Notes for using generics:
1. Generics do not support primitive data types
List
The Collection system:
Ollection includes two systems, a List and a Set
List features:
Access is ordered, indexed, can be evaluated by index, elements can be repeated
Set features:
Access is unordered and elements cannot be repeated
List:
ArrayList, LinkedList, Vector(obsolete)
The greatest purpose of collections is access; The List collection is characterized by orderly access. It can store repeated elements and operate elements with subscripts
ArrayList: The underlying implementation uses arrays, so the query speed is fast, add and delete speed is slow
Package learn Java well; import java.util.ArrayList; import java.util.Iterator; import java.util.List; Public class Test {// Use ArrayList to add and iterate public static void main(String[] args) {List<String> List = new ArrayList<String>(); list.add("Interface 1");
list.add("Interface 2");
list.add("Interface 3"); Iterator<String> it = list.iterator(); Iterator<String> it = list.iterator();while(it.hasNext()){
String next = it.next();
System.out.println(next);
}
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -"); // The second traversal method, foreachfor(String str : list){ System.err.println(str); }}}Copy the codeLinkedList: is implemented based on a LinkedList structure, so it is slow to query, fast to add and delete, and provides special methods to operate on elements from top to bottom.
Use LinkedList to implement stacks and queues; Stacks are fifo and queues are fifO
package com.xiaoshitou.classtest; import java.util.LinkedList; /** * use LinkedList to simulate the characteristics of stack * : @author Beck * */ public class MyStack {private LinkedList<String> linkList = new LinkedList<String>(); Public void push(String STR){linklist.addFirst (STR); } // unstack public Stringpop() {returnlinkList.removeFirst(); } // View public Stringpeek() {returnlinkList.peek(); } // Check whether it is empty public BooleanisEmpty() {returnlinkList.isEmpty(); }} package learn Java; Public class Test {public static void main(String[] args) {stack = new stack Test(); stack.push("I was the first one in.");
stack.push("I was the second one to go in.");
stack.push("I was the third one to go in.");
stack.push("I was the fourth to go in.");
stack.push("I was the fifth to go in."); / / removewhile(! stack.isEmpty()){ String pop = stack.pop(); System.out.println(pop); } // Print the result /* I'm the fifth to go in, I'm the fourth to go in, I'm the third to go in, I'm the second to go in, I'm the first to go in */Copy the codeLinkedList implementation Queue:
Package learn Java well; import java.util.LinkedList; /** * queue with linkedList * queue: * @author Beck * */ public class QueueTest {private LinkedList<String> link = new LinkedList<String>(); Public void put(String STR){link.addFirst(STR); } // Get public Stringget() {returnlink.removeLast(); } // Check whether it is empty public BooleanisEmpty() {returnlink.isEmpty(); }} package learn Java; Public class Test {public static void main(String[] args) {QueueTest queue = new QueueTest(); queue.put("I was the first one in line.");
queue.put("I was the second one in line.");
queue.put("I was the third person in line.");
queue.put("I was the fourth person in line."); // Walk through the queuewhile(! queue.isEmpty()){ String str = queue.get(); System.out.println(str); } // Print the result /* I'm first in the queue I'm second in the queue I'm third in the queue I'm fourth in the queue */}}Copy the codeVector: obsolete, replaced by ArrayList; It also has an iterator that is retrieved from vector.elements(). The methods used to determine the presence and fetch elements are hasMoreElements(), nextElement().
Package learn Java well; 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");
vector.add("vector");
vector.add("list");
Enumeration<String> elements = vector.elements();
while(elements.hasMoreElements()){ String nextElement = elements.nextElement(); System.out.println(nextElement); }}}Copy the codeSet:
Set sets include: HashSet, LinkedHashSet, TreeSet
HashSet stores strings:
Package learn Java well; import java.util.HashSet; import java.util.Iterator; import java.util.Set; Public class Test {public static void main(String[] args) {// Use HashSet to access Set<String>set = new HashSet<String>();
set.add("Oh my God.");
set.add("I am repetitive.");
set.add("I am repetitive.");
set.add("welcome"); Iterator<String> it = set.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 result, the duplicate has been removed /* my day welcome I am duplicate -------------- my day welcome I am duplicate */}Copy the codeSo how do hash tables guarantee uniqueness? Hash tables are guaranteed uniqueness through hashCode and equals.
The procedure for storing data in a hash table (the underlying hash table also maintains an array) :
Calculate the hashCode value based on the stored elements, and then calculate the subscript of the storage based on the calculated hashCode value and the length of the array. If the position of the subscript has no element, it is stored directly; If there are elements, then use the equals method with the element to be saved. If the result is true, then the same element already exists, so it is not saved. If the result is false, store it as a linked list.
Using HashSet to store custom objects:
Package learn Java well; Public class Person {// attribute private String name; private int age; // Constructor publicPerson() { super(); } public Person(String name, int age) { super(); this.name = name; this.age = age; } // To store unique elements in a hash table, you must Override hasCode and equals @override public inthashCode() {
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 learn Java well; import java.util.HashSet; import java.util.Set; Public class Test {public static void main(String[] args) {public static void main(String[] args) {set = new HashSet<Person>();
set.add(new Person("Zhang", 12));
set.add(new Person("Bill", 13));
set.add(new Person("Fifty", 22));
set.add(new Person("Zhang", 12)); / / traversefor (Person p : set){ System.out.println(p); /*Person [name= Person, age=22] Person [name= Person, age=13] */Copy the codeSo when storing custom objects into a HashSet, the hashCode and equals methods must be overridden to ensure that the set is unique.
LinkedHashSet:
Is based on linked list and hash table common implementation, so have access to order, the element is unique
Package learn Java well; import java.util.LinkedHashSet; Public class Test {public static void main(String[] args) {public static void main(String[] args) {set = new LinkedHashSet<Person>();
set.add(new Person("Zhang", 12));
set.add(new Person("Bill", 13));
set.add(new Person("Fifty", 22));
set.add(new Person("Zhang", 12)); / / traversefor (Person p : set){ System.out.println(p); } // Result: Store two triple objects into the set, but the set successfully stored one, // and the order in which they were stored, /*Person [name= name, age=12] Person [name= name, age=22]*/}}Copy the codeTreeSet:
** Features: ** access is unordered, elements are unique, and can be sorted (sorting is done when adding).
TreeSet is a data structure based on binary trees. One node cannot contain more than two nodes.
Binary tree stored procedure:
If it’s the first element, it’s stored as the root node, and the next element that comes in is compared to the node, and if it’s bigger than the node, it’s to the right, and if it’s smaller than the node, it’s to the left; Equals the node does not store. Subsequent elements are compared until there is space to store them
The TreeSet collection stores strings
Package learn Java well; 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); } /* ABC CBC XBC ZBC */Copy the codeTreeSet guarantees element uniqueness in two ways:
Comparable (0, 0); Comparable (0, 0); Comparable (0, 0);
When TreeSet is created, we pass the Comparator interface implementation object into the constructor. The implementation of the Comparator interface overrides the compara method.
A ClassCastException occurs when a custom object is saved to TreeSet and the custom class does not implement the Comparable interface, or when a Comparator is not passed in
Here are two ways to store custom objects
Package learn Java well; Public class Person implements Comparable<Person>{// attribute private String name; private int age; // Constructor publicPerson() { super(); } public Person(String name, int age) { super(); this.name = name; this.age = age; } // To store unique elements in a hash table, you must Override hasCode and equals @override public inthashCode() {
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);
}
returnresult; }} package learn Java; import java.util.TreeSet; Public class Test {public static void main(String[] args) {TreeSet<Person> TreeSet = new TreeSet<Person>(); Treeset. add(new Person(); // The Person class implements the Comparable interface and rewrites the comparaTo method."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 four.", 17));
treeSet.add(new Person("Zhang shan 5", 20));
for(Person p : treeSet){ System.out.println(p); } // Result: Person [name= name, age=13] Person [name= name, age=16] Person [name= name, age=16] Person [name= name, age=20] */}}Copy the codeAnother way: use the Comparator
Package learn Java well; Public class Person{// attribute private String name; private int age; // Constructor publicPerson() { super(); } public Person(String name, int age) { super(); this.name = name; this.age = age; } // To store unique elements in a hash table, you must Override hasCode and equals @override public inthashCode() {
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 learn Java well; import java.util.Comparator; import java.util.TreeSet; Public class Test {public static void main(String[] args) {// Use TreeSet to store custom Person objects // The TreeSet object is created by passing in the Comparator using an anonymous inner class. The comparison rules are sorted 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());
}
returnresult; }}); 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 four.", 17));
treeSet.add(new Person("Zhang shan 5", 20));
for(Person p : treeSet){ System.out.println(p); } // Result: /* Person [name= js1, age=13] Person [name= js1, age=16] Person [name= js1, age=17] Person [name= name, age=20] */}}Copy the codeComparator summary:
Summary of Collection system:
-
List :” Features :” Access ordered, elements indexed, elements can be repeated.
-
ArrayList: Array structure, query fast, slow to add and delete, thread unsafe, therefore high efficiency.
-
Vector: an array structure that is fast to query, slow to add and delete, thread-safe, and therefore inefficient.
-
LinkedList: LinkedList structure, slow query, fast add and delete, thread insecurity, therefore high efficiency.
addFirst() removeFirst() getFirst()
Copy the code-
Features :” Access disorder, elements without index, elements can not be repeated.
-
HashSet: Unordered storage, element without index, element cannot be repeated. The bottom layer is a hash table.
How does a hash table ensure that elements are unique? The bottom line is to rely on hashCode and equals methods.
When storing elements, calculate an index based on the hashCode + array length to determine if there are elements in the index position.
If there are no elements, store them directly. If there are elements, check equals to see if the two elements are the same. If they are different, store them and discard them.
The elements of our custom object store must implement hashCode and equals.
-
LinkedHashSet: Stored in order, elements cannot be repeated.
-
TreeSet: Access is unordered, but can be sorted (naturally sorted). Elements cannot be repeated.
There are two ways to sort:
- Natural ordering:
Our elements must implement the Comparable interface. Implement CompareTo method.
- Comparator sort:
We need a custom class that implements the Comparetor interface, and this class is the comparator that implements the Compare method.
The comparator object is then passed to the TreeSet as a parameter when it is created.
Map:
A Map is a two-column collection that holds key-value pairs. The keys are required to be unique and the values can be repeated
Key values are one-to-one; a key can only correspond to one value
**Map features: ** is unordered access, keys cannot be repeated
When a Map is stored, it passes key values into the Entry and then stores the Entry object
Below them are the HashMap, LinkedHashMap, and TreeMap
A HashMap:
Is implemented based on a hash table structure, so when storing custom objects as keys, you have to override hasCode and equals methods. Access unordered
Here’s how HashMap uses custom objects as keys:
Package learn Java well; 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) {public static void main(String[] args) {public static void main(String[] args)hashHashMap<Person,String> map = new HashMap<Person,String>(); map.put(new Person("Zhang", 12), "JAVA");
map.put(new Person("Bill"13),"IOS");
map.put(new Person("Flower", 22)."JS");
map.put(new Person("Black", 32), "PHP");
map.put(new Person("Zhang", 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: If the Map keys are the same, /* Person [name= Person, age=13]-- IOS Person [name= Person, age=12]-- C++ Person [name= Person, age=12] Age = 32] - PHP Person [name = floret, age = 22] - JS * /}}Copy the codeLinkedHashMap:
The usage is basically the same as HashMap. It is based on the structure of linked list and hash table, so it has the characteristics of orderly access and non-duplicate keys
The following example uses LinkedHashMap storage, noting that the order of storage is the same as the order of traversal:
Package learn Java well; import java.util.LinkedHashMap; import java.util.Map.Entry; Public class Test {public static void main(String[] args) {public static void main(String[] args) {public static void main(String[] args)hashCode and equals methods LinkedHashMap<Person,String> map = new LinkedHashMap<Person,String>(); map.put(new Person("Zhang", 12), "JAVA");
map.put(new Person("Bill"13),"IOS");
map.put(new Person("Flower", 22)."JS");
map.put(new Person("Black", 32), "PHP");
map.put(new Person("Zhang", 12), "C++"); / / foreach traversalfor (Entry<Person,String> entry : map.entrySet()){
System.out.println(entry.getKey()+"= = ="+entry.getValue()); } // If the Map has the same key, the last value will overwrite the previous value. LinkedHashMap is characterized by orderly access, /* Person [name= name, age=12]== C++ Person [name= name, age=13]===IOS Person [name= small, age=13]===IOS Person [name= small, age=13]=== Age 22] = = = = JS Person [32] name = black, age = = = = * / PHP}}Copy the codeTreeMap:
Save a custom object to the TreeMap collection. The custom object is used as the key of the TreeMap collection. Due to the binary tree used at the bottom of TreeMap, all data stored in TreeMap need to be sorted. To sort, objects are required to have comparison function. The class to which the object belongs needs to implement the Comparable interface. Or pass a Comparator interface object to the TreeMap collection.
Use TreeMap to store custom objects as keys:
Package learn Java well; import java.util.Comparator; import java.util.Map.Entry; import java.util.TreeMap; Public class Test {public static void main(String[] args) { Implement the Comparable interface or pass in 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());
}
returnresult; }}); map.put(new Person("Zhang", 12), "JAVA");
map.put(new Person("Bill", 50), "IOS");
map.put(new Person("Flower", 32), "JS");
map.put(new Person("Black", 32), "PHP");
map.put(new Person("Zhang", 12), "C++"); / / foreach traversalfor (Entry<Person,String> entry : map.entrySet()){
System.out.println(entry.getKey()+"= = ="+entry.getValue()); } // If the Map has the same key, the last value will overwrite the previous value. TreeMap is pulled out in a sorted order, /* Person [name= name, age=12]===C++ Person [name= small, age=32]===JS Person [name= small, age=32]===JS Age = = = = 32] PHP Person [50] name = li si, the age = = = = IOS * /}}Copy the codeSecond, advanced summary of set
Arrays and first class objects
An array identifier is actually a handle to a real object, regardless of the type of array being used. The objects themselves are created in the memory “heap”. Heap objects can be created either “implicitly” (that is, by default) or “explicitly” (that is, explicitly specified, with a new expression). Part of the heap object (actually the only field or method we can access) is the read-only Length member, which tells us how many elements can fit in that array object. For array objects, the “[]” syntax is the only alternative access method we can use.
Arrays of objects and arrays of primitive data types are almost identical in how they are used. The only difference is that object arrays hold handles, whereas primitive arrays hold concrete 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); // 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); // Initialization syntax: e = new int[] {1, 2}; System.out.println("e.length = "+ e.length); }}Copy the codeThe 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
Where array A is simply initialized to a NULL handle. At this point, the compiler forbids us from actually doing anything with the handle unless it has been properly initialized. Array B is initialized to point to an array of Weeble handles, but there are no actual Weeble objects in that array. However, we can still query the size of that array because B points to a legitimate object.
In other words, we only know the size or capacity of an array object, not how many elements it actually holds.
However, since an array object is automatically initialized to NULL when it is created, it is possible to check for NULL and determine whether a particular array “empty” holds an object. Similarly, arrays of primitive data types are automatically initialized to zero (for numeric types), NULL (for character types), or false (for Boolean types)
Array C shows that we first create an array object and then assign Weeble objects to all the “vacancies” in that array. Array D reveals the “collection initialization” syntax to create array objects (explicitly with the new command, similar to array C) and then initialize them with Weeble objects, all in one statement. The following expression:
a = d;
Copy the codeI showed you how to take a handle to a connection of the same array object and assign it to another array object, okay
1. Collection of basic data types Collection classes can only hold object handles. An array, on the other hand, can contain both primitive types of data directly and handles to objects. Using “wrapper” classes such as Integer and Double, you can put values of basic data types into a collection.
Either putting data of a primitive type into an array or encapsulating it into a class in a collection is a matter of execution efficiency. Obviously, it is much more efficient to create and access an array of primitive data types than to access a collection of encapsulated data.
Return of an array
Suppose we now want to write a method that doesn’t just return one thing, but a series of things. At this point, languages like C and C++ complicate matters because we cannot return an array, only a pointer to it. This can be very troublesome because it is difficult to control the “lifetime” of an array, and it can easily lead to memory “holes”.
Java takes a similar approach, but we can “return an array.” Of course, the actual return is still a pointer to the array. But in Java, we never have to worry about whether that array is available or not — it exists automatically as long as we need it. And the garbage collector will automatically clean it up when we’re done
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 the codeThe flavorSet() method creates a String array named Results. The size of the array is n — depending on the argument we pass to the method. It then randomly picks “flavors” from the flav array and places them in Results, eventually returning results. Returning an array is no different from returning any other object — what you end up returning is a handle.
On the other hand, note that when the flavorSet() randomly selects a spice, it needs to ensure that a random selection that occurred before does not occur again. To do this, it uses an infinite while loop that keeps making random selections until it finds an element that hasn’t been included in the Picks array. (Of course, string comparisons can also be done to check if random selections have been included in the Results array, but string comparisons are less efficient.) If successful, the element is added and the loop is broken to find the next one (I is incremented). But if t is an array that has already appeared under PICKS, force a new T by jumping back two levels with the labeled continue. This process can be seen clearly with a debugger.
A collection of
To accommodate a set of objects, the most appropriate choice should be an array. And arrays are a must if you’re holding a range of basic data types.
** Disadvantages: ** type unknown
The “downside” of using Java collections is that you lose type information when putting objects into a collection. This happens because when the collection was written, the programmer had no idea what type the user wanted to put into the collection. Instructing a collection to allow only certain types prevents it from being a “general-purpose” tool, causing problems for users. To solve this problem, the collection actually holds handles to objects of type Object.
Of course, note that the collection does not include primitive data types, because they are not inherited from “anything.” Java does not allow people to abuse objects placed into collections. If you throw a dog into a cat collection, you still treat everything in the collection as a cat, so you get an “illegal” error when using that dog. In the same sense, if you try to “shape” a dog handle to a cat, you still get an “illegal” error at run time
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 the code- In some cases, the program seems to work correctly and does not sculpt back to our original type. The first case is quite special: the String class gets extra help from the compiler to make it work. Whenever the compiler expects a String and doesn’t get one, it automatically calls the toString() method defined in Object that can be overridden by any Java class. This method generates a String that meets the requirements and then uses it when we need it. So all you have to do to make your class’s objects visible is override the 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 the codeYou can see the toString() redefinition code in Mouse. In the second for loop of main(), you can find the following statement:
System.out.println("Free mouse: " +
mice.elementAt(i));
Copy the codeAfter “+”, the compiler expects to see a String. ElementAt () generates an Object, so to get the desired String, the compiler calls toString() by default. Unfortunately, you can only get something like this for strings; This conversion is not done for any other type.
The second method of hiding shapes is already used in Mousetrap. Instead of receiving a Mouse, the caughtYa() method receives an Object. Then it was shaped as a Mouse. Of course, this is very bold, because by receiving an Object, anything can be passed to the method. However, if the styling is incorrect — if we pass the wrong type — we get a violation error at run time. This is certainly not as good as checking at compile time, but it can still prevent problems. Note that no modeling is required when using this method: mousetrap.caughtya (mice.elementat (I));
- A more “robust” solution would be to use Vector to create a new class that accepts only the types we specify and generates only the types 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 the codeThe new GopherVector class has a private member of type Vector (inheriting from Vector is a bit tricky, for reasons we’ll see later), and the methods are similar to Vector. However, it does not receive and generate ordinary objects and is only interested in Gopher objects. Since Gopher vector only receives a Gopher, suppose we use: gophers.addelement (New Pigeon()); You get an error message at compile time. This way, even though it’s more tedious from a coding standpoint, you can immediately tell if you’re using the right type. Note that you don’t have to sculp when you use elementAt() — it’s definitely a Gopher
The enumerator
Accommodating a variety of objects is the primary task of collections. In Vector, addElement() is the method we use to insert objects, and elementAt() is the only method to extract objects. Vector is very flexible, we can select anything at any time, and we can select multiple elements using different indexes. If you look at the problem from a higher perspective, you’ll see one drawback: you need to know the exact type of the collection in advance, or you can’t use it. At first glance, this may not seem relevant. But what if you decide to use a Vector initially, and then later in your program decide (for efficiency reasons) to change to a List that is part of the Java1.2 collection library? We often think of iterators as “lightweight” objects; In other words, it costs very little to create. But it is for this reason that we often find iterators with limitations that seem strange. For example, some iterators can only move in one direction. The Enumeration of Java is an example of an iterator with these limitations. You can’t use it for anything else except: (1) Ask the collection to give us an Enumeration with a method called elements(). The first time we call its nextElement(), the Enumeration returns the first element in the sequence. (2) Get the next object with nextElement(). (3) Use hasMoreElements() to 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 the codeTake a closer look at the printing method:
static void printAll(Enumeration e) {
while(e.hasMoreElements())
System.out.println(
e.nextElement().toString());
}
Copy the codeNotice that there is no information about the sequence type. All we have is Enumeration. To learn about sequences, an Enumeration is sufficient: to get the next object, and to know if the end has been reached. Taking a series of objects and then walking through them to perform a specific operation is a valuable programming concept
Types of collections
V e c t o r
The Java standard collection includes toString() methods, so they can generate their own String representations, including the objects they hold. In Vector, for example, toString() steps and iterates through the elements of the Vector, calling toString() for each element. Suppose we now want to print out the address of our class. It might seem as if we could simply refer to this (especially as C++ programmers tend to do) :
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 the codeWhat happens here is an automatic type conversion of the string. When we use the following statement: “CrashJava Address:” + this The compiler finds a “+” at the end of a string and something else that doesn’t look like a string, so it tries to convert this to a string. The conversion calls toString(), which produces a recursive call. If this happens in a Vector, it looks like the stack will overflow and 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’s toString method. Instead of adding this, use super.tostring (). Of course, there is one caveat to this approach: we must inherit directly from Object, or there is no parent class that overrides the toString method.
B i t S e t
A BitSet is actually a Vector of “bits”. If you want to efficiently store large amounts of on-off information, use bitsets. It only makes sense in terms of size; If you want efficient access, it will be slower than using arrays of some inherent type. The minimum length of a BitSet is the length of a Long integer: 64 bits. This means that if we are going to save smaller data than this, such as 8-bit data, the BitSet would be wasteful. So it’s best to create your own class that holds your own flag bits.
S t a c k
A Stack is sometimes called a LIFO (last in, first out) set. In other words, the last thing we “push” into the stack will be the first thing that pops up later. Like all Other Java collections, what we press in and pop out are “objects,” so we have to “shape” what we pop out. Here is a simple stack example that reads each line of an array and pushes it onto 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 the codeEach row of the Months array is inherited into the stack by push() and later taken out from the top of the stack with pop(). It should be noted that Vector operations can also be performed on Stack objects. This may be determined by inherited qualities — a Stack “belongs” to a Vector. Thus, operations that can be done on a Vector can also be done on a Stack, such as the elementAt() method
H a s h t a b l e
Vector allows us to select a number from a list of objects, so it actually associates the number with the object. But what if we wanted to select a set of objects based on other criteria? The stack is an example of this: it is selected on the basis of “last thing on the stack”. This concept of “selecting from a list of objects” can also be called a “map”, a “dictionary” or an “associative array”. Conceptually, it looks like a Vector, but instead of looking up objects by numbers, it looks up them by another object! This usually belongs to an important process within a program. In Java, this concept is embodied in the abstract class Dictionary. The interface to this class is very intuitive size() telling us how many elements it contains; IsEmpty () checks if it contains elements (true if it does); Put (Object key, Object value) Adds a value (something we want) and associates it with a key (something we want to search for it); Get (Object key) Retrieves the value corresponding to a key; Remove (Object Key) is used to remove key-value pairs from the list. Enumeration techniques can also be used: keys() produces an Enumeration of keys; Elements () produces an enumeration of all values. That’s what a Dict Ionary is all about.
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 the codeThe first problem we noticed in the definition of AssocArray is that it “extends” the dictionary. This means that AssocArray is a type of Dictionary, so you can make the same request to it as to Dictionary. If you want to generate your own Dictionary, and do it right here, all you have to do is populate all the methods that reside in the Dictionary (and you have to override all of them, because they — except for the builder — are abstract). The standard Java library contains only one variant of Dictionary, called Hashtable. Java hash tables have the same interface as AssocArray (because both inherit from Dictionary). But there is one area that does: execution efficiency. If you think about what you have to do for a get(), searching for keys in a Vector is much slower. But using hash tables can speed things up a lot. Instead of using lengthy linear search techniques to find a key, you use a special value called a “hash code.” A hash code takes information from an object and converts it to a “relatively unique” integer (int) for that object. All objects have a hashCode, and hashCode() is a method of the root Object class. Hashtable gets the object’s hashCode() and uses it to quickly find keys.
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++;
elseht.put(r, new Counter()); } System.out.println(ht); }}Copy the code- Creating “key” classes But when using hash tables, we run into a very common problem once we create our own class to use as a key. For example, suppose a weather forecast system matches a Groundhog object as Prediction. This seems straightforward enough: We create two classes, then use Groundhog as the key and Prediction as the value. As follows:
class Groundhog { int ghNumber; Groundhog(int n) { ghNumber = n; }} class Prediction {Boolean shadow = math.random () > 0.5; public StringtoString() {
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 the codeThe problem is that Groundhog inherits from the generic Object root class (all classes end up inheriting from Object if the base class is not originally identified). The hashCode for each Object is actually generated using the Object’s hashCode() method, and by default only the address of its Object is used. So, the first instance of Groundhog(3) does not produce the same hashCode as the second instance of Groundhog(3), and we might think that all we have to do at this point is overwrite hashCode() properly. But this still doesn’t work, unless you do one more thing: override equals(), which is also part of Object. This method is used when the hash table is trying to determine whether our key is equal to a key in the table. Similarly, the default object.equals () simply compares Object addresses, so one Groundhog(3) does not equal another Groundhog(3). Therefore, in order to use your own class as a key in a hash table, you must override both hashCode() and equals(), as shown below:
class Groundhog { int ghNumber; Groundhog(int n) { ghNumber = n; }} class Prediction {Boolean shadow = math.random () > 0.5; public StringtoString() {
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 the codeGroundhog2.hashcode () returns the marmot number as an identifier (in this case, the programmer needs to ensure that no two marmots coexist with the same ID number). To return a unique identifier, hashCode() is not needed, and equals() must be able to strictly determine whether two objects are equal. The equals() method does two checks: checks if the object is null; If not, continue to check if it is an instanceof Groundhog2 (using the instanceof keyword). It should be a Groundhog2 even in order to continue equals(). As you can see, this comparison is based on actual ghNumber. Once we run the program this time, we’ll see that it finally produces the correct output (many Java library classes override the hashCode () and equals() methods to accommodate what they provide).
Again, enumerators
Separate the operations that traverse a sequence from the infrastructure of that sequence. In the example below, the PrintData class moves through a sequence with an Enumeration and calls the toString() method for each object. At this point, two collections of different types are created: a Vector and a Hashtable. Since Enumeration hides the structure of the base set, PrintData doesn’t know or care what type of set Enumeration comes from:
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 the codeNote that printData.print () takes advantage of the fact that the objects in these collections belong to the Object class, so it calls toString(). However, it is often necessary to ensure that your Enumeration traverses a particular type of collection when solving your own practical problems. For example, you might require that all elements in the collection be a Shape with the draw() method. If this is the case, the Shape must be traced back from the Object returned by enumeration.nextelement () to produce a Shape.
The sorting
One of the problems with writing generic sort code is that you have to perform comparison operations based on the actual types of objects to achieve the correct sort. One solution, of course, is to write a different sorting method for each different type. However, be aware that if you do this, it will be difficult to reuse your code later when adding new types. A major goal of programming is to “separate what changes from what stays the same.” In this case, the code that remains the same is the generic sorting algorithm, while what changes each time it is used is the actual comparison of objects. Therefore, instead of “hard-coding” the comparison code into multiple different sorting routines, we use a “callback” technique. With callbacks, the part of code that changes often is encapsulated in its own class, while code that always stays the same “calls back” the changed code. In this way, different objects can express different comparisons while passing them the same sort code. The following “Interface” shows how to compare two objects, encapsulating those “things that will change” :
interface Compare {
boolean lessThan(Object lhs, Object rhs);
boolean lessThanOrEqual(Object lhs, Object rhs);
}
Copy the codeFor both methods, LHS represents the “left-handed” object in this comparison, while RHS represents the “right-handed” object. We can create a subclass of Vector to “quicksort” by using Compare. 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 the codeTo use SortVector, we must create a class that implements Compare for the sorted objects we prepare. Inner classes are not particularly important at this point, but they are beneficial to the organization of your code. Here is an example of a String 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 the codeOnce the framework is in place, it’s very easy to reuse a design like this — simply write a class that encapsulates what “needs to change,” Then passing an object to SortVector extends here to create a Vector of a new type — that is, SortVector is a Vector with some additional functionality. Inheritance can play a big role here, but it brings problems. It makes some methods final, so they cannot be overridden. If you want to create an ordered Vector that only receives and generates strings, you run into trouble. Because addElement() and elementAt() both have final attributes, and they are methods that we must override otherwise we cannot achieve only receiving and producing strings. On the other hand, consider the “composition” approach: put an object inside a new class. Instead of rewriting the above code to do this, we simply use a SortVector in the new class. In this case, the inner class that implements the Compare interface can be created “anonymously.
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 the codeThe new collection
List x = new LinkedList();
Copy the codeOf course, you can also decide to use X as a LinkedList (rather than a regular List) and load the exact type information with X. The advantage of using interfaces is that once you decide to change your implementation details, all you have to do is change it at creation time, as follows:
List x = new ArrayList();
Copy the codeIn the hierarchical structure of classes, you see a large number of classes that begin with “Abstract,” which can be confusing at first. They are really tools for “partially” implementing a particular interface. For example, if you want to generate your own Set, you don’t start with the Set interface and implement all the methods yourself. Instead, we can inherit from AbstractSet and get our own new classes with minimal effort. Still, the new collections library contains enough functionality to meet almost all of our needs. So for our purposes, we can ignore all classes that begin with “Abstract”. So, when looking at this diagram, the only things you really need to care about are the “interface” at the top and the normal (real) class — both surrounded by solid line boxes. Typically, you need to generate an object of the actual class and shape it up to the corresponding interface. You can then use that interface anywhere in your code. Here is a simple example that populates a collection with a String object and prints 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 the codeThe first line of main() creates an ArrayList object, which is then molded up to a collection. Since this example uses only the Collection method, any object of a class inherited from Collection will work fine. But an ArrayList is a typical Collection that replaces a Vector. The add() method puts a new element into the collection. However, the user documentation is careful to note that add() “guarantees that the collection contains the specified elements.” This foreshadows Set, which will actually add the element only if it doesn’t exist. For arrayLists and any other form of List, add() definitely means “join directly.” Using the iterator() method, all sets generate an iterator. An iterator is just like an “Enumeration”, except that (1) it uses a historically default name that has been widely adopted in OOP (iterators). (2) Use shorter names than Enumeration: hasNext() replaces hasMoreElement() and next() replaces nextElement(). (3) Added a new method called remove() that removes the last element generated by Iterator. So every time you call next(), you only need to call remove() once
C o L L E C T I o N s
The table below summarizes everything you can do with a collection (you can do the same with sets and lists, although lists provide some additional functionality). Map does not inherit from Collection, so it is treated separately
Boolean add(Object) * Ensures that the collection contains arguments. If it does not add arguments, return false (false) Boolean addAll(Collection) * addAll elements in the argument. Void clear() * Delete all elements in the set. Boolean Contains (Object) Return true Boolean containsAll(Collection) returns true Boolean isEmpty() if there are no elements in the Collection, Iterator () returns an Iterator that iterates through the elements of the set. Boolean remove(Object) * If an argument is in the set, it removes an instance of that element. Boolean removeAll(Collection) * Removes all elements in the argument. Return “true” Boolean retainAll(Collection) * if any deletions have been made only the elements contained in an argument (a theoretical “intersection”). Int size() returns the number of elements in the collection. Object[] toArray() returns an array containing all the elements in the collection. * This is an “optional” method, and some collections may not implement it. If so, this method will encounter a UnsupportedOperatiionException, that is, a “operation is not supported” violation.
The following example demonstrates all of these methods. Again, they only work for things inherited from collections, and an ArrayList is used as a kind of “uncommon denominator.
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 the codeBoth versions of newCollection() create arrayLists to contain different datasets and return them as collection objects. So obviously, nothing else will be used except the Collection interface.
L, I, S, T, s
List (interface) ordering is the most important feature of lists; It ensures that elements are arranged in a specified order. List adds a number of methods to the Collection so that we can insert and delete elements in the middle of the List (only recommended for LinkedList). Lists also generate a ListIterator, which can be used to walk through a List in both directions, inserting and deleting elements in the middle of the List (again, this is only recommended for linkedLists). ArrayList Is a List that is extrapolated from an array. Used as a general-purpose object container in place of the original Vector. Allows us to access elements quickly, but is a bit slow to insert and delete elements from the middle of the list. ListIterator should generally only be used to traverse an ArrayList forward and backward, not to delete and insert elements; It is less efficient than LinkedLists. Many LinkedLists provide optimized sequential access performance while efficiently inserting and deleting in the middle of the list. But when it comes to random access, the speed is rather slow, and ArrayList should be used instead. AddFirst (), addLast(), getFirst(), getLast(), removeFirst(), and removeLast() (not defined in any interface or base class) are also provided for use as a specification, queue, and a two-way queue
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 the codeIn basicTest() and iterMotiion(), calls are simply made to reveal the correct syntax. And although the return value is captured, it is not used. In some cases, return values are not captured because they are not particularly useful. Before using them, you should carefully study your online documentation to understand the complete and correct use of these methods.
ArrayList Example
import java.awt.List; import java.util.ArrayList; import java.util.Iterator; /** * @author sihai * @time 2018/4/19 * ArrayList //ArrayList Usage Example ArrayList<String> m_ArrayList=new ArrayList<String>(); m_ArrayList.add("Evankaka");
m_ArrayList.add("sihai");
m_ArrayList.add("Dede");
m_ArrayList.add("Evankaka");
m_ArrayList.add("Little red");
m_ArrayList.set(2,"sihai2"); M_arraylist.add (3,"Learn Java."); Iterator<String> it_ArrayList = m_arraylist.iterator (); Iterator<String> it_ArrayList = m_arraylist.iterator (); System.out.println(ArrayList traversal method 1);
while(it_ArrayList.hasNext()) { System.out.println(it_ArrayList.next()); } //ArrayList (system.out.println)ArrayList traversal method 2);
for(Object o:m_ArrayList){ System.out.println(o); } //ArrayList (system.out.println)ArrayList traversal method 3);
for(int i = 0; i<m_ArrayList.size(); i++){ System.out.println(m_ArrayList.get(i)); } // Delete the element 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("Learn Java.")){
it_ArrayList.remove();
}else{ System.out.println(m_String); }}}}Copy the codeOutput result:
Evankaka Sihai Sihai2 Evankaka Sihai Sihai2 Evankaka Sihai Sihai2 Evankaka Sihai Sihai2 Evankaka Sihai Sihai2 Sihai sihai2 Evankaka sihai2 Evankaka Sihai2 Evankaka Sihai2 Evankaka Sihai2 Evankaka Sihai2
ArrayList note
(1) Do not modify collection elements when Iterator is used. Otherwise, an exception will be raised. And Iterator can only iterate backwards (2). If you want to get rid of an element in the loop, you can only call it.remove, not list.remove, or you’ll get a concurrent access error.
Use S, e, T, S
A Set is nothing more than a Collection with different behaviors (this is an ideal application of instances and pleomorphism: to express different behaviors). Here, a Set allows only one instance of each object (as you will see later, the composition of an object’s “values” can be quite complex). Each element added to a Set must be unique; Otherwise, Set does not add duplicate elements. Objects added to a Set must define equals() to establish uniqueness. Set has exactly the same interface as Collection. A Set is not guaranteed to maintain its elements in any particular order. A HashSet is used for all but very small sets. The object must also define a hashCode() ArraySet as a Set extrapolated from an array. Design for very small sets, especially those that require frequent creation and deletion. For small sets, an ArraySet is much less expensive to create and iterate over than a HashSet. But as Set gets bigger, its performance degrades. No need for HashCode() TreeSet sequential Set derived from a “red-black tree” backward (note ⑦). In this way, we can refer to a sequential Set from a 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 the codeDuplicate values are added to the Set, but when printing, we see that the Set accepts only one instance of each value. When you run this program, you’ll notice that the order maintained by a HashSet is different from an ArraySet. This is because they take different approaches to saving elements for their later positioning. Arraysets retain their sequential state, whereas hashsets use a hash function, which is specifically 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 the codeBut it’s only necessary to use hashCode() if you want to put the class into a HashSet — which is entirely possible, since you usually choose to implement it as a Set first.
M, a, P, s
Map (interface) maintains a key-value mapping (pair) to find the corresponding value by a key HashMap is implemented based on a Hashtable (instead of Hashtable). This form provides the most stable performance for key-value pair insertion and retrieval. This performance can be tuned through the builder to set the hash table’s “capability” and “load factor” ArrayMap the Map that is extrapolated from an ArrayList. Provides precise control over the sequence of iterations. Design for very small maps, especially those that need to be created and deleted frequently. For very small maps, the cost of creation and iteration is much lower than for hashMaps. However, as the Map becomes larger, performance is correspondingly significantly reduced. TreeMap is implemented on a red-black tree basis. When you view keys or key-value pairs, they are arranged in a fixed order (depending on Comparable or Comparator, which is discussed later). The best thing about TreeMap is that we get sorted results. TreeMap is the only Map with a subMap() method that returns a portion 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 the codeTraverse the Map instance
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"."Learn Java.");
map.put("third"."sihai");
map.put("first"."sihai2"); Println (map.keyset) {system.out.println ();"= = = = = = = = = = = = = = = = = = = by Map. The keySet traverse the key and the value: = = = = = = = = = = = = = = = = = = =");
for (String key : map.keySet()) {
System.out.println("key= " + key + " and value= "+ map.get(key)); } // Iterator iterator through the key and value system.out.println ("= = = = = = = = = = = = = = = = = = = by Map. The entrySet use iterator traverses the key and the 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()); } // entrySet traverses key and value system.out.println ("= = = = = = = = = = = = = = = = = = = by Map. The entrySet traverse the key and the value: = = = = = = = = = = = = = = = = = = =");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= "+ entry.getValue()); } // Map.values() traverses all values, but not key system.out.println ()"= = = = = = = = = = = = = = = = = = = by Map. The values () to iterate through all the value: = = = = = = = = = = = = = = = = = = =");
for (String v : map.values()) {
System.out.println("value= "+ v); }}}Copy the codeThe following output is displayed:
= = = = = = = = = = = = = = = = = = = by Map. The keySet traverse the key and the value: = = = = = = = = = = = = = = = = = = = key = third and value = sihai key = first and value = sihai2 Key = second and value = have a good learning Java = = = = = = = = = = = = = = = = = = = by Map. The entrySet use iterator traverses the key and the value: = = = = = = = = = = = = = = = = = = = key = third and Value = sihai key= first and value= sihai2 key= second and value= Learn Java = = = = = = = = = = = = = = = = = = = by Map. The entrySet traverse the key and the value: = = = = = = = = = = = = = = = = = = = key = third and value = sihai key = first and value = Sihai2 key = second and value = have a good learning Java = = = = = = = = = = = = = = = = = = = by Map. The values () to iterate through all the value: = = = = = = = = = = = = = = = = = = = value = sihai Value = sihai2 value= Learn Java
Decide which collection to use
ArrayList, LinkedList, and Vector (roughly equivalent to ArrayList) all implement the List interface, so our program will get similar results no matter which one we choose. However, an ArrayList (and a Vector) is derived from an array backwards; LinkedList is implemented as a regular double-linked list, because each individual object contains data and handles to elements before and after the list. For this reason, if you want to do a lot of insert and delete operations in the middle of a list, then LinkedList is the best choice (LinkedList has some additional functionality built into AbstractSequentialList). If not, opt for ArrayList, which is probably faster. As another example, a Set can be implemented as either an ArraySet or a HashSet. An ArraySet is derived from an ArrayList and is designed to support only a small number of elements, making it particularly useful in situations where you need to create and delete a large number of sets. However, the performance of an ArraySet suffers when you need to accommodate a large number of elements in your own Set. When writing a program that requires a Set, choose HashSet by default. And you should switch to ArraySet only in some special cases, where there is a compelling need to improve performance.
1. Decide which List to use
The easiest way to see the differences between List implementations is to take a one-time performance 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 voidtest(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 the codeThe inner class Tester is an abstract class that provides a base class for a particular test. It contains a string to print at the start of the test, a size parameter to count the number of tests or elements, a builder to initialize the field, and an abstract method test(). Test () does the most practical testing. All types of tests come together in one place: the Tests array. We initialize this array with a different anonymous inner class that inherits from Tester. To add or remove a test item, you simply add or remove an inner class definition from the array, and everything else 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 the codeRandom accesses (get()) and loops in an ArrayList are the most rewarding; But it’s a lot of overhead for LinkedList. On the other hand, inserting and deleting in the middle of the list is much more cost-effective for a LinkedList than an ArrayList. Our best bet is probably to choose an ArrayList as our default starting point. Later, if you find that performance degrades due to a lot of inserts and deletions, consider switching to LinkedList.
2. Decide which Set to use
You can choose between an ArraySet and a HashSet, depending on the size of the Set (TreeSet; if you need a sequential list from a Set).
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 voidtest(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 the codeWhen you do add() and contains(), HashSet is obviously much better than ArraySet, and performance obviously doesn’t depend on the number of elements. You almost never need to use an ArraySet when you’re writing a program
3. Decide which Map to use
When choosing different Map implementations, note that the size of the Map has the greatest impact on performance, as the following test program clearly illustrates:
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 voidtest(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 the codeSince the size of the Map is the most serious problem, the program’s timing tests are split by the size (or capacity) of the Map in order to get convincing test results. Here’s a list of results (which may vary on your machine) : Even at size 10, ArrayMap performs worse than HashMap — except when iterating. With maps, iteration is usually not important (get() is usually where we spend the most time). TreeMap provides excellent put() and iteration times, but get() performance is poor. But why do we still need to use TreeMap? In this way, we can use it not as a Map, but as a way to create sequential lists. ** Once a TreeMap is populated, keySet() can be called to get a Set “view” of the key. We then use toArray() to produce an array containing those keys. The static method array.binarySearch () is then used to quickly find the contents of the sorted Array. ** Of course, this might only be necessary if the behavior of a HashMap is unacceptable. Because HashMap is designed for fast retrieval operations. Finally, when we use maps, the first choice should be HashMap. Only in rare cases should an alternative approach be considered
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 the codeTreeMap is significantly faster to create than the other two types (but you should try it out for yourself, as the new version is said to potentially improve ArrayMap’s performance). For this reason, and because of the aforementioned TreeMap’s excellent PUT () performance, the best strategy is to create and populate a TreeMap if you need to create a lot of maps and only need to do a lot of retrieval later. Later, when the retrieval volume increases, the important TreeMap is converted into a HashMap — using the HashMap(Map) builder.
An unsupported operation
It’s possible to convert an array to a List using static arrays.tolist ()
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 the codeAs you can see, only part of the Collection and List interfaces are actually implemented. Residual method leads to unpopular, called UnsupportedOperationException. Support for those methods may or may not be provided in the collection classes that implement those interfaces. If the call a failed to support method, can lead to an UnsupportedOperationException (action not support violation), which suggests that the emergence of a programming error. Arrays.tolist () produces a List derived from a fixed-length array. So the only operations that can be supported are those that do not change the length of the array. On the other hand, asking for a new interface to express different kinds of behavior (perhaps called a “FixedSizeList” — a fixed-length list) runs the risk of experiencing even greater complexity. As a result, when you try to use the library in the future, you will soon find yourself wondering where to start. For methods that take Collection, List, Set, or Map as arguments, their documentation should indicate which optional methods must be implemented. For example, sorting requires the implementation of set() and iterator.set () methods, but not add() and remove().
Sort and search
An array of
The Arrays class provides an overloaded sort() and binarySearch() for all Arrays of primitive data types, as well as strings and Objects.
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 the codeIn main(), random.nextbytes () populates array arguments with randomly selected bytes (there is no corresponding Random method for creating arrays of other basic data types). Once you get an array, you can see that you only need to make one method call to sort() or binarySearch(). There is another important caveat related to binarySearch() : if you do not call sort() before executing binarySearch() once, unpredictable behavior can occur, including an infinite loop. The sorting and searching of strings are similar, but when we run the program, we notice an interesting fact: the sorting follows dictionary order, which means that the uppercase letters precede the lowercase letters in the character set. As a result, all uppercase letters are at the top of the list, followed by lowercase letters — Z comes before a. Even the phone book seems to be sorted this way.
- If you want to sort an Object array, you must solve a problem. What determines the order of two objects? Unfortunately, the original Java designers did not consider this an important issue, or they would have defined it in the root class Object. One consequence of this is that ordering objects must be done externally, and the new collection library provides a standard way to do this (ideally by defining it in Object). For an Object array (and a String, which is of course a kind of Object), we can use a sort() and make it take another argument: An object that implements the Comparator interface (that is, the “Comparator” interface, part of the new collection library) and compares with its single compare() method. This method takes two objects to be compared as arguments — ** If the first argument is less than the second, return a negative integer; If equal, return zero; If the first argument is greater than the second, a positive integer is returned. ** Based on this rule, the String part of the above example could be rewritten to be truly alphabetized: by modeling it as a String, the compare() method does a “hint” test to make sure it is operating on only strings — the runtime catches any errors. When both strings are forced to lowercase, the String.compareTo() method yields the expected result. If you perform a sort() with your own Comparator, you must use that same Comparator when using binarySearch(). The Arrays class provides another sort() method that takes a single argument: an Object array with no Comparator. The sort() method must also compare two objects in the same way. By implementing the Comparable interface, it takes the “natural comparison approach” given to a class. This interface contains a single method, compareTo(), that can compare objects by returning a negative, zero, or positive number depending on whether it is less than, equal to, or greater than the argument, respectively.
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 the code- A List can be sorted and searched in the same way as an array. Static methods for sorting and searching lists are contained in the Collections class, but they have similar signatures to those in Arrays: sort(List) is used to sort a List of objects that have implemented Comparable; BinarySearch (List,Object) is used to find an Object ina List; Sort (List,Comparator) uses a “Comparator” to sort a List; 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 the codeThe usage of these methods is exactly the same as in Arrays, except that a list is used instead of an array. TreeMap must also sort its objects according to Comparable or Comparator utilities in the Collections class: Generate primitive style enumeration(enumeration) Max (Collection) for arguments, Min (Collection) generates the maximum or minimum element Max (Collection,Comparator) in the argument using the natural comparison method of objects in the Collection. NCopies (int n, Object O) returns an immutable list of length N. All handles point to o subList(List,int min,int Max) returns a new List extrapolated from the specified argument List. Think of this List as a “window” that starts at index min and ends just before Max. Note that min() and Max () work with Collection objects, not with lists. So don’t worry about sorting the Collection (as noted earlier, sort() must be done on either a List or an array before performing a binarySearch().)
1. Make Collection or Map unmodifiable
In general, it is more advantageous to create a “read only” version of a Collection or Map. The Collections class allows us to do this by passing the original container into a method and having it return a read-only version. There are four variations of this method, one for Collection (if you don’t want to treat the Collection as a more special type), List, Set, and 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 the codeIn each case, the container must be populated with valid data before it can be officially made read-only. Once the load is successful, the best practice is to replace the existing handle with the handle generated by the “unmodifiable” call. Doing so will help you avoid making it unmodifiable and accidentally changing the content. On the other hand, the tool also allows us to keep containers that can be modified private in a class and return a read-only handle to that container from a method call. This way, although we can modify it in the class, everyone else can only read it. Call “no change” for certain types of method will not result in a compile-time checks, but in the event of any changes, calls to modify specific container method will produce an UnsupportedOperationException exceptions.
2. Synchronization of Collection or Map
Just note here that the Collections class provides a way to automatically synchronize the entire container. Its syntax is similar to that of the “immutable” method:
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 the codeconclusion
(1) An array contains a digital index of an object. It holds objects of a known type, so when you look up an object, you don’t have to sculpt the results. Arrays can be multidimensional and can hold basic data types. But once it’s created, urine and feces can’t change. (2) Vectors also contain numeric indexes of objects — think of arrays and vectors as randomly accessed collections. As we add more elements, the Vector automatically changes its size. But a Vector can only hold handles to objects, so it cannot contain primitive data types; And when an object handle is removed from the collection, the result must be molded. A Hashtable, a type of Dictionary, is a way of associating objects (rather than numbers) with other objects. Hash tables also support random access to objects; in fact, their entire design emphasizes the “high speed” of access. A Stack is a LIFO queue. For a Hashtable, anything can be put into it and retrieved very quickly. With Enumeration, a sequence can be traversed and a specific action taken on each element in it. That’s a powerful enough tool. But hashTables have no concept of order. Vectors and arrays provide a linear order, but inserting an element into the middle of either of them is usually very costly. In addition, queues, unpacking queues, priority queues, and trees all involve “ordering” elements — not just putting them in so that they can later be found or moved in linear order.
Iii. Comparison and summary of each set class
Set: Objects in a Set are not arranged in any particular way, operate on data by index, and cannot have a List of duplicate elements: Objects in a sequence are stored in a linear fashion, operate on data by index, and can have a Map of duplicate elements: Each mapping item is a name-value pair. The name can not be repeated, but the value can be repeated. Each name corresponds to a unique value
The Iterator Iterator
Iterators are the standard mechanism for accessing each element in a collection by retrieving all objects in sequence. Iterator: The iterator() method of the Collection interface returns an iterator iterator it=test.iterator(); // Convert the test collection object to an iterator.
HasNext (); hasNext(); hasNext(); hasNext(); hasNext(); hasNext(); hasNext(); hasNext(); hasNext()
public interface Iterator {
boolean hasNext();
Object next();
void remove(); // Optional
}
Copy the codeThe next() method must be called once when the remove() method is called. The remove() method actually removes the last returned element.
List common methods
Void add(int index, Object element) : Void add(int index, Object element) : Object get(int index) : int indexOf(Object Element) : Int lastIndexOf(Element) : find the last element in the List. Object remove(int index) : ListIterator ListIterator (int startIndex) ListIterator (int startIndex) StartIndex List subList(int fromIndex, int toIndex) : ListIterator subList(int fromIndex, int toIndex) Return a sublist List containing the element before fromIndex to toIndex
ArrayList
Think of it as an array that grows automatically. Returns an array using toArray() of ArrayList. Arrays.aslist () returns a list. Iterators give us a universal way to access elements in a collection. ArrayList can automatically expand the capacity arrayList. ensureCapacity(int minCapacity) first gets the length oldCapacity of the current elementData attribute. Then, the capacity expansion is determined by determining which parameter is larger than oldCapacity or minCapacity. If minCapacity is larger than oldCapacity, the capacity expansion is performed on the current List. ** The capacity expansion policy is as follows: ** Use the larger value between (oldCapacity * 3)/2 + 1 and minCapacity. If minCapacity is not greater than oldCapacity, the data will not be expanded.
LinkedList
LinkedList is implemented using a two-way circular LinkedList. We can use LinkedList to implement stacks, queues, and double-ended queues. It has methods addFirst(), addLast(), getFirst(), getLast(), removeFirst(), removeLast(), etc.
ArrayList and LinkedList comparison
1.ArrayList is a data structure based on dynamic array, while LinkedList is a data structure based on LinkedList. 2. ArrayList feels superior to LinkedList for random access to GET and set because LinkedList moves the pointer. 3. For add and remove operations, LinedList has an advantage because ArrayList moves 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 the codeRecommendation:
for( Iterator<ComType> iter = ComList.iterator(); iter.hasNext();) { ComType com = iter.next();if ( !com.getName().contains("abc")){
iter.remove(com); }
Copy the codeAdding elements to an LST without limit is bound to cause the LST to consume too much memory
Map common methods
Common methods:
Object PUT (Object key,Object value) : Stores a key-value pair. Object Remove (Object key) : Void putAll(Map Mapping) : Void putAll(Map mapping) : Void clear() : Void putAll(Map mapping) : Void get(Object key) : Boolean containsKey(Object key) : Boolean containsValue(Object value): Specifies whether a value (value) exists in the Map. Public Set keySet() : Public Collection Values (); public Set entrySet(); public Set entrySet(); public Set entrySet(); Returns an element Set that implements the Map.Entry interface
HashMap
Map is mainly used to store key value pairs, and values are obtained based on keys. Therefore, duplicate keys are not allowed, but duplicate values are allowed. A HashMap is one of the most commonly used maps that stores data based on the HashCode value of the key, which can be retrieved directly based on the key, with fast access speed. A HashMap allows a Null key for at most one record; Multiple records are allowed to be Null. HashMap does not support thread synchronization, meaning that multiple threads can write a HashMap at any one time. Data inconsistency may result. If synchronization is required, the Collections synchronizedMap method can be used to make HashMap synchronous, or ConcurrentHashMap can be used to use HashMap, Both equals() and hashCode() are overridden when an object is treated as a key
LinkedHashMap compared to HashMap and TreeMap
A Hashtable is similar to a HashMap in that it inherits from the Dictionary class, except that it does not allow the record to have empty keys or values. It supports thread synchronization, meaning that only one thread can write a Hashtable at any one time, thus making it slow to write a Hashtable. A Hashmap is one of the most commonly used maps. It stores data according to the HashCode value of the key. It can obtain its value directly according to the key, with fast access speed, traversal, and completely random order of obtaining data. The LinkedHashMap holds the insertion order of the records, and when Iterator traverses the LinkedHashMap, the records obtained first must be inserted first. It can also be constructed with parameters, sorted by the number of applications. It is slower to traverse than a HashMap, except in cases where HashMap has a large volume and less actual data, it may be slower to traverse than LinkedHashMap, because the traversal speed of LinkedHashMap is only related to the actual data, not the capacity. The traversal speed of a HashMap is related to its capacity. TreeMap implements the SortMap interface, which sorts the records it holds by key. By default, the keys are sorted in ascending order. You can also specify a comparator for sorting. The one we use most is a HashMap, which is the best way to insert, delete, and locate elements in a Map, where the key-value pairs stored are randomly retrieved. TreeMap pulls out the sorted key-value pairs. But TreeMap is better if you want to traverse the keys in natural or custom order. LinkedHashMap is a subclass of HashMap. If you want the output order to be the same as the input order, you can use LinkedHashMap. It can also be read in order, as in connection pooling.
The use of the Set
Add restriction to add(), equals(), and hashCode() methods HashSet and TreeSet are implementations of Set Set — HashSet LinkedHashSet SortedSet — TreeSet
HashSet
Public Boolean Contains (Object o) : Returns true if the set contains the specified element. Iterator () returns the Iterator of the elements in the set. Public Object[] toArray() : ToArray (Object[] a) : Returns an array containing all elements of a set. The runtime type of the returned array is the specified runtime type of the array. Public Boolean add(Object o) : Public Boolean removeAll(Collection C) : public Boolean removeAll(Collection C) : Public Boolean containsAll(Collection c) : returns true if the set containsAll elements of the specified Collection. This method returns true if you specify that the set is also a set, only a subset of the current set
Implement HashSet interface, rely on HashMap to implement. We should define hashCode() and equals() for each object we want to store in the hash table. Call HashCode to get a HashCode — equal equals(); equal equals()
TreeSet
TreeSet is implemented by TreeMap. The TreeSet is an ordered set. The elements in a TreeSet are arranged in ascending order. The default is natural order.
Compare HashSet versus TreeSet versus LinkedHashSet
TreeSet is the only implementation class of SortedSet interface. TreeSet can ensure that set elements are in sorted state. TreeSet supports two sorting modes, natural sorting and custom sorting. Natural sorting is the default sorting mode. Objects of the same class should be added to TreeSet. TreeSet determines that two objects are not equal by returning false through equals or by comparing them with CompareTo, which does not return 0. Then arrange the elements in ascending order. Int compare(To1,To2) {compare(To1,To2) {compare(To1,To2) But it also uses linked lists to maintain the order of elements. This makes the elements look like they are stored in insertion order, that is, when traversing the collection, the LinkedHashSet will access the elements of the collection in the order they were added. LinkedHashSet performs better than HashSet when iteratively accessing all elements in a Set, but performs slightly worse than HashSet when inserted.
References:
- Ideas for Java Programming
- https://blog.csdn.net/u012124438/article/details/76698331
- http://www.cnblogs.com/xiaoshitoutest/p/6963798.html
If there are any improper articles, please correct them. You can also pay attention to my wechat public number: Learn Java well and get high quality resources.