A collection and array comparison
Set structure inheritance diagram
Collection is divided into two categories: one is a single way to store elements, the superparent interface is java.util.collection; One is to store elements as key-value pairs, and the superparent interface is java.util.map. Collection and Map are the root interfaces of the Collection framework.
Inheritance of collection structures requires proficiency. Be aware of which are interfaces and which are implementation classes.
Order: the order in which the elements are stored and the order in which they are taken out; Unordered: indicates that the order is stored in, but not necessarily taken out. And there are no subscripts. Repeatable: allows the storage of duplicate elements; Non-repeatable: Duplicate elements are not allowed. Even if I put a 1 in, I can't store another 1.Copy the codeIii. Collection interface
The Collection interface is the parent of the List and Set interfaces. The Collection interface defines methods for adding, deleting, modifying, and querying collections. The List and Set interfaces inherit these methods.
List interface and its implementation class
A List is an ordered and repeatable Collection, and using this interface you can precisely control where each element is inserted. Users can access elements in a List using an index (the position of an element in a List, similar to an array subscript). Common classes that implement the List interface are LinkedList, ArrayList, and Vector.
Special methods in List:
1. The ArrayList class
The bottom layer is the Object array, so the ArrayList collection is efficient to query, but inefficient to add and delete. Q: Why is array retrieval efficient and add and delete inefficient? A: Retrieval efficiency is high because first, Java arrays store each element of the same type, that is, each element occupies the same amount of space. Second, the memory address of each element stored in a Java array is continuous; As the memory address of the entire array object, we can see that we know the memory address of the first element. Fourth: array elements are subscripts, subscripts can be calculated to find the element and the offset of the first element. Adding and deleting is inefficient because adding an element to a subscript position in an array requires moving the element after that subscript one bit further, as does deleting. ArrayList automatic capacity expansion mechanism: The initial capacity is 10 and the capacity is 1.5 times of the original capacity after expansion.
The ArrayList class has three constructors:
Arraylist set test:
Public static void main(String[] args) {ArrayList<String> list = new ArrayList<>(); // Add element for (int I =97; i<105; i++) { list.add(String.valueOf((char)i)); } system.out. println(" the contents of the list array are "+ list); System.out.println("list array number of elements: "+ list.size()); list.set(0,"haha"); System.out.println("list array: "+ list); Println (" List array contains "A" : "+ list. Contains ("a")); System.out.println(" + list.get(2)); list.remove("c"); System.out.println("list array with 'c' removed: "+ list); For (String s: list) {system.out.printf ("%s\t",s); }}Copy the codeResults:
The content of the list array is [A, B, C, D, E, F, G, H] The number of elements in the list array is as follows: 8 The modified content of the list array is as follows: [haha, B, C, D, E, F, g, H] Whether the list array contains a: The element with subscript 2 in the false list array is: c The content of the list array after removing "C" is: [haha, b, D, E, f, g, h] haha b d e f g hCopy the code2, LinkedList class
The bottom layer uses a bidirectional linked list structure, which has the advantage of efficient insertion and deletion of elements, but the speed of random access to elements is slow, which is the opposite of ArrayList. If your program needs to repeatedly insert and delete collections, choose the LinkedList class.
The LinkedList class has two constructors:
The LinkedList class also implements the Deque and Queue interfaces, implementing the methods specified in these interfaces for handling elements at the head and tail. You can use LinkedList to implement stacks, queues, and double-ended queues. It has methods addFirst(), addLast(), getFirst(), getLast(), removeFirst(), removeLast(), etc.
LinkedList collection test:
Public static void main(String[] args) {ArrayList<String> list = new ArrayList<>(); // Add element for (int I =97; i<105; i++) { list.add(String.valueOf((char)i)); } system.out. println(" the contents of the list array are "+ list); // create LinkedList instance LinkedList<String> link = new LinkedList<>(list); System.out.println("link "+ link); link.addFirst("first"); link.addLast("last"); System.out.println("link "+ link); System.out.println(" + link.getFirst() "); }Copy the codeResults:
[a, b, c, D, e, f, g, h] [A, b, c, D, e, f, g, h] [a, b, c, d, e, f, g, h] [a, b, c, d, e, f, g, h] [a, b, c, d, e, f, g, h] The first element of the last] link is: firstCopy the code3, Vector class
: The underlying data structure is array, which is fast to query, slow to add and delete, thread safe, low efficiency, can store repeated elements, not recommended.
Iterator interface (Iterator)
The Iterator interface is an Iterator that iterates over a Collection. Using this interface, you can access the elements in a Collection and iterate over the Collection elements. The Iterator interface has three methods:
Iterators start with the first object and use Next() to point to the Next object. If the collection structure is changed in a way other than the remove() method during iteration of a collection element, the iterator must be reacquired. And remove() can only be used after the Next() method is called, at most once after each execution of Next().
Iterator tests:
Public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>(); // Add element for (int I =1; i<9; i++) { list.add(i); Iterator<Integer> it = list.iterator(); Iterator<Integer> it = list.iterator(); // Iterator iterates through the collection while (it.hasnext ()) {// Determine if there are elements int x = it.next(); // Get the element System.out.println(x); If (x == 5) // remove element it.remove(); } // Convert to Object array [] a = list.toarray (); System.out.printf(" Delete after: "); for (int i=0; i<a.length; i++) { System.out.printf("%s\t",a[i]); }}Copy the codeResults:
1 2 3 4 5 6 7 8 After deleting: 1 2 3 4 6 7 8Copy the codeSet interface and its implementation class
Unordered collections, where duplicate elements are not allowed; Null elements are allowed. Stricter restrictions are placed on the add(), equals(), and hashCode() methods.
(Because both HashSet and TreeSet collections are underlying maps, HashSet is underlying HashMap, and TreeSet is underlying TreeMap. So learn Map, Set Set is very easy to understand, so here is a brief introduction to the Set interface and its implementation class, you can first go to learn section 7 Map interface.
1, HashSet class
Hash table is used to implement the underlying data structure of HashSet. The elements are unordered and unique, which is not thread safe and efficient. Null elements can be stored.
Specific comparison process to achieve uniqueness: Storing elements first uses the hash() algorithm function to generate a hashCode hash value of type int, and then compares the hashCode values of the stored elements. If hashCode is not equal, then the two stored objects must not be equal. In this case, store the element object at the current new hashCode value. If hashCode is equal, the objects storing the elements are not necessarily equal. In this case, equals() is called to determine whether the contents of the two objects are equal. If the contents of the comparison are not equal, then it is different objects, and it is stored. In this case, the hash algorithm for resolving address conflicts is adopted. The current hashCode value is like a new linked list, and the different objects are stored after the same hashCode value, so as to ensure the uniqueness of elements.
HashSet class test:
public static void main(String[] args) { Set<String> strs = new HashSet<>(); strs.add("aa"); strs.add("bb"); strs.add("cc"); strs.add("dd"); strs.add("aa"); Iterator<String> it = strs.iterator(); while (it.hasNext()) { String s = it.next(); System.out.println(s); }}Copy the codeResults:
aa
bb
cc
dd
Copy the code2, the TreeSet class
The bottom layer of the collection is TreeMAp, and the bottom layer of TreeMAp is binary tree structure. Unlike the HashSet class, the TreeSet class is not hashed but ordered.
The element is unique and already sorted; Uniqueness also requires overriding the hashCode and equals() methods, and the binary tree structure guarantees ordering of elements. CompareTo (); compareTo(); compareTo(); compareTo(); The Comparator row needs to pass in a Comparator object that implements the Comparator interface at TreeSet initialization, or override the compare() method by using an anonymous inner class to create a new Comparator object.
7. Map interface
1. There is no inheritance relationship between Map collection and Colltection collection. 2. Map sets store elements as key-value pairs of keys and values. Key and Value are memory addresses that store Java objects. Key plays the leading role and Value is an accessory of Key. Disorder can not be repeated.
Common methods in Map:
Map common methods test:
Public static void main(String[] args) {// Create a Map collection object Map<Integer,String> Map = new HashMap<>(); // Add the key-value pair map.put(1," China ") to the collection; Map. The put (2, "us"); Map. Put (3," Russia "); Map. The put (4, "British"); Println (map.get(1)); System.out.println(" containsKey '4' : "+ map.containskey (4)); Println (" does it contain value "China" : "+ map.containsValue(" China ")); System.out.println(" Is the set empty: "+ map.isempty ()); Map.remove (2); // Delete key pairs from map.remove(2); System.out.println(" count of set elements: "+ map.size()); Set< map.entry <Integer,String>> Set = map.entrySet(); System.out.println("======================================================"); For (map.entry <Integer,String> Entry: set) {system.out.println ("key: "+ entry.getKey() +" value: " + entry.getValue()); }}Copy the codeResults:
China contains key "4" : true contains value China: true set is empty: false Number of set elements: 3 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = key: value: 1 China key: 3 value: Russia key: value: the UKCopy the code1. Four ways to traverse a Map collection
public static void main(String[] args) { Map<String, String> map= new HashMap<>(); Map. Put (" guan Yu ", "yun Chang "); Map. Put (" zhang Fei ", "Yi De "); Map. Put (" zhao yun ", "Zi long "); Map. Put (" ma Chao ", "Meng Qi "); Map. Put (" huang Zhong ", "han Sheng "); For (String s: map.keyset ()){system.out.println ("key: map.keyset ()){system.out.println ("key: map.keyset ()); "+s+" value : "+map.get(s)); } System.out.println("===================================="); For (String s1: map.keyset ()){// For (String s1: map.keyset ()){system.out.println (" key: "+s1); } for(String s2:map.values()){system.out.println (" value: "+s2); } System.out.println("===================================="); Map.entry <String,String> for loop through the output key key and value value Set< map.entry <String,String>> Set = map.entryset (); For (map.entry <String, String> Entry: set){system.out.println (" key key: "+entry.getKey()+" value value: "+entry.getValue()); } System.out.println("===================================="); // The fourth type of Iterator iterates and gets map. Entry<String, String>, GetKey () and getValue() 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()+" value: "+entry.getValue()); } System.out.println("===================================="); }Copy the code2, HashMap data structure
To master HashMap collections, you need to be familiar with the data structure of hash tables. Because the underlying HashMap collection is a hash table/hash table data structure.
A hash table is a combination of an array and a one-way linked list. So hash tables are very efficient in querying and adding and deleting data.
The underlying HashMap is actually a one-dimensional array containing a Node (hashmap. Node, which contains hash values, key-value pairs, and the memory address of the next Node). The hash value is the result of the key’s hashCode() method, which, through the hash function, can be converted toThe index of the array.
Map. put(k,v) implementation principle: ① Encapsulate key pair k,v into Node object; (2) The underlying method will call k’s hashCode() method to get the hash value; ③ Convert the hash value to the index of the array using the hash function. If the subscript position does not have any elements, add Node to the subscript position. If there is a list at the subscript position, it compares k with k of each node on the list using equals() (since the Map is non-repeatable). If there are no duplicates, new nodes are appended to the end of the list; otherwise, nodes with the same k value are overwritten.
Map.get (k) = map.get(k) = map.get(k) If there are no elements on the index, return null. If there are linked lists, compare k with k on each node using equals(). If the result is false, return null. If equals returns true for a node, return the value of that node.
Q: Why is the efficiency of random addition and deletion of hash tables high? A: The addition and deletion are done on the linked list, and the query does not need to be scanned all, only partial scan.
The important point here is that the hashCode() and equals() methods called above need to be overridden! Equals () overridden reason: Equals () compares the memory addresses of two objects by default, but we need to compare the contents of k. HashCode conclusion: Elements placed in the key part of the HashMap() collection, and elements placed in the HashSet collection need to override both hashCode and equals methods.
Rewriting equals() and hashCode() tests: The results of the code run before and after rewriting are different, you can use this code to test, and uncomment the previous section and the comment section.
public class HashMapTest01 {
public static void main(String[] args) {
Student s1 = new Student("Jake");
Student s2 = new Student("Jake");
System.out.println(s1.equals(s2));
System.out.println(s1.hashCode() == s2.hashCode());
Set<Student> students = new HashSet<>();
students.add(s1);
students.add(s2);
System.out.println(students.size());
}
}
class Student {
//@Override
//public boolean equals(Object o) {
// if (this == o) return true;
// if (o == null || getClass() != o.getClass()) return false;
// Student student = (Student) o;
// return Objects.equals(name, student.name);
//}
//
//@Override
//public int hashCode() {
// return Objects.hash(name);
//}
private String name;
public Student(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
Copy the code3, TreeMap classes
TreeMap class is a concrete implementation of Map interface. The underlying binary tree data structure supports the ordered storage of elements, which can be automatically sorted according to the size order of elements. All elements in the TreeMap class must implement the Comparable interface, similar to the TreeSet class.
TreeSet automatic sorting test:
public static void main(String[] args) { TreeSet<String> ts = new TreeSet<>(); ts.add("ss"); ts.add("abf"); ts.add("g"); ts.add("f"); ts.add("abcd"); ts.add("abc"); Iterator<String> it = ts.iterator(); while (it.hasNext()) { System.out.println(it.next()); }}Copy the codeResults (in ascending lexicographical order) :
abc
abcd
abf
f
h
ss
Copy the codeTreeMap does not automatically sort custom types. Rules for comparing custom objects need to be specified. If you do not specify (who is bigger and who is smaller is not specified), the TreeMap class does not know how to sort elements and will report an error, such as this code:
public class TreeSetTest02 { public static void main(String[] args) { Student s1 = new Student("Ana",18); Student s2 = new Student("Bob",25); Student s3 = new Student("Stark",21); Student s4 = new Student("Lip",18); TreeSet<Student> students = new TreeSet<>(); students.add(s1); students.add(s2); students.add(s3); students.add(s4); Iterator<Student> it = students.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } } class Student { private String name; private int age; public Student(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; }}Copy the codeThe following exceptions will be reported:
java.lang.ClassCastException: class test.Student cannot be cast to class java.lang.Comparable
Copy the codeThis is where we need to implement the Comparable interface for our custom types and rewrite the compareTo() method, where we need to write the logic (comparison rules) for comparisons. The compareTo method returns an int: 0 means the same, value overwrites; Returns >0, looks in the right subtree; Returns <0, looks in the left subtree. (Learn binary tree data structure)
The comparison rule is self-imposed, first comparing the size of the age, and if the age is the same, comparing the size of the string.
public class TreeSetTest02 { public static void main(String[] args) { Student s1 = new Student("Ana",18); Student s2 = new Student("Bob",25); Student s3 = new Student("Stark",21); Student s4 = new Student("Lip",18); TreeSet<Student> students = new TreeSet<>(); students.add(s1); students.add(s2); students.add(s3); students.add(s4); Iterator<Student> it = students.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } } class Student implements Comparable<Student>{ private String name; private int age; public Student(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; } @override // compareTO returns an int; // If the age is the same, the size of the string is compared; public int compareTo(Student o) { if (this.age ! = o.age) return this.age - o.age; Else // age same return this.name.compareTo(O.name); // Instead of calling the compareTo method of the class, the compareTo method of the string is called}}Copy the codeResults:
Student{name='Ana', age=18}
Student{name='Lip', age=18}
Student{name='Stark', age=21}
Student{name='Bob', age=25}
Copy the codeThe second way elements in a TreeSet collection can be sorted is by using the comparator method. Write a separate comparator that implements the java.util.Comparator interface. And pass in the comparator when you create the TreeSet collection.
public class TreeSetTest02 { public static void main(String[] args) { Student s1 = new Student("Ana",18); Student s2 = new Student("Bob",25); Student s3 = new Student("Stark",21); Student s4 = new Student("Lip",18); TreeSet<Student> Students = new TreeSet<>(new StudentComparator())); TreeSet<Student> Students = new StudentComparator(); students.add(s1); students.add(s2); students.add(s3); students.add(s4); Iterator<Student> it = students.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } } class Student { public String name; public int age; public Student(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; Class StudentComparator implements the java.util.Comparator interface class StudentComparator implements the StudentComparator <Student> {@override public int compare(Student o1, Student o2) { if (o1.age ! = o2.age) return o1.age - o2.age; else return o1.name.compareTo(o2.name); }}Copy the codeYou can also use anonymous inner classes.
public class TreeSetTest02 { public static void main(String[] args) { Student s1 = new Student("Ana",18); Student s2 = new Student("Bob",25); Student s3 = new Student("Stark",21); Student s4 = new Student("Lip",18); // When creating a TreeSet collection, TreeSet<Student> Students = new TreeSet<>(new Comparator<Student>() {@override public int compare(Student o1, Student o2) { if (o1.age ! = o2.age) return o1.age - o2.age; else return o1.name.compareTo(o2.name); }}); students.add(s1); students.add(s2); students.add(s3); students.add(s4); Iterator<Student> it = students.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } } class Student { public String name; public int age; public Student(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; }}Copy the codeConclusion: There are two ways to sort elements placed in the key part of a TreeSet or TreeMap set. First, elements placed in the set implement the java.lang. Comparable interface. Second: Pass a comparator object to a TreeSet or TreeMap collection when it is constructed. (Used when comparison rules change frequently)