When I was sorting out the five data structures of Redis, when I mentioned the list, set and other knowledge points, I remembered the awkward days when I was just in college. When I was talking with my girlfriend, she said, why don’t you also sort them out? Oneself also recall the following that time we fall in love you let me wait for you in the machine room, hum! (PS: I have no free time to mention this issue of what ah, first go to coax and then come back to continue to write ah)

.

This is the mind map I made (my tutor asked me to do it at that time, AND I thank him for cultivating me with this habit). It happens to be used here as a catalog (I will display it later when I explain it).

Personal public account: Java Architects Association, updated daily technical good articles

Before learning Java, when it comes to storing things, the first thing that comes to mind is to use arrays. Using arrays is also quite convenient in data access, with high storage efficiency and fast access. However, it is also subject to some restrictions, such as the length of the array and the type of the array. When I need a string and an Integer, I have to define it twice. The size of the array is also limited. Even if I define the length of the array dynamically, it still needs to be fixed within a certain range, which is inconvenient and inflexible.

What if I want to eliminate this limitation and inconvenience? Does Java provide a solution? Java containers are instances of classes provided by the Java API that are used to store objects in programs, mainly in the java.util package, which is of unlimited length, unlimited type, and you can still store Integer classes while you’re storing String classes. They don’t conflict.

The result of the container API class diagram is as follows:

The Collection interface

Collection is the most basic Collection interface. A Collection represents a group of objects, namely the elements of a Collection. Some collections allow the same elements while others do not. Some can sort and some can’t. The Java SDK does not provide classes that directly inherit from a Collection. The Java SDK provides classes that inherit from a Collection’s “subinterfaces” such as List and Set.

For example:

import java.util.*;
public class TestA{
	public static void main(String[] args)
	{
		Collection<String> lstcoll=new ArrayList<String>();
  	lstcoll.add("China");
  	lstcoll.add(new String("ZD"));
  	
 		System.out.println("size="+lstcoll.size());
    System.out.println(lstcoll);
	}
Copy the code

Results:

The List interface

A List is an ordered Collection, and using this interface you can precisely control where each element is inserted. The user can access elements in a List using an index (the element’s position in the List, similar to an array’s subscript), that is, it is sequential, similar to a Java array. Unlike sets, lists are allowed to have the same elements. List container classes provided by J2SDK include ArrayList, LinkedList and so on.

Example:

import java.util.*; public class TestB{ public static void main(String[] args) { List<String> l1=new LinkedList<String>(); for(int i=0; i<=5; i++){ l1.add("a"+i); } System.out.println(l1); l1.add(3,"a100"); System.out.println(l1); l1.set(6,"a200"); System.out.println(l1); System.out.println((String)l1.get(2)+" "); l1.remove(1); System.out.println(l1); }}Copy the code

Running results:

ArrayList

An ArrayList is analogous to cis-storage, wrapping an array Object[]. When an ArrayList is instantiated, an array is instantiated, and when objects are added to the ArrayList, the array size changes accordingly. This leads to the following features: fast random access, where you can access each element immediately without worrying about performance, by calling the get(I) method to access the array element with the subscript I. Adding objects to it is slow, and when you create an array you don’t know its capacity, so you have to do a lot of things in memory when changing the array. Manipulating objects is slow, and when you add objects between any two elements in the array, the array moves all subsequent objects.

Let’s take a look at source-level operations in action

Array-based support for fast random access

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Java.io.Serializable // implements RandomAccess representation to support fast RandomAccessCopy the code

Array default size is 10, array based implementation

private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData; // non-private to simplify nested class access
Copy the code

The add () method is called when an element is added, and ensureCapacityInternal () is used to guarantee the array’s capacity when the add () method is called, and grow () is called when the array’s capacity is insufficient.

Expansion Code:

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // Expand the capacity by 1.5 times...... . // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); // Copy the original array into the new array.Copy the code

To delete an element, the system.arrayCopy () method is called, which copies all elements after index+1 to the location of index

System.arraycopy(elementData, index+1, elementData, index, numMoved);
Copy the code

LinkedList

LinkedList is the equivalent of chain storage, which is achieved by nodes connecting directly to each other. Each node contains a reference to the previous node, a reference to the next node, and the value stored by the node. When a new node is inserted, only the references to the sequential nodes need to be modified, as well as when records are deleted. This leads to the following features: the objects in it can be manipulated quickly, only the connection needs to be changed, and the new node can be anywhere in memory. There is no random access, although there is a get() method, which is slow because it iterates over the contacts.

Code implementation

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

The Set interface

A Set is a Collection that contains no duplicate elements, i.e. any two elements E1 and e2 have E1.equals (e2)=false, and a Set has at most one null element. The constructor of a Set has a constraint that the Collection argument passed cannot contain duplicate elements.

Set container classes include HashSet, TreeSet, etc.

HashSet

This class implements the Set interface, supported by a hash table (which is actually a HashMap instance). It does not guarantee the iteration order of set; In particular, it does not guarantee the constancy of the order. This class allows the use of null elements.

For example:

import java.util.*; public class TestC{ public static void main(String[] args) { Set <String> s=new HashSet<String>(); s.add("Hello"); // same element s.dd ("Hello"); System.out.println(s); }Copy the code

Results:

treeset

TreeSet is an ordered collection whose purpose is to provide an ordered Set. It inherits AbstractSet class and implements NavigableSet, Cloneable, Serializable interfaces. TreeSet is implemented based on TreeMap. TreeSet elements support two sorting methods: natural sorting or sorting according to the provided Comparator.

The instance

public static void demoOne() { TreeSet<Person> ts = new TreeSet<>(); Ts. Add (new Person(" 三", 11)); Ts. Add (new Person("李四", 12)); Ts. Add (new Person(" wang5 ", 15)); Ts. Add (new Person(" zhao liu ", 21)); System.out.println(ts); }Copy the code

Results: throws an exception: Java. Lang. ClassCastException is obviously appeared abnormal type conversion. The reason is that we need to tell TreeSet how to compare elements, and if we don’t, we’ll throw the exception. Okay

How to solve: How to specify rules for comparison that require implementing the Comparable interface in a custom class (Person) and overriding the compareTo method in the interface

public class Person implements Comparable<Person> { private String name; private int age; . public int compareTo(Person o) { return 0; // When the compareTo method returns 0, there is only one element in the collection. // when compareTo returns a positive number, the collection is stored in the same way as return -1; // The collection is stored in reverse order when compareTo returns a negative number}}Copy the code

Why is it that if you return 0, you only store one element, if you return -1 you store it in reverse order, and if you return 1 you store it in whatever way you want? The reason is that the underlying TreeSet is actually a binary tree mechanism, and every new element inserted (except the first one) will call the compareTo() method to compare it with the last inserted element and arrange it according to the binary tree structure.

If you write the return value from compareTo() to zero, the element value is considered the same element each time it is compared, and no new element other than the first is inserted into the TreeSet. So there is only the first element inserted in the TreeSet.

If you write the return value from compareTo() to 1, each comparison of the element values will treat the newly inserted element as larger than the last one, so the binary tree will be stored to the right of the root and read in positive order.

If you write the return value from compareTo() to -1, each comparison of the element values will treat the newly inserted element as smaller than the last one, so the binary tree will be stored to the left of the root and read in reverse order.

The Map interface

Note that Map does not inherit the Collection interface, which provides key-to-value mapping. A Map cannot contain the same key, and each key can Map only one value. The Map interface provides views of three sets. The contents of a Map can be regarded as a set of keys, a set of values, or a set of key-value mappings.

The implementation classes of Map interface mainly include HashMap and TreeMap.

HaspMap

Add data using PUT (key, value), retrieve data using GET (key), HashMap allows NULL, that is, null value and NULL key. But when a HashMap is treated as a Collection (the values() method returns a Collection), its iteration suboperation time is proportional to the capacity of the HashMap. Therefore, do not set the initialization capacity of the HashMap too high or the load factor too low if the performance of iterative operations is important.

For example:

import java.util.*; public class TestD{ public static void main(String[] args) { Map <String,String> M=new HashMap <String,String>(); M.put("one",new String("1")); M.put("two",new String("2")); System.out.println(M); }}Copy the code

Results:

ConcurrentHashMap

Thread-safe alternative to HashMap for concurrent use, based on JDK1.7 source code.

Data storage structure, HashMap for Entry.

static final class HashEntry<K,V> { final int hash; final K key; volatile V value; volatile HashEntry<K,V> next; } // ConcurrentHashMap uses Segment locking technology. Each Segment lock maintains several hashentries. Multiple threads can access buckets on different segments at the same time. final Segment<K,V>[] segments; //Segment core class inherits ReentrantLock. Static final class Segment<K,V> extends ReentrantLock implements Serializable {// ConcurrentHashMap Because there are 16 Segmen. Static final int DEFAULT_CONCURRENCY_LEVEL = 16; // The default concurrency level is 16.Copy the code

conclusion

There are really only three types of Java containers :Map, List, and Set; But each interface has a different implementation version. Their differences can be reduced to what is behind them. That is, what data structure implements the interface you use.

** For example, ArrayList and LinkedList both implement the List interface. So no matter which one you choose, the basic operation is the same. But ArrayList is underpinned by arrays. LinkedList is implemented by a two-way LinkedList. So LinkedList is good if you want to frequently insert or delete data into a List. Otherwise you should use a faster ArrayList.

The Set option HashSet always performs better than TreeSet. The latter exists because it maintains the sorted state of the elements. Therefore, TreeSet should only be used if you need a sorted Set.

Map selection: As above, select HashMap as much as possible.

In fact, each involved in the bottom of the interview questions are not very difficult, but also can not be taken lightly, if usually do not pay attention to the knowledge of this place, then you will be at a disadvantage in the interview, this is to develop the charm of this line, enjoy this line to stimulate