Summary of a.

1. Object storage

In the initial version of Java, the need to store multiple objects can be realized by using arrays. The characteristic of arrays is that once the length is determined after initialization, it cannot be changed, which makes it lose scalability. In addition, arrays provide fewer methods, and some common operations need to be implemented manually, which is less efficient, even though they are initialized to limit the type safety of the elements in them. Now imagine a scenario where you need to store non-repetitive, ordered data. How would that work? Array traversal? This is obviously inefficient. Further, what if we need to store key-value data? Using an array implementation is a bit of a stretch.

2. Collection framework

After java1.2, the collection framework came out of nowhere. Simply put, collections can also be thought of as containers that store references to objects dynamically, with methods that facilitate efficient access. Like other data structure libraries, the collection library separates the interface from the implementation, so when we use the collection framework, we are actually calling the implementation class for a specific interface. A generic collection framework is provided in the java.util package, which includes multiple interfaces and implementations, including the List, Set, Map, and other interfaces, as well as the implementation of ArrayList and HashMap.

3. Interface classification

There are two basic interfaces in the Collection: Collection and Map.

3.1 the Collection interface

The Collection interface is the parent of the List, Set, and Queue interfaces and inherits from the Iterable interface. There are some basic methods defined in this interface that can operate on sets as well as lists and queues. There is no direct implementation of this interface, but implementations of its specific subinterfaces are provided.

  • Set interface: This interface extends from the Collection interface and is a Collection that does not contain repeating elements (which are consistent according to equals) and in no particular order
  • SortedSet: An extension of Set, similar to Set except that its elements are ordered
  • List interface: List is a repeatable and ordered collection, and each element has a corresponding sequential index. The main implementation classes are ArrayList, LinkedList and so on
  • Queue interface: Elements in a Queue have an implicit order, and each Queue has a head element

3.2 the Map interface

Map and Collection exist side by side, which are used to store key-value pair data with mapping relationship. The key and value in Map can be any reference type data, because the key in Map is stored by Set, so duplication is not allowed. Therefore, the corresponding object of the key value must override the **hashCode() and equals()** methods. Since the key is unique, you can always find the corresponding value through the key. Map also has an extension interface called sortedMap. The difference is that the keys are ordered.

3.3 the Iterator interface

This is an iterator interface that can be used to return one element at a time from a collection. There is also an Iterator interface for List objects, the Listiterator interface, which adds some list-related methods compared to the Iterator interface. Also part of the collections framework is the Iterable interface under the java.lang package, which is an object that provides iterators and can be used to enhance for.

3.4 interface tree


1. Iterator interfaces and Iterable interfaces

1.1 an overview of the

A class that implements the Iterator interface represents an Iterator. A class that implements the Iterable interface represents an Iterable.

The Collection interface inherits from the Iterable interface, which means that the Collection interface is Iterable. The Iterator method that calls the Collection interface returns an Iterator object that iterates through the elements of the Collection. This is the same feature of the Collection framework compared to arrays: Provides a new way to iterate over stored elements without affecting the original collection object because a new object is created, and many of the details of the traversal process are implemented inside the iterator. Note that the collection object gets a brand new iterator each time it calls the iterator() method. The default cursor precedes the first element of the collection. There is also a ListIterator interface that extends the Iterator interface by adding methods that allow it to iterate over a sorted List object, either using hasNext and next forward or hasPrevious and previous backward.

1.2 Iterator objects

An iterator object has several methods for iterating over elements, with cursors default before the first element in the collection.

  • HasNext () returns the presence of an element at the next location, which can be used to detect whether the end of the collection has been reached
  • Next () returns iterating over the next element, and NoSuchElementException is reported if there is no element next
  • Remove () removes the most recently returned element from the iteration, requiring that next() be called first to ensure that the element is removed correctly. If remove has already been called after next, a second call will throw an IllegalStateException

2. Use iterators to iterate over operations

The first way is to iterate through the collection using hasNext, next methods, using ArrayList as an example

public class IteratorTest {
    public void test1(a){
        Collection coll1 = new ArrayList();
        // Get the iterator object
        Iterator itColl1 = coll1.iterator();
        //hasNext() determines if the next bit has an element
        while (itColl1.hasNext()){
            //next() gets the next element
            System.out.println("2)"; // output: jack}}}Copy the code

The second way: Java5 after the implementation of foreach loop iteratively access collections and arrays, the underlying implementation using iterator

public class ForEachText {
    public void test1(a) {
        Collection coll1 = new ArrayList();
        // Use the enhanced for loop to iterate over elements without subscripts
        for (Object obj : coll1) {
            System.out.println(obj); // output:Tom 123}}}Copy the code

Realization of Collection subinterface

1. Methods defined in the Collection interface

Some generic methods for manipulating collection data are defined in this interface, but there is no concrete implementation. Instead, specific operations are implemented in the subinterface.

  1. Coll1.add (object e) Adds element E to coll1

  2. Coll1.size () Displays the length of coll1

  3. Coll1. addAll(Collection coll2) adds the elements of coll2 to coll1

  4. Coll1.clear () clears data in coll1 but the object still exists

  5. Coll1.isempty () checks whether coll1 isEmpty(not a null pointer)

  6. Coll1. contains(Object obj) Determines whether the current collection contains OBj

Note: This returns true if you compare the contents of strings to be consistent, since strings override equals. Equals is false if no other class overrides it. Therefore, it is best to override the equals method whenever data is loaded into the Collection

  1. Coll1. containsAll(Collection coll2) Checks whether all coll2 data is contained in coll1

  2. Coll1. remove(object obj) Removes the element obj from the collection

  3. Coll1. removeAll(Collection coll2) Removes all elements of coll2 from coll1

  4. Coll1. retainAll(Collection coll2) After coll1 is processed, the content of coll1 is the intersection of Coll1 and Coll2

  5. Coll1. equals(Collection coll2) compares coll1 with all elements of coll2

  6. Coll1.hashcode () computes the hash of coll1

  7. Coll1.toarray () implements collection toArray

Note: Array-to-collection conversions can be implemented using the arrays.aslist () method

  1. Coll1.iterator () returns an iterator object

2. Set

A Set is an unordered Set that does not contain repeating elements. It extends Collection but does not add new methods. If you add the same element consecutively to a set, it returns true the first time and false the next time. So how do you tell if it’s the same element? Set uses the Equals method to add element objects and the HashCode method, which are described in more detail below. Classes that implement the Set interface in Java include LinkedHashSet, HashSet, TreeSet, and so on.

2.1 HashSet

A HashSet is a hash table implementation of a Set. It is a typical implementation of the Set interface, and is used most of the time with sets. A HashSet uses the Hash algorithm to store the elements of a collection, so it has good access, find, and delete performance. A HashSet does not guarantee the order of elements, nor is it thread-safe. For a HashSet, if two elements are equal, the hashcodes of the two elements must be equal, and equals must return true. Therefore, elements stored in a HashSet must override the hashCode and equals methods to ensure that the hashCode is generated.

What happens when we add elements to a HashSet? First, a HashSet calls the object’s hashCode() method to get the object’s hashCode value. Then, based on the hashCode value, some hash function determines where the object is stored in the underlying array of the HashSet. For example, if hashCode is 1000 and the underlying array length is 15, then 1000%15 is the index of the element, although this calculation is very low… The more hashed the elements, the better the hash function is designed. If the hashCode() values of two elements are equal, the equals method will be called. If the equals method is true, the hash function will fail. If false, the element is saved because the array already has elements at its location (hash collisions), so the link continues through a linked list. After a hash conflict occurs, element A is stored in a linked list with the data that already exists in the index: in JDK7, element A is placed in an array pointing to the original linked list; In JDK8, the original list is placed in an array, pointing to element A; So the bottom layer of a HashSet is an array + a linked list.

    public void test1(a) {
        Set set = new HashSet();
        set.add(new User("tom".12));
        Iterator setIt = set.iterator();
        while(setIt.hasNext()){ System.out.println(; }}//output: ABC 123 User{name=' Tom ', age=12}
// You can see from the result that duplicate elements are not stored in the HashSet
Copy the code

Additionally, in addition to the empty parameter constructor, a HashSet has a constructor that takes the initial capacity, which represents the size of the underlying array, and the load factor, which indicates the capacity to expand when the HashSet reaches occupancy, the details of which are dissected in the HashMap.

2.2 LinkedHashSet

LinkedHashSet, a subclass of HashSet, determines where elements are stored based on their hashCode value, but it also maintains the order of elements using a two-way linked list, which makes them appear to be stored in insertion order. LinkedHashSet has slightly lower insert performance than HashSet, but good performance when iteratively accessing all elements in a Set. LinkedHashSet does not allow collection elements to be repeated. The time it takes to iterate over it is proportional only to size, not capacity.

2.3 the TreeSet

TreeSet is an implementation class of the SortedSet interface, which stores content in a tree structure that ensures that collection elements are sorted. TreeSet uses red-black tree structure to store data. The time complexity of tree modification or search is O(logn). There are two sorting methods for TreeSet, one is natural (the default) and the other is custom. He has four constructors:

public TreeSet(a){}	// Create a new tree set whose elements must implement the Comparable interface
public TreeSet(Collection <? extends E> coll){}		// Add elements from coll to the tree set
public TreeSet(Comparator <? super E> comp){}	// Create a tree set to sort by comp (custom sort)
public TreeSet(SortedSet <E> set){}		// Migrate the contents of the set and the sorting method to generate a new tree set
Copy the code

In natural sorting, TreeSet calls the compareTo method of elements to compare sizes and then sorts them in ascending order, so elements added to a TreeSet must implement the compareTo method of the Comparable interface.

import org.junit.Test;
import java.util.*;
// Customize the User class
class User implements Comparable{
    private String name;
    private Integer age;
	/ * * * * * * * * * * * * * * * * * * to omit the constructor toString method such as * * * * * * * * * * * * * * * * * * * * * * /
    Implement a two-level sorting of compareTo methods on the Comparable interface in custom classes
    public int compareTo(Object o) {
        if(o instanceof User){
            User user = (User)o;
            if(this.age.compareTo(user.age)==0) return;
            else return this.age.compareTo(user.age);
            throw new RuntimeException("Type mismatch"); }}}// A natural sort instance
class TreeSetTest{
    public void test(a) {
        TreeSet<Integer> set = new TreeSet<>();
        Iterator<Integer> setIt = set.iterator();
        //output: -5 123 234
        TreeSet<Object> set2 = new TreeSet<>();
        set2.add(new User("Tom".15));
        set2.add(new User("Jack".20));
        set2.add(new User("Oliver".12));
        set2.add(new User("Adam".20));
        Iterator<Object> set2It = set2.iterator();
        while (set2It.hasNext()){
        //output: User{name='Oliver', age=12}	User{name='Tom', age=15}
		// User{name='Adam', age=20} User{name='Jack', age=20}}}Copy the code

Compare (T o1,T O2). If the compare(T o1,T O2) method returns a positive integer, o1 is greater than O2. If 0 is returned, it is equal; Returns a negative integer indicating that O1 is less than O2. To implement a custom order, you pass an instance implementing the Comparator interface as a parameter to TreeSet’s constructor. The standard for determining the equality of two elements using custom sorting is that comparing two elements using the Comparator returns 0.

public class TreeSetTest1 {
    public void test3(a) {
        // Custom sort lambda expressions
        TreeSet<User> set = new TreeSet<>((o1, o2) -> {
            if(o1 ! =null&& o2 ! =null) {return o1.getName().compareTo(o2.getName());
                throw new RuntimeException("Type mismatch"); }}); set.add(new User("Tom".15));
        set.add(new User("Jack".20));
        set.add(new User("Oliver".12));
        set.add(new User("Adam".20));
        Iterator<User> setIt = set.iterator();
        while(setIt.hasNext()){ System.out.println(; }}}Copy the code

Classic example:

class Test{	
    public void test2(a) {
        HashSet set = new HashSet();
        Person p1 = new Person("AA".1001);
        Person p2 = new Person("BB".1002);
        set.add(p2); = "CC";
        //output: [Person{name='CC', age=1001}, Person{name='BB', age=1002}]
        // Select * from set (CC 1001);
        set.add(new Person("CC".1001));
		/ * the output:  [Person{name='CC',age=1001},Person{name='CC',age=1001}, Person{name='BB',age=1002}] one of the (CC 1001) indexes in the set is actually (AA 1001) calculated by hashCode so there are two co-existing */
       	set.add(new Person("AA".1001));
        / * the output:  [Person{name='CC', age=1001}, Person{name='CC', age=1001}, Person{name='AA', age=1001}, Person{name='BB', Age =1002}] The new hashCode (AA 1001) is the same as one of the hashcodes converted from p1 (CC 1001), but as described above, when hashcodes are consistent, the equals method is called. Compare their name and age, it is clear that AA and CC are not the same, so we can still increase success */}}Copy the code

3. List

As mentioned earlier, there are some disadvantages of using arrays to store data, so arrays are usually replaced by lists. The List interface extends the Collection interface and defines a set of elements in a specified order. Each element of the collection has a specific position (starting from 0). So when you add to a List, it adds to the end, and when you remove an element, it moves the element that follows it forward. That is, the elements in the List collection class are ordered and repeatable. Each element in the collection has its corresponding sequential index, and the elements in the container can be accessed by ordinal order. In addition to the methods inherited from the Collection, List adds methods that manipulate Collection elements based on indexes.

  • Void add(int index, Object ele): Insert ele at index position
  • Boolean addAll(int index, Collection eles): Adds all elements from eles starting at index
  • Object get(int index): Gets the element at the specified index position
  • Int indexOf(Object obj): Returns the position where obj first appears in the set
  • Int lastIndexOf(Object obj): Returns the position of the last occurrence of obj in the current collection
  • Object remove(int index): Removes the element at the specified index position and returns the element
  • Object set(int index, Object ele): Sets the element at the specified index position to ele
  • List subList(int fromIndex, int toIndex): Returns a subset of positions from fromIndex to toIndex

The List implementation classes in the JDK API are ArrayList, LinkedList, and Vector.

3.1 ArrayList

ArrayList is the main implementation class for the List interface, which stores elements in an array. In essence, an ArrayList is a “variable-length” array of object references. In JDK1.7, ArrayList creates an array with an initial size of 10. In JDK1.8, ArrayList creates an array with an initial size of 0. Create an array of size 10 when the first element is added. What if the initial capacity is insufficient? This is when the ArrayList expansion mechanism starts. In JDK7 and JDK8, ArrayList is expanded by 1.5 times. ArrayList has three constructors:

public ArrayList(a){}	// Create an ArrayList with the default capacity
public ArrayList(int initalCapacity){}		// Create an ArrayList with an underlying array size of initalCapacity
public ArrayList(Collection <? extends E> coll){} // Create an ArrayList containing all elements of colL with an initial capacity 1.1 times that of COLl
Copy the code

An example of a wave method for ArrayList:

class Test{
    public void test3(a) {
        ArrayList list = new ArrayList();
        list.add(new Person("jack".15));
        System.out.println(list); //output:[tom, 123, Person{name='jack', age=15}, 123]
        // 1) list.add(index,Object obj) Insert obj into list at index position
        //output:[tom, jerry, 123, Person{name='jack', age=15}, 123]
        // 2) list.addAll(index, list ls) addAll(index, list ls
        List ls = Arrays.asList(1.2.3);
        //[tom, jerry, 1, 2, 3, 123, Person{name='jack', age=15}, 123]
        // 3) list.get(index) Retrievesthe element whose index is index
        System.out.println(list.get(0)); //oputput:tom
        // 4) list.indexof (Object obj) returns -1 if obj does not appear in list for the first time
        System.out.println(list.indexOf(123)); //output:5
        // 5) list.lastindexof (Object obj) returns -1 if the lastIndexOf obj in list does not exist
        System.out.println(list.lastIndexOf(123)); //output:7
        // 6) list.set(index,Object obj) change the index of the list to obj
        //output:[tom, jerry, 654, 2, 3, 123, Person{name='jack', age=15}, 123]
        // 7) list.remove(index) remove the index element from the list
        // It is important to note that if an integer is entered, it is deleted by index by default
        // New Integer(xx) is required to delete the data
        Object obj = list.remove(2); // This returns the deleted element
        System.out.println(obj); //output:654
        //output:[tom, jerry, 2, 3, 123, Person{name='jack', age=15}, 123]
        // 8) list.subList(fromIndex,Index) returns a list subset from fromIndex to Index(left closed and right open)
        List list1 = list.subList(3.6);
        //output:[3, 123, Person{name='jack', age=15}]}}Copy the code

3.2 LinkedList

LinkedList is a bidirectional LinkedList that is less efficient for random reads than ArrayList, but more efficient for inserting data. Instead of declaring an array internally, LinkedList defines Node types first and last to record the first and last elements. At the same time, the inner class Node is defined as the basic structure for storing data in the bidirectional linked list. In addition to storing data, Node defines two variables: the prev variable records the location of the previous element, and the next variable records the location of the next element.

transient Node<E> first;
transient Node<E> last;
private static class Node<E> { 
    E item;
    LinkedList.Node<E> next;
    LinkedList.Node<E> prev;
    Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
        this.item = element; = next;
        this.prev = prev; }}Copy the code

LinkedList provides two constructors, one for empty arguments and one for creating LinkedList containing specified Collection elements. In addition, it implements some methods of Collection as well as custom methods:

public class LinkedListTest {
    public void test2(a) {
        var list1 = new LinkedList<String>();

        var list2 = new LinkedList<String>();

        // 1) addFirst adds the element to the head of the list
        // 2) addLast adds the element to the end of the list
        System.out.println(list1); //output:[first, test1, test2, test3, last]
        // 3) getFirst gets the list header element
        System.out.println(list2.getFirst()); / / the output: not
        // 4) getLast gets the last element of the list
        System.out.println(list2.getLast()); / / the output: demo4
        // 5) removeFirst Removes the header element
        // 6) removeLast removes the last element of the list
        System.out.println(list2); / / the output: [demo2, demo3]}}Copy the code

3.3 the Vector

Vector is an ancient collection, dating back to JDK1.0. Most operations are the same as ArrayList, except that Vector is thread-safe. Of all the lists, an ArrayList is the best default. Use LinkedList when insertions and deletions are frequent. Vector is always slower than ArrayList, so avoid using it.

Ps: the interview question: can you tell me the ArrayList/LinkedList/similarities and differences between the Vector? What is your understanding? What’s underneath an ArrayList? Expansion mechanism? What is the biggest difference between Vector and ArrayList? [Shang Silicon Valley]

1) Similarities and differences between ArrayList and LinkedList Both of which are thread-safe and perform more efficiently than thread-safe Vector. In addition, ArrayList is a data structure based on dynamic arrays, and LinkedList is a data structure based on linked lists. ArrayList feels superior to LinkedList for random access to GET and set because LinkedList moves the pointer. For the add and remove operations add(specifically insert) and remove, LinkedList is superior because ArrayList moves data. Vector and ArrayList are almost identical, except that **Vector is strongly synchronized. So it’s more expensive and slower to access than ArrayList. Normally, most Java programmers use an ArrayList rather than a Vector, because synchronization can be completely controlled by the programmer. Vector requests twice as much space each time it expands, whereas ArrayList requests 1.5 times as much. Vector also has a subclass, Stack.

4. Queue

The Queue interface extends the Collection interface, which defines a head position that is the next element to be removed. Queues are usually first-in, first-out operations (stacks are last-in, first-out), or in a specified order. You can use the Element method to get the queue header and throw an exception if the queue is empty. The peek method can return the queue header. If the queue is empty, no exception is thrown. At the same time, it is best to add elements using the Offer method and remove elements using the poll method, because the add/remove methods fail without throwing an exception, whereas the Add and remove methods of Collection fail to throw an exception. The LinkedList class mentioned above provides a simple implementation of Queue, but null inserts should be avoided.

4.1 a Deque

Java6 introduced the Deque interface (double-ended Queue), which is a subinterface of the Queue interface. Double-ended queues allow adding and deleting elements in the header and tail, but not in the middle. This interface is implemented by the ArrayDeque and LinkedList classes, both of which provide double-endian queues.

public class QueueTest {
     public void test1(a) {
         var arr = new ArrayDeque<String>();
         //1) There are two ways to add elements to the head and tail of the queue
         //1.1) addFirst() addLast() raises IllegalStateException if the queue is full
         OfferFirst () offerLast() Returns false if the queue is full
         System.out.println(arr);  / / the output: [tom1, tom2]
         System.out.println(arr); //output: [tom3, tom1, tom2]
         System.out.println(arr); //output: [tom3, tom1, tom2, tom4]
         //2) If the queue is not empty, there are two ways to delete the header element and the tail element
         RemoveFirst () removeLast() throws NoSuchElementException if the queue is empty
         //2.2) pollFirst() pollLast() returns null if the queue is empty
         System.out.println(arr); //output: [tom1, tom2, tom4]
         System.out.println(arr); / / the output: [tom1, tom2]
         //3) There are two ways to get the head element and the tail element if the queue is not empty
         //3.1) getFirst() getLast() throws a NoSuchElementException if the queue is empty
         //3.2) peekFirst() peekLast() returns null if the queue is empty
         String first = arr.getFirst();
         String last = arr.peekLast();
         System.out.println(first+"\t"+last); / / the output: tom1 tom2}}Copy the code

4.2 PriorityQueue

A priority queue uses a data structure called a heap, in which elements can be inserted in any order, but the smallest is always removed when deleted. Priority queues are used for scheduling tasks. When a new task is started, the task with the highest priority is deleted from the queue (traditionally, the highest priority is 1). The object (element) added here needs to implement the compareTo method.

public class PriorityQueueTest {
    public void test1(a) {
        var pq = new PriorityQueue<LocalDate>();
        // Remove removes the smallest element
        System.out.println(pq); / / the output: [2019-06-01, 2019-06-01]}}Copy the code

4.3 Blocking Queue

Another type of queue is a blocking queue, which will throw an exception if the queue is full. The main implementation classes include ArrayBlockQueue, PriorityBlockingQueue, and LinkedBlockingQueue. Although the interface does not define a blocking method, the implementation class extends the parent interface to implement the blocking method. origin

Implementation of Map interface

The Map interface exists alongside the Collection interface to store mapped key-value pairs. The keys and values in the Map can be any reference type of data. The String class is commonly used as the “key” of a Map. There is a one-way one-to-one relationship between key and value, that is, a unique and definite value can always be found through a specified key. Common implementation classes for the Map interface: HashMap, TreeMap, LinkedHashMap, and Properties.

The Map implementation class inheritance structure is as follows:

1. HashMap

HashMap implements the Map using a hash table, which determines the position according to the hashCode method of each key, so the corresponding class for the key element overrides equals() and hashCode(). Meanwhile, the set formed by all values is unordered and repeatable. So the value element’s corresponding class overrides equals(). A HashMap allows null keys and null values and, like a HashSet, does not guarantee the order of the mapping. In a HashMap, a key-value pair forms an entry, and the collection of all entries is unordered and non-repeatable. A HashMap determines that two keys are equal when they return true via equals() and the hashCode values are equal. The HashMap criterion for determining the equality of two values is that they return true via equals().

1.1 the constructor

Public HashMap() creates a new HashMap using the default initial capacity and load factor

Public HashMap(int init) Creates a HashMap using the given init and default load factor

Public HashMap(int init, float loadFactor) creates a HashMap using init hash bits and the given loadFactor(non-negative)

public HashMap(Map <? extends K, ? Extends V> map) creates a HashMap and copies the content from the map. The initial capacity is based on the map size, with a default load factor

1.2 Common Methods

The Collection framework does not treat the mapping table itself as a Collection, so it is level with the Collection. But you can get a view of the mapping table, which is a set of views that implement the Collection interface or its subinterfaces. There are three views: key set, value set, and key value pair set.

Set keyset(); // Generate a keyset

Collection values(); // Generate a set of values

Set<Map.Entry<K,V>> entrySet(); // Generate a set of key-value pairs

The keySet method returns the object of a class that implements the Set interface and whose methods operate on the original mapping table. The Set interface extends the Collection interface, so you can use a keySet just like any Collection. The same is true for entrySet.

/ / * * * * * * * * * * * * * * * * * * * * methods HashMap * * * * * * * * * * * * * * * * * * * * * *
public class MapTest {
    public void test1(a) {
        HashMap<String,Object> map = new HashMap<>();
        HashMap<String,Object> mapCp = new HashMap<>();
        //1) Add a key value pair put(key,value)
        map.put("id".2);  // Perform the put operation on the same key to replace the value
        //2) Add key-value pairs putAll(HashMap xx)
        //3) get(key) Obtains the value corresponding to the key without removing it
        Object id = map.get("id");
        //4) remove(key) Returns the value of the corresponding key
        //5) Boolean containsKey(key) Specifies whether it contains a key
        // Boolean containsValue(value) specifies whether it containsValue
        //6) map.clear() sets all elements in map to null but map is not null
    public void test2(a) {
        HashMap<String,Object> map = new HashMap<>();
        //1) The keySet method returns a set for all keys
        Set<String> mks = map.keySet();
        // We can then iterate over the output using iterators
        Iterator<String> mksIt = mks.iterator();
        //2) The values method returns a collection of all values
        Collection<Object> mvs = map.values();
        // We can then iterate over the output using iterators
        Iterator<Object> mvsIt = mvs.iterator();
        //3) The entrySet method returns a set of entries
        Set<Map.Entry<String, Object>> mes = map.entrySet();
        // We can then iterate over the output using iterators
        Iterator<Map.Entry<String, Object>> mesIt = mes.iterator();
            Map.Entry<String, Object> entry =;
            System.out.println("key is "+entry.getKey()+"|values is "+entry.getValue());
        // If you need to iterate through key-values, you only need to know one of them}}Copy the code

1.3 Underlying Implementation Principles

The underlying implementation principle of HashMap, Java7, is different from Java8. In Java7 and earlier, HashMap was an array + linked list structure. In Java8 version HashMap is an array + linked list + red-black tree implementation.

When the empty argument constructor of the HashMap is instantiated, the underlying one-dimensional array Entry[] TABLE ** of length 16 is created (in Java8 arrays are created only when the PUT method is called, and are of type Node)**. When map.put(key1,value1) is called, the hashCode() method of the class of key1 is first called to calculate the hash value of key1. This value uses the algorithm to calculate the position of the Entry array in the underlying array of the HashMap (index position). If this position is empty, the key1-value1 key/value pair is inserted successfully. -① If the hash value of key1 is different from the hash value of the existing data, the insert succeeds. -② If the hash value of key1 is the same as the hash value of the existing data (key2-value2), call equals of the class where key1 resides. -②equals returns false, key1-value1 is added successfully.

Note that key1-Value1 will be stored in a linked list with the data that already exists for the index in the case of a successful addition to the first.

1.4 Capacity Expansion Mechanism

As the number of elements in a HashMap increases, the probability of hash collisions increases because the array length is fixed. So to improve the efficiency of the query, the HashMap array has to be expanded, and after the HashMap array is expanded, the most performance costly point occurs: the data in the original array has to be recalculated and put into the new array, which is called resize.

Array expansion occurs when the number of elements in a HashMap exceeds the product of the array size and loadFactor. As mentioned earlier, the default value of loadFactor is 0.75, which is a compromise value. That is, by default, when the number of elements in the HashMap exceeds 12(16*0.75), the array size is doubled to 32, and the position of each element in the array is recalculated. Since this is a very performance-intensive operation, if we already know the number of elements in a HashMap, the preset number of elements can effectively improve the performance of the HashMap. In Java8, when the number of objects in a HashMap reaches 8, if capacity does not reach 64, the HashMap will be expanded first. If capacity reaches 64, the chain will become a tree, and the Node type will be changed from Node to TreeNode. Of course, if the number of nodes in the tree is judged to be less than 6 in the next resize after the mapping relationship is removed, the tree will also be converted to a linked list.

How does the size of the load factor value affect the HashMap

  1. The size of the load factor determines the data density of a HashMap.
  2. The higher the load factor is, the higher the collision probability will be, and the longer the linked list in the array will be. As a result, the number of comparisons during query or insertion will increase, and the performance will decrease.
  3. The smaller the load factor, the easier it is to trigger capacity expansion, and the smaller the data density, which means less collisions, shorter linked lists in arrays, fewer queries and insertions, and higher performance. But it wastes some content space. In addition, frequent capacity expansion may affect performance. Therefore, you are advised to initialize a larger space.
  4. Based on the reference and research experience of other languages, the load factor is considered to be between 0.7 and 0.75, where the average retrieval length is close to constant.

2. LinkedHashMap

LinkedHashMap, a subclass of HashMap, uses a pair of bidirectional linked lists to record the order in which elements are added, based on the storage structure of HashMap. Like LinkedHashSet, LinkedHashMap maintains the iteration order of the Map: the iteration order is the same as the insertion order of key-value pairs. LinkedHashMap may perform worse than HashMap due to the overhead of maintaining the linked-list structure, but its iteration time is proportional only to the size of the LinkedHashMap, not its capacity.

3. TreeMap

When TreeMap stores key-value pairs, it is necessary to sort them by them to ensure that all key-value pairs are in an ordered state. The bottom layer of TreeSet uses red-black tree structure to store the sorting of TreeMap keys. There are also two sorting methods: If natural ordering is used, all TreeMap keys must implement the Comparable interface and all keys must be objects of the same class, otherwise ClasssCastException will be thrown; If you use custom sorting, you pass in a Comparator object when you create a TreeMap that sorts all the keys in the TreeMap. You don’t need the Map’s key to implement the Comparable interface. The sorting content is basically the same as TreeSet and will not be repeated here. TreeMap’s criterion for determining that two keys are equal is that both keys return 0 using either compareTo() or compare(). TreeMap is typically used only when sorting is required or when the hashCode method is poorly implemented.

TreeMap has several constructors:

Public TreeMap() creates a TreeMap in which the keys are ordered in natural order

public TreeMap(Map <? extends K, ? Extends V> map) is equivalent to calling TreeMap and adding key-value pairs from the map

public TreeMap(Comparator <? Super K> comp) creates a TreeMap and arranges the keys in a custom order

public TreeMap(SortedMap<K, ? Extends V> map) creates a TreeMap with the same initial content and sort as a map

4. Hashtable

Hashtable is an old Map implementation class, and unlike HashMap, **Hashtable is thread-safe. **Hashtable implements the same principle and functions as HashMap. Hash table structure is used in the bottom layer, which can be used interchangeably in many cases. But Hashtable does not allow null for keys and values. Like a HashMap, a Hashtable does not guarantee the order of key-value pairs. Hashtable Specifies whether two keys are equal and two values are equal, which is the same as that of a HashMap.

4.1 the Properties

The Properties class is a subclass of Hashtable, which is used to process Properties files. Since the keys and values in the Properties file are strings, the keys and values in the Properties file are strings. When accessing data, setProperty(String Key,String Value) and getProperty(String Key) methods are recommended.

public class PropertiesTest {
    // Use the properties class to read the configuration file using the IO stream
    public void test1(a) throws Exception {
        FileInputStream fis = null;
        Properties pro = new Properties();
        fis = new FileInputStream("top/jtszt/ReflectionTest/");
        String name = pro.getProperty("name");
        String password = pro.getProperty("password");
        System.out.println("name is "+name+", password is "+password); fis.close(); }}Copy the code

Collections and Arrays

1. The Collections utility class

Collections is a utility class that operates on Collections such as sets, lists, and maps. Collections provides a series of static methods for sorting, querying, and modifying collection elements, as well as methods for immutability and synchronization control of collection objects. Collections provides multiple synchronizedXx() methods to convert thread-unsafe list/Collection/ Map to thread-safe.

public class CollectionsTest {
    public void test1(a) {
        List<Integer> list = new ArrayList<>();
        //1) The reverse(list) method reverses elements in a list
        Collections.reverse(list); // No value is returned for changes made to list
        //2) Shuffle (list) Shuffles the list randomly
        //3) sort(list) compareTo
        //4) swap(list, I,j) swap(list, I,j
        //5) Max (Collection) returns the largest element in the Collection (based on compareTo method)
        //6) min(Collection) returns the smallest element in the Collection (based on the compareTo method)
        //7) frequency(Collection, I) returns the number of occurrences of I in a Collection
        int frequency = Collections.frequency(list, 55);
        //8) copy(list dest,list SRC) Copy the contents of SRC to dest
        // Create a list with null src.size()
        List<Object> dest = Arrays.asList(new Object[list.size()]);
        // 9) Convert list to thread-safe using synchronizedList(list)List<Integer> list1 = Collections.synchronizedList(list); }}Copy the code

2. Arrays utility classes

The Arrays class provides static methods for working with Arrays, most of which have fully overloaded forms: one for primitive data types and one for objects. In actual development, sometimes Arrays and collections need to be converted. In this case, arrays.aslist method can be used to convert Arrays to collections, and toArray() method can also be used to convert Arrays to Arrays. A collection is cast to an array of concrete types using the toArray method, which takes an array of objects. There are other ways:

  1. Sort: Sort an array in ascending order
  2. BinarySearch: Finds the given key in an ordered array. This method returns the subscript of the key or the negative value encoding the safe insertion point
  3. Fill: Fills the array with the given value
  4. Equals and deepEquals: Returns true if two arrays passed are the same object, or both are null, or of the same size and contain equivalent content. There are no subarray versions of these two methods, and the equals method for Object[] calls the object.equals method for each element in the array. Because this method does no special handling for nested arrays, it generally cannot be used to compare arrays containing arrays. The deepEquals method performs a recursive check on the equivalence of two objects [] and takes into account the equivalence of nested arrays.
  5. HashCode and deepHashCode: returns a hashCode based on the contents of a given array. Because the deepHashcode method for Object[] considers the contents of a nested array, the deepHashcode method computes the hash code recursively for Object[].
  6. ToString and deepToString: Return string representations of the contents of an array. The returned string consists of a list of array elements separated by commas, and the entire list is enclosed in []. The contents of an array type are converted to a String using string.valueof. The toString method for 0bject[] converts all nested arrays to strings using the object.tostring method. The deepToString method returns a string representation of Object [] by recursively converting a nested array into a string defined by the method.


  • Java Core Technology
  • Java Programming Language
  • Ideas for Java Programming