Basic concepts of Java collection classes
Sometimes we need to store more than one piece of data in one place. In general, arrays are a good choice if we know exactly how many objects we want to store in advance. Once this array length is specified during array initialization. The array length is immutable, and Java collection classes are a good design if we want to store data that can grow dynamically.
Collection classes are responsible for holding other data, so they are also commonly referred to as container classes. All of the collection classes are in the java.util package.
- Collection
A Set of elements that obey a certain rule 1.1) List must maintain a certain order of elements 1.2) Set cannot have duplicate elements 1.3) Queue Maintains a first-in, first-out order 2) Map
A key-value pair object that consists of pairs
The difference between a Collection and a Map is the number of elements held at each location in the container
(1) A Collection can only hold one element per location, and (2) a Map holds “key-value pairs”, just like a small database. We can find the value by the key
Second, Java collection class architecture hierarchy
1.Iterface Iterable
Iterator interface, which is the parent interface of the Collection class. Objects that implement this Iterable interface allow foreach traversal, that is, all Collection objects are “foreach traversable.” The Iterable interface has only one method: iterator (). It returns a generic iterator representing the current collection object for subsequent traversal operations.
1.1 the Collection
Collection is the most basic Collection interface. A Collection represents a Collection of objects called the elements of a Collection. Collection is an interface that provides a specification definition and cannot be instantiated
1) Set
A Set is like a bucket in that there is no discernible order between objects placed in a Set. Set inherits from the Collection interface and cannot contain repeating elements.
Set determines that two objects are the same not using the “==” operator, but based on equals. That is, when we add a new element, Ser will accept the new element if equals returns false, and if not, Ser will reject it.
Because of this restriction on sets, two things should be considered when using sets: 1) The implementation class of the elements in the Set implements a valid equals (Object) method. 2) The constructor of the Set, passed in the Collection argument, cannot contain duplicate elements
1.1) HashSet
HastSet is a typical implementation of the Set interface. HashSet uses the HASH algorithm to store elements in a collection, so it has good access and lookup performance. When storing an element into a HashSet collection, the HashSet calls the object’s hashCode () method to get the object’s hashCode value, which is then used to determine where the object is stored in the HashSet.
1.1.1) LinkedHashSet
The LinkedHashSet collection also determines where elements are stored based on their hashCode value, but unlike a HashSet, it also uses a linked list to maintain the order of elements so that they appear to be stored in the order they were inserted.
When traversing the LinkedHashSet elements, the LinkedHashSet will access the elements in the order they were added.
LinkedHashSet needs to maintain the insertion order of elements, so it has slightly lower performance than HashSet, but good performance when iteratively accessing all elements of a Set.
1.2) SortedSet
This interface is mainly used for sorting operations, that is, subclasses that implement this interface are subclasses of sorting
1.2.1) TreeSet
TreeSet is an implementation class of the Sorted interface that ensures that the collection elements are in Sorted state
1.3) enumsets
EnumSet is a collection class designed specifically for American TV series. All elements in an EnumSet must be enumerations of the specified tragedy type, either explicitly or implicitly specified when creating the EnumSet. The set elements of EnumSet are also ordered.
2) List
The List set represents an ordered, repeatable set of elements in which each element has a corresponding sequential index. The List collection allows the addition of duplicate elements because it can access the collection elements by index. By default, the List collection sets the index of the elements in the order they were added
2.1) ArrayList
ArrayList is an array-based implementation of the List class that encapsulates a dynamically growing, reallocatable Object[] array.
2.2) Vector
Vector and ArrayList are almost identical in usage, but since Vector is an ancient collection, it provides methods with long names. Vector was later changed to implement the List interface, which was incorporated into the collection framework
2.2.1) Stack
Stack is a subclass of Vector that simulates the Stack data structure
2.3) LinkedList
Implement the List, a Deque. Implement the List interface, he can carry out queue operations, that is, according to the index to randomly access the elements in the collection. He also implements the Deque interface, which allows the LinkedList to be used as a two-ended queue. Naturally, it can also be used as a stack.
1.2 the Map
A Map is used to store “mapping” data. Therefore, a Map contains two sets of values. One set of values is used to store keys in the Map and the other set of values is used to store values in the Map. Both key and value can be data of any reference type. Map keys are not allowed to be duplicated. The equals method always returns false for any two keys of the same Map object.
The key sets in these Map implementation classes and subinterfaces are stored exactly the same as the Set sets.
The value sets in these Map implementation classes and subinterfaces are stored very similarly to lists (that is, values can be repeated and looked up by index)
1) a HashMap
Just as a HashSet does not guarantee the order of elements, a HashMap does not guarantee the order of key-value pairs. And similar to a HashSet, the criteria for determining whether two keys are equal is true: two keys are compared using equals ().
The hashCode values of the two keys must also be equal.
1.1) LinkedHashMap
LinkedHashMap also uses a bidirectional linked list to maintain the order of key-value pairs, consistent with the insertion order of key-value pairs (note that TreeMap sorts and partitions all key-values)
2) the HashTable
2.1) the properties
3) sortedMap
Just as the Ser interface derives the SortedSet subinterface and the SortedSet interface has a TreeSet implementation class, the Map interface also derives a SortedMap implementation class
3.1) TreeMap
TreeMap is a red-black tree data structure. Each key-value pair is a node in the red-black tree. When TreeMap stores key-value pairs (nodes), you need to sort them by key pair and order. TreeMap can include guarantees that all key-value pairs are in an ordered state. TreeMap also has two kinds of sorting: natural sorting and custom sorting
3.Java collection class Demo
1.Set
HashSet
import java.util.*
// Class A’s equals() method always returns true, but does not override its hashCode() method. There is no guarantee that the current object is unique to the HashSet
class A { public bollean equals(Object obj) { return true;
Class B’s hashCode() method always returns true, but does not override its equals() method. Class B {public bollean hashCode(Object obj) {return 1;
Class C {public int hashCode() {return 2; } public boolean equals(Object obj) { return true; }}
public class HashSetTest { public static void main(String[] args) { HashSet books=new HashSet();
// Add two A objects, two B objects, and two C objects to books.add(new A()); books.add(new A()); books.add(new B()); books.add(new B()); books.add(new C()); books.add(new C()); System.out.println(books);Copy the code}}
The results of
[B@1, B@1, C@2, A@3bc257, A@785d65]
As you can see, if two objects return true through equals (), but their hashCode methods return different hashCode values, this will cause the HashSet to store the two objects in different places in the Hash table so that the objects can be added successfully. This is a little bit different from the Set rule. So, we need to make it clear that equals () determines whether we can add a HashSet, and hashCode () determines where we can store it, both of which must be met to allow a new element to be added to the HashSet.
Note, however, that if two objects have the same hashCode, but their equals returns different values, the HashSet will store multiple objects in a chain structure at that location. A HashSet accesses a collection element based on its HashCode value, which leads to performance degradation.
So if we need to store objects of a class in a HashSet, we should override the equasl () and hashCode () methods of that class to ensure that the two objects return the same value from hashCode () when they return true via equals ().
LinkedHashSet
import java.util.*; public class LinkedHashSetTest { public static void main(String[] args) { LinkedHashSet books=new LinkedHashSet(); books.add(‘Java1’); books.add(‘Java2’); System.out.println(books); // delete Java1 books.remove(“Java1”); // add Java1 books.add(“Java1”); System.out.println(books); }}
The output
[Java1, Java2] [Java1, Java2]
The element order is always the same as the order of addition, and remember that LinkedHashSetTest is a subclass of HashSet because it does not allow collection elements to be repeated
TreeSet
import java.util.*;
public class Test { public static void main(String[] args) { TreeSet nums = new TreeSet(); // Add four Integer objects nums.add(5) to TreeSet; nums.add(2); nums.add(10); nums.add(-9);
System.out.println(nums); [-9, 2, 5, 10] system.out.println (nums.first()); System.out.println(nums.last())); HeadSet (4); // headSet(4); // headSet(4) is returned. [-9, 2] // Returns a subset greater than 5, including 5 system.out.println (nums.tailset (5)) if the Set contains 5; [5, 10] // Returns subsets greater than or equal to -3 and less than 4. System.out.println(nums.subSet(-3 , 4)); [2]}Copy the code}
Unlike a HashSet, which uses a hash algorithm to determine where elements are stored, TreeSet uses a red-black tree data structure to store collection elements. TreeSet supports two sorting methods: natural sorting and custom sorting
1. Prioritize naturally
The TreeSet calls the compareTo (Object obj) method of the collection elements to compare the small relationships between the elements, and then sorts the collection elements in ascending order, that is, in natural order. If you attempt to add an Object to the TreeSet, the class of that Object must implement the Comparable interface. Otherwise, the program will throw an exception.
When an Object is added to a TreeSet collection, the TreeSet calls the Object’s compareTo (Object obj) method to compare its size with other objects in the container, and then finds its location based on the red-black tree structure. If two objects are equal using the compareTo (Object obj) method, the new Object cannot be added to the TreeSet collection (remember that sets do not allow duplication).
Note: If you want to override the equals () method of an Object into a TreeSet, you should ensure that the equals () method has the same result as compareTo (Object obj). If two objects return true through equals (), These two objects should also be equal by compareTo (Object obj)
For and Set, equals() is defined as the uniqueness criterion. For the specific implementation, HashSet and TreeSet have their own unique uniqueness criterion, which can only be judged as unique if both of them are satisfied
2. Custom sorting
TreeSet’s natural ordering is that TreeSet sorts collection elements in ascending order based on their size. If we need to implement custom sorting, we do it through the Comparator interface. This interface contains an int compare (to1, to2) method that allows the user to compare sizes.
import java.util.*;
class M { int age; public M(int age) { this.age = age; } public String toString() { return “M[age:” + age + “]”; }}
public class Test { public static void main(String[] args) { TreeSet ts = new TreeSet(new Comparator() { Public int compare(Object o1, Object o2) {M m1 = (M)o1; M m2 = (M)o2; return m1.age > m2.age ? -1 : m1.age < m2.age ? 1:0; }}); ts.add(new M(5)); ts.add(new M(-3)); ts.add(new M(9)); System.out.println(ts); }}
EnumSet
import java.util.*;
enum Season { SPRING,SUMMER,FALL,WINTER } public class EnumSetTest { public static void main(String[] args) { EnumSet es1 = enumset.allof (season.class); / / output [SPRING, SUMMER, FALL, WINTER] System. Out. The println (es1);
// Create an empty collection of EnumSet whose elements are enumerated values of the Season class. EnumSet es2 = EnumSet.noneOf(Season.class); [] system.out.println (es2); // Manually add two elements es2.add(season.winter); es2.add(Season.SPRING); // Output [SPRING,WINTER] system.out.println (es2); EnumSet es3 = EnumSet. Of (season.summer, season.winter); // print [SUMMER,WINTER] system.out.println (es3); EnumSet es4 = EnumSet.range(Season.SUMMER , Season.WINTER); // print [SUMMER,FALL,WINTER] system.out.println (es4); EnumSet es5 + es4 = Season EnumSet = enumset.plementof (es4); // Output [SPRING] system.out.println (es5); }Copy the code}
The output
[SPRING, SUMMER, FALL, WINTER] [] [SPRING, WINTER] [SUMMER, WINTER] [SUMMER, FALL, WINTER] [SPRING]
So that’s a Demo of the Set class. Now how do I choose the Set class?
(1) HashSet always performs better than TreeSet (except for the most common operations such as adding and querying elements) because TreeSet requires additional red-black tree algorithms to maintain the order of collection elements. You should use TreeSet only when you need a Set that keeps sorting, otherwise you should use HashSet
(2) For normal insert and delete operations, LinkedHashSet is a bit slower than HashSet due to the overhead of maintaining the linked list. However, traversing the LinkedHashSet is faster because of the link
(3) EnumSet is the best performing of all Set implementation classes, but it can only hold the enumeration value of one enumeration class as a Set element.
(4) HashSet, TreeSet, EnumSet are “thread-unsafe”.
2.List
ArrayList
If you know how many elements an ArrayList collection needs to hold from the start, you can specify the size when you create them to reduce the number of reallocations and improve performance. ArrayList also provides the following methods to reallocate an Object[] array.
- EnsureCapacity (int minCapacity): Increments the Object[] array length of the ArrayList collection by minCapacity
- TrimToSize (): Adjusts the Object[] array length of the ArrayList collection to the current number of elements. Programs can use this method to reduce the memory footprint of ArrayList collection objects
import java.util.*;
public class Test { public static void main(String[] args) { List books = new ArrayList(); Books.add (new String(” Lightweight Java EE Enterprise Application “)); Books.add (new String(” Crazy Java notes “)); Books.add (new String(” Crazy Android handout “)); System.out.println(books);
// Insert the new String object in the second position books.add(1, new String(" Crazy Ajax notes ")); for (int i = 0; i < books.size(); i++) { System.out.println(books.get(i)); } // remove the third element book.remove (2); System.out.println(books); Println (books.indexof (new String(" Crazy Ajax handouts ")))); Books.set (1, new String("LittleHann")); System.out.println(books); Println (books.sublist (1, 2)); println(books.sublist (1, 2)); println(books.sublist (1, 2)); }Copy the code}
The output
[Lightweight Java EE enterprise application real estate, crazy Java handout, crazy Android handout] Crazy Android handout] 1 [Lightweight Java EE enterprise application practice, LittleHann, crazy Android handout]
Stack
Note the lifO nature of Stack
import java.util.*;
public class Test { public static void main(String[] args) { Stack v = new Stack(); V. ush(” Crazy Java notes “); V.ush (” Lightweight Java EE Enterprise Application Combat “); V.ush (” Crazy Android handout “);
// Output: system.out.println (v); // Output: system.out.println (v); // Access the first element, but do not pop it off the "stack", output: crazy Android handout system.out.println (v.peeek ()); // Still output: [crazy Java handout, lightweight Java EE enterprise application, crazy Android handout] system.out.println (v); // Pop out the first element, output: crazy Android handout system.out.println (v.pop()); // Output: system.out.println (v); system.out.println (v); }Copy the code}
The output
Crazy Android handout [crazy Java handout, lightweight Java EE enterprise application practice, crazy Android handout] crazy Android handout [crazy Java handout, lightweight Java EE enterprise application practice, crazy Android handout] crazy Android handout Lightweight Java EE enterprise Application practice]
LinkedList
import java.util.*;
public class Test { public static void main(String[] args) { LinkedList books = new LinkedList();
Books.offer (" Crazy Java handouts "); // Add string elements to the end of the queue (double-ended queue). // Add a string element to the top of the stack (double-ended queue) books.push(" Lightweight Java EE enterprise application combat "); // Add the string element to the head of the queue (equivalent to the top of the stack) books.offerfirst (" Crazy Android handout "); for (int i = 0; i < books.size() ; i++ ) { System.out.println(books.get(i)); System.out.println(books.peekfirst ())); System.out.println(books.peeklast ())); Println (books.pop()); system.out.println (books.pop()); // The following output will see the first element in the queue deleted system.out.println (books); // Access and delete the last element of the queue system.out.println (books.polllast ()); // The following output will see only the middle element in the queue: // Lightweight Java EE Enterprise Application Combat System.out.println(books); }Copy the code}
The output
Crazy Android handout lightweight Java EE enterprise application real estate crazy Android handout crazy Java EE enterprise application real estate Crazy Java handout [Lightweight Java EE enterprise Application practice]
Queue
import java.util.*;
public class PriorityQueueTest { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); Pq.offer (6); pq.offer(6); pq.offer(-3); pq.offer(9); pq.offer(0);
[-3, 0, 9, 6] system.out.println (pq); // Access the first element in the queue, which is the smallest element in the queue: -3 system.out.println (pq.poll()); }Copy the code}
PriorityQueue does not allow the insertion of null elements. It also needs to sort queue elements, and PriorityQueue elements can be sorted in two ways
1) Natural ordering: All objects in a PriorityQueue that uses natural order must implement the Comparable interface and be multiple instances of the same class, otherwise a ClassCastException may occur
When we create a PriorityQueue, we pass in a Comparator object that sorts all the elements in the queue
ArrayDeque
import java.util.*;
public class Test { public static void main(String[] args) { ArrayDeque stack = new ArrayDeque(); // Push the three elements into the “stack”. Stack.push (” Lightweight Java EE Enterprise Application Combat “); Stack.push (” Crazy Android handout “);
// Output: system.out.println (stack); system.out.println (stack); // Access the first element without popping it out of the "stack", output: crazy Android handout System.out.println(stack.peek()); // Still output: system.out.println (stack); system.out.println (stack); // Pop out the first element, output: crazy Android handout system.out.println (stack.pop()); // Output: system.out.println (stack); }Copy the code}
Crazy Android handout, lightweight Java EE enterprise application combat, crazy Java Handout crazy Android handout, lightweight Java EE enterprise application combat, Crazy Java handouts crazy Android handouts [Lightweight Java EE enterprise application practice, crazy Java handouts]
This is the programming scenario for the List collection class. So let’s just think about this
Java provides a List that is a “linear table interface.” ArrayList and LinkedList are two typical implementations of linear tables
Queue represents a Queue, Deque represents a double-ended Queue (that is, can be used as a Queue or stack)
Because arrays hold all their elements in a contiguous chunk of memory, they perform best when accessed randomly.
Internal linked list as the underlying implementation of the collection of insert, delete operations have a good performance
traverse
As we said earlier, the Collection interface inherits from the Iterable interface, which means that all the Collection classes we learned above are “traversable”.
The Iterable interface is also a member of the Java Collections framework. It hides the low-level details of the various Collection implementation classes and provides applications with a unified programming interface to traverse Collection elements:
- Boolean hasNext(): Whether there is a next element that has not been iterated over
- Object Next (): Returns the next element in the collection
- Void remove(): Removes the iteration element from the collection that was last returned by the next method
import java.util.*;
Public class Test {public static void main(String[] args) {// Create a Collection Collection books=new HashSet(); books.add(“1”); books.add(“2”); books.add(“3”); Iterator it=books.iterator(); while(it.hasNext()) { String book=(String)it.next(); System.out.println(book); If (book.equals(“2”)) {// Remove the element returned by the last next method from the collection it.remove(); } // Assign to the book variable, without changing the collection element itself. } System.out.println(books);
}
Copy the code}
The output
3 2 1 [3, 1]
As you can see from the code, the iterator must be attached to the Collection object. If there is an iterator, there must be a Collection object associated with it.
In addition to iterating through the elements of a Collection using the Iterator interface, it is much easier to iterate through the elements using java5’s foreach loop
Foreach implements traversal
import java.util.*;
Public class Test {public static void main(String[] args) {// Create a Collection Collection books = new HashSet(); books.add(new String(“1”)); books.add(new String(“2”)); books.add(new String(“3”));
For (Object obj: books) {String book = (String)obj; System.out.println(book); If (book. Equals (" 2 ")) {/ / the code below will cause abnormal ConcurrentModificationException / / books. Remove (book); } } System.out.println(books); }Copy the code}
The output
3 2 1 [3, 2, 1]
Map
A HashMap, HashTable
import java.util.*;
class A { int count; public A(int count) { this.count = count; } // Determine whether two objects are equal based on the value of count. public boolean equals(Object obj) { if (obj == this) return true; if (obj! =null && obj.getClass()==A.class) { A a = (A)obj; return this.count == a.count; } return false; } // Calculate the hashCode value based on count. public int hashCode() { return this.count; Public Boolean equals(Object obj) {return true;} public Boolean equals(Object obj) {return true; } } public class Test { public static void main(String[] args) { Hashtable ht = new Hashtable(); Ht. put(new A(60000), “Crazy Java handout “); Ht. Put (New A(87563), “Lightweight Java EE Enterprise Application Combat “); ht.put(new A(1232) , new B()); System.out.println(ht);
// As long as two objects return true through equals comparison, //Hashtable considers them equal values. Since there is a B object in Hashtable, // it is equal to any object by equals comparison, so the following output is true. System.out.println(ht.containsValue(" test string ")); // If the count of two A objects is equal, they return true through equals, and hashCode is equal. System.out.println(ht.containsKey(new A(87563))); Ht. remove(new A(1232)); // Select * from key (s) where key (s) = (key (s)); ht.keySet()) { System.out.print(key + "---->"); System.out.print(ht.get(key) + "\n"); }}Copy the code}
The output
{A@ea60= crazy Java handouts, A@1560b= lightweight Java EE enterprise application combat, A@4d0=B@547c9586} true true A@1560b > crazy Java handouts > lightweight Java EE enterprise application combat
If you override the equals (Object obj) and hashCode () methods of a HashMap or Hashtable, you should ensure that the two methods are consistent — when two keys are compared using equals () and return true, The return value of hashCode () for both keys should also be the same.
LinkedHashMap
import java.util.*;
public class Test { public static void main(String[] args) { LinkedHashMap scores = new LinkedHashMap(); Scores. Put (” scores “, 80); Scores. Put (“英文”, 82); Scores. Put (” scores “, 76); For (key: scores.keyset ()) {system.out.println (key + “——>” + scores. Get (key)); }}}
The output
Chinese ——>80 English ——>82 Math ——>76
properties
import java.util.; import java.io.;
public class Test { public static void main(String[] args) throws Exception { Properties props = new Properties(); // Add props. SetProperty (“username”, “yeeku”) to Properties; props.setProperty(“password” , “123456”);
// save the key-value pair from Properties to the props. Store (new FileOutputStream("a.ini"), "comment line"); Props2 = new Properties(); // Add props2.setProperty("gender", "male") to Properties; Props2. load(new FileInputStream("a.ini")); / / (2) System. The out. Println (props2); }Copy the code}
The output
{password=123456, gender=male, username=yeeku}
TreeMap
import java.util.*;
class R implements Comparable { int count; public R(int count) { this.count = count; } public String toString() { return “R[count:” + count + “]”; } // Use count to determine whether two objects are equal. public boolean equals(Object obj) { if (this == obj) return true; if (obj! =null && obj.getClass()==R.class) { R r = (R)obj; return r.count == this.count; } return false; } // Determine the size of two objects based on the count attribute value. public int compareTo(Object obj) { R r = (R)obj; return count > r.count ? 1 : count < r.count ? 1:0; } } public class TreeMapTest { public static void main(String[] args) { TreeMap tm = new TreeMap(); Tm. put(New R(3), “Lightweight Java EE Enterprise Application Combat “); Tm. put(new R(-5), “Crazy Java handout “); Tm. put(new R(9), “Crazy Android handout “);
System.out.println(tm); System.out.println(tm.firstEntry())); System.out.println(tm.lastkey ())); // Returns the minimum key of this TreeMap greater than new R(2). System.out.println(tm.higherKey(new R(2))); // Return the largest key-value pair of the TreeMap smaller than new R(2). System.out.println(tm.lowerEntry(new R(2))); // Return the child TreeMap system.out.println (tm.submap (new R(-1), new R(4))); }Copy the code}
The output
{R[count:-5]= crazy Java handout, R[count:3]= lightweight Java EE enterprise application, R[count:3] R[count:-5]= R[count: 5] R[count:-5]= R[count:9] R[count: -3]
As you can see from the code, similar to the criteria for determining whether two elements are equal in TreeSet, the criteria for determining whether two keys are equal in TreeMap is
- Both keys return 0 through the compareTo() method
- The equals () back into true
EnumMap
import java.util.*;
Enum Season (SPRING, SUMMER, FALL, WINTER} public class Test {public static void main (String [] args) {/ / create a EnumMap object, EnumMap EnumMap = new EnumMap(season.class); Enummap. put(Season.SUMMER, “SUMMER “); Enummap. put(Season. System.out.println(enumMap); }}
The output
{SPRING= SPRING, SUMMER= SUMMER}
To create an EnumMap, you must specify an enumeration class to associate the EnumMap with the specified enumeration class
Above is the Map collection class programming small demo. So let’s just think about this
(1) The efficiency of HashMap and Hashtable is roughly the same because their implementation mechanism is almost identical. But HashMap is generally a bit faster than Hashtable because Hashtable requires a second level of thread synchronization control
(2) TreeMap is usually slower than HashMap and Hashtable (especially in insert and delete key-value pairs) because TreeMap is used at the bottom