1. Introduction of sets

Array, collection is a storage operation for multiple data, referred to as the container.

When we introduced collections we used arrays more often.

1.1 Features of arrays

  1. Once the length of an array is specified, the length is determined and cannot be changed;
  2. Once an array is typed, it can only hold arrays of that type, and arrays can only hold data of the same type.

1.2 Disadvantages of arrays

  1. Once the length of an array is specified, the length is determined and cannot be changed.
  2. Delete, add elements, low efficiency;
  3. There is no way to get the actual number of elements in the array. There is no method or attribute provided to get it.
  4. Array storage: ordered, repeatable; An unordered, non-repeatable array is not sufficient

The introduction of sets is to solve the above shortcomings.

classification

Collection mainly includes two types: Collection and Map. Collection stores a Collection of objects, while Map stores a mapping table of key and value pairs (two objects).

Refer to the blog

www.cyc2018.xyz/Java/Java%2…

Snailclimb. Gitee. IO/javaguide / #…

2, the Collection

2.1 the List

The stored elements are ordered and repeatable

  • ArrayList:Object[]The array;
  • Vector:Object[]Arrays, thread-safe;
  • LinkedList: two-way LinkedList (before JDK1.6, JDK1.7 cancelled the loop)

2.1.1 What are the differences between them? Says from?

From he said: from the bottom composition, the characteristics of the data structure said

2.1.2 The difference between ArrayList and LinkedList

  1. Underlying data structure:ArrayListThe underlying use isObjectThe array;LinkedListThe underlying use isTwo-way linked listData structure (bidirectional circular list before JDK 1.6, cancelled after JDK 1.7);
  2. The efficiency of:ArrayListFast search (support fast random access), slow insertion and deletion;LinkedListSearch is slow, insert and delete fast;
  3. Memory space occupied:ArrayListThe space waste is mainly reflected in the list at the end of the list will reserve a certain capacity space, andLinkedListThe main cost of space is the ratio of consumption required for each of its elementsArrayListMore space for the direct precursor and direct successor as well as the data itself.
  4. Whether to ensure thread safety:ArrayList 和 LinkedListThey’re out of sync, which means they’re not thread-safe;

2.1.3 Expansion mechanism of ArrayList

By default, the capacity is 1.5 times that of the original container. (If oldCapacity is odd, run oldCapacity >> 1.)

Take the ArrayList constructed with no parameters as an example

  1. ArrayListAnd three constructors

    public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; Private static final int DEFAULT_CAPACITY = 10; private static final int DEFAULT_CAPACITY = 10; Private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] EMPTY_ELEMENTDATA = {}; /** * shared empty array instance for default size empty instance. * We distinguish it from EMPTY_ELEMENTDATA to see how much it should swell when the first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * ArrayList is an array that contains data */ Transient Object[] elementData; // Non-private to simplify class access at the bottom of the ArrayList /** * Specifies the number of elements contained in the ArrayList */ private int size; /** * The default constructor takes no arguments and creates a pair of empty array instances with an id. After the instance is created using the no-arguments constructor, the container is still an empty array * when the element is first added, Public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * Constructor with an initial capacity argument. */ public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} /** * Construct a list of the elements in the specified collection that are returned in order using iterators for that collection. * If the specified collection is NULL, throws NullPointerException. */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}}Copy the code

  2. The add() method of ArrayList

    /** * appends the specified element to the end of the list. */ public Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! ElementData [size++] = e; return true; }Copy the code

  3. EnsureCapacityInternal (int minCapacity) method

    MinCapacity = size + 1; if the number of new elements is greater than 1, the number of new elements is greater than 1

     // 第一次调用时，此时 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
 // 返回 DEFAULT_CAPACITY = 10
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         return Math.max(DEFAULT_CAPACITY, minCapacity);
     }
     return minCapacity;
 }
 ​
 // 此时的 minCapacity 是 size+1，也就是 当前元素的个数 + 1 = 1
 private void ensureCapacityInternal(int minCapacity) {
     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 }
Copy the code

  4. EnsureExplicitCapacity (int minCapacity) method

    // For the first call, minCapacity = 10, elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, Private void ensureExplicitCapacity(int minCapacity) {modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }Copy the code
    • When we want to add the first element to the ArrayList, elementData.length is 0 (because it is still an empty list), because the executionensureCapacityInternal()Method, so minCapacity is now 10. At this point,minCapacity - elementData.length > 0That’s true, so it’s going to entergrow(minCapacity)Methods.
    • When the second element is added, the minCapacity is 2, and then e lementData.length(capacity) expands to 10 after adding the first element. At this point,minCapacity - elementData.length > 0It’s not valid, so it won’t enter.grow(minCapacity)Methods.
    • When you add the 3rd, 4th, and 10th elements, the grow method is still not executed, and the size of the array is 10.

  5. Grow (int minCapacity) method

    Private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // private void grow(int minCapacity) {// Private void grow(int minCapacity) {// oldCapacity = elementData.length; // Expand the size of the new container = 1.5 times the size of the original container. Int newCapacity = oldCapacity + (oldCapacity >> 1); If (newCapacity - minCapacity < 0) newCapacity = minCapacity; If (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } /** * When minCapacity is greater than MAX_ARRAY_SIZE, */ private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }Copy the code
    • NewCapacity = minCapacity(= 10); newCapacity = minCapacity(= 10); However, the second if judgment does not hold, that is, newCapacity is not larger than MAX_ARRAY_SIZE, and will not be enteredhugeCapacityMethods. The size of the array is 10, and the add method returns true, increasing the size to 1.
    • When the 11th element of add enters the grow method, newCapacity is 15, which is larger than minCapacity (which is 11). If the new capacity is not larger than the array maximum size, it does not enter the hugeCapacity method. The size of the array is increased to 15. The add method returns true, and the size is increased to 11.
    • And so on

2.1.4 Difference between System. Arraycopy and Array. copyOf

  • System. Arraycopy () to an array of array is copied to the target, the target array length must enough, otherwise an error ArrayIndexOutOfBoundsException

    // SRC: source array; SrcPos: source array starting subscript; Dest: target array; DestPos: the starting index of the destination array; System.arraycopy(Object SRC,int srcPos,Object dest,int destPos,int Length) public static void test2(){  System.out.println("==== System.arraycopy ===="); ,4,2,34,12,4 int [] arr1 = {2}; int[] arr2 = new int[10]; arr2[0] = 7; arr2[1] = 8; arr2[2] = 9; System. Arraycopy (arr2 arr1, 0, 1, arr1. Length); System.out.println(Arrays.toString(arr2)); Arraycopy ==== [7, 2, 4, 2, 34, 12, 4, 0, 0, 0]Copy the code

  • Arrays.copyOf returns a new array containing all the elements of the source array, of a custom length

    public static int[] copyOf(int[] original, int newLength) public static void test3(){ System.out.println("==== Arrays.copyOf ===="); Int [] arr3 = {11,22,33,44,55}; Int [] arr4 = Arrays. CopyOf (arr3, 10); System.out.println(Arrays.toString(arr4)); } ==== Arrays.copyOf ==== [11, 22, 33, 44, 55, 0, 0, 0, 0, 0]Copy the code

  • System.arraycopy() requires both the original array and the target array, and copies the original array into the custom array. You can select the starting point of the original array, the length of the original array, and the location of the target array.

  • Array.copyof () is when the system automatically creates an Array internally and returns it. (System.arrayCopy () is still called inside the source code)

2.2 the Set

The stored elements are unordered and non-repeatable

  • HashSet :(unordered, unique) based onHashMapImplementation, the underlying adoptionHashMapTo store elements, thread unsafe, can be storednullValue;
  • LinkedHashSet:LinkedHashSet 是 HashSetSubclass of, and its interior is passedLinkedHashMapTo achieve,Ability to iterate in order of addition;
  • TreeSet (ordered, unique) red-black tree (self-balancing sorting binary tree)

Comparable and Comparator

  • They are both interfaces that must be implemented and overwritten to be used in order to customize the sort;

  • The Comparable interface is implemented by the sorted element (typically a custom class), overwriting the compareTo(T T) method, and customizing the sort in the method;

    • compareTo(T t)Returns theintType, the general memory is:thisReturn 1;thisThe value of is less than the value of the parameter, return-1;ascending
    • Integer,StringAnd so onComparableInterface;
    public class Person implements Comparable<Person>{ private Integer num; // Note that the type is Integer, private String name is used; private int age; // The setters () and getters () methods are omitted. public Person() { } public Person(String name, int age) { this.name = name; this.age = age; } public Person(Integer num, String name, int age) { this.num = num; this.name = name; this.age = age; } @override public int compareTo(Person p) {if(this.age > p.age ()){return 1; } else if(this.age < p.getAge()){ return -1; } return 0; } @Override public boolean equals(Object o) { ... } @Override public int hashCode() { ... } @Override public String toString() { ... }}Copy the code
    /** * The class Person to be sorted implements the Comparable interface, * overwrites the Comparator method, Public static void comparableTest(){system.out.println ("+++++++ comparableTest ++++++++"); System.out.println("============ list =========="); List<Person> personList = new ArrayList<>(); Personlist. add(new Person(3," personList ",22)); Personlist. add(new Person(8," red ",5)); Personlist. add(new Person(7," xiaohua ",15)); Personlist. add(new Person(9," xiaoming ",20)); Collections.sort(personList); Iterator iterator = personList.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } System.out.println("============ set =========="); TreeSet<Person> personTreeSet = new TreeSet<>(); Persontreeset. add(new Person(" personTreeSet ",22)); Persontreeset. add(new Person(" little red ",5)); Persontreeset. add(new Person(" personTreeSet ",15)); Persontreeset. add(new Person(" min ",20)); Iterator iterator1 = personTreeSet.iterator(); while(iterator1.hasNext()){ System.out.println(iterator1.next()); }}Copy the code
    = = = = = = = = = = = = = = = = = = = = = = = = = + + + + + + + comparableTest + + + + + + + + = = = = = = = = = = = = list = = = = = = = = = = Person {num = 8, name = 'red', Age =5} Person{num=7, name=' xiaoming ', age=15} Person{num=9, name=' xiaoming ', age=20} Person{num=3, name=' xiaoming ', age=20} Person{num=3, name=' xiaoming ', Age 22} = = = = = = = = = = = = = set = = = = = = = = = = Person {num = null, name = 'red', the age = 5} Person {num = null, name = 'xiaohua', Age =15} Person{num=null, name=' min ', age=20} Person{num=null, name=' min ', age=22}Copy the code

  • Compare (T t1,T t2) ¶ Compare (T t1,T t2) ¶ compare(T t1,T t2)

    • Compare (T t1,T t2) return 1; compare(T t1,T t2) return 1; If p1 is less than p2, return-1; ascending

      Public static void comparatorTest(){system.out.println (); System.out.println("+++++++ comparatorTest ++++++++"); List<Person> personList = new ArrayList<>(); Personlist. add(new Person(3," personList ",22)); Personlist. add(new Person(8," red ",5)); Personlist. add(new Person(7," xiaohua ",15)); Personlist. add(new Person(9," xiaoming ",20)); Collections.sort(personList, new Comparator<Person>() {@override public int compare(Person p1, Person p2) { if(p1.getNum() > p2.getNum()){ return -1; } else if(p1.getNum() < p2.getNum()){ return 1; } return 0; Return p1.getnum ().compareto (p2.getnum ()); // Return p1.getnum ().compareto (p2.getnum ()); // Default ascending}}); Iterator iterator = personList.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the code
      = = = = = = = = = = = = = = = = = = = = = = + + + + + + + comparatorTest + + + + + + + + Person {num = 9, name = 'Ming', the age = 20} Person {num = 8, name = 'red', Age =5} Person{num=3, name=' ', age=15} Person{num=3, name=' ', age=22}Copy the code