1. Automatic packing and unpacking

As we learned earlier, we can define generic classes, such as linkedlistdeque < item > and arraydeque < item >
When we want to instantiate an object that uses a generic class, we must replace the generic with a specific type.
Recall that Java has eight initial types, and all types other than the initial type are reference types.
For generics, we cannot replace the generic type in < > with the initial type, such as:
Arraydeque < int > is a syntax error. Instead, we use arraydeque < integer >
For each initial type, it is associated with a reference type called "wrapper classes"

We assume that when using generics, we must make a manual conversion, that is, the initial type must be converted to generics

public class BasicArrayList {
    public static void main(String[] args) {
      ArrayList<Integer> L = new ArrayList<Integer>();
      L.add(new Integer(5));
      L.add(new Integer(6));

      /* Use the Integer.valueOf method to convert to int */
      int first = L.get(0).valueOf();
    }
}

The above code is a little annoying to use. Fortunately, Java can automatically perform implicit conversion, so we only need to write the above code as follows:

public class BasicArrayList {
    public static void main(String[] args) {
      ArrayList<Integer> L = new ArrayList<Integer>();
      L.add(5);
      L.add(6);
      int first = L.get(0);
    }
}

Java can automatically pack and unpack,
Suppose we pass a variable of the initial type, but Java expects a boxing type, it will automatically boxing and call blah(new Integer(20))

public static void blah(Integer x) {
    System.out.println(x);
}
int x = 20;
blah(x);

Suppose we pass a variable of packing type, but Java expects the initial type, it will be unpacked automatically

public static void blahPrimitive(int x) {
    System.out.println(x);
}
Integer x = new Integer(20);
blahPrimitive(x);

Warning:
When it comes to automatic packing and unpacking, there are several things to pay attention to.

• Arrays will never be automatically boxed or unpacked. For example, if you have an Integer array int[] x and try to put its address into a variable of type Integer [], the compiler will not allow your program to compile.
• Automatic packing and unpacking also have a certain impact on the performance. That is, code that relies on automatic boxing and unpacking is slower than code that does not use this automatic conversion.
• In addition, the boxed type uses more memory than the initial type. On most modern compilers, your code must hold a 64bits reference to an Object, and each Object also requires a 64 bit overhead to store the dynamic type of the Object, etc.

Widening

In addition to automatic packing and unpacking, Java also has automatic widening. For example, there is a function whose value is double:

public static void blahDouble(double x) {
   System.out.println("double: " + x);
}

But when we pass in int

int x = 20;
blahDouble(x);

Java will think that int is narrower than double, so it will automatically widen int
Conversely, if you want to convert a wider initial type to a narrower one, you need to cast it

public static void blahInt(int x) {
   System.out.println("int: " + x);
}
double x = 20;
blahInt((int) x);

2.Immutability invariant

Invariant means that once a variable is assigned, no operation can change it. Use the final keyword to specify a variable as an invariant
For example, in Java, integer and String are invariants, even though String has many built-in functions, such as

• charAt(int i): get the ith item of the string
• compareTo(String s): compares the dictionary order with another string
• concat(String s): link another string
• split(String r): splits a string

The above functions do not make destructive modifications to the original string, but generate a new copy of the string and return it. The value of the original string will not be affected. For example, the following Data class is an invariant:

public class Date {
    public final int month;
    public final int day;
    public final int year;
    private boolean contrived = true;
    public Date(int m, int d, int y) {
        month = m; day = d; year = y;
    }
}

This class is immutable. When you instantiate Date(), you can no longer change the value of any of its properties.
be careful:

• Declaring a reference as final does not make the object pointed to by the reference immutable! For example, consider the following code snippet:

   public final ArrayDeque<String>() deque = new ArrayDeque<String>();

  The reference deque cannot be re assigned, that is, deque cannot point to a new ArrayDeque, but the value of the ArrayDeque pointed to by deque can be changed, such as addLast(),addFirst(), etc

• It is not necessary to declare final. Sometimes declaring a variable as private can prohibit external access and modification of the variable, but using the reflection API, you can even change the private variable! Our concept of invariance is based on the fact that we do not use this special function.

3.ArrayMap

In this section, we will create our own ArrayMap instead of using the built-in Map in Java. The data structure is array and generic type is used:
Firstly, the interface of Map61B is given:

package Map61B;
import java.util.List;

public interface Map61B<K, V> {
    /* Returns true if this map contains a mapping for the specified key. */
    boolean containsKey(K key);

    /* Returns the value to which the specified key is mapped. No defined
     * behavior if the key doesn't exist (ok to crash). */
    V get(K key);

    /* Returns the number of key-value mappings in this map. */
    int size();

    /* Associates the specified value with the specified key in this map. */
    void put(K key, V value);

    /* Returns a list of the keys in this map. */
    List<K> keys();
}

Then we create an Array Map to implement the interface, which contains the following member variables:

package Map61B;

import java.util.List;
import java.util.ArrayList;

public class ArrayMap<K, V>implements Map61B<K, V> {
    private K[] keys;
    private V[] values;
    int size;

}

1. Constructor:

    public ArrayMap() {
        keys = (K[]) new Object[10];
        values = (V[]) new Object[10];
        size = 0;
    }

1. keyIndex(K key): query the key key. If it exists, return the subscript of the key in the keys [] array. If it does not exist, return - 1

    private int keyIndex(K key) {
        for (int i = 0;i < size; i++) {   
            if (keys[i].equals(key)) {
                return i;
            }
        }
        return -1;
    }

Note that the initialized keys [] have 10 sizes (more allowed), and the loop terminates with I < size instead of keys Length is because there are some null spaces in the keys [] array. We only need to compare the size of the actually added keys, and those null values do not need to be compared
Secondly, why not use keys[i] == key? Instead, use keys [i] equals(key)
Because = = actually means that two referenced memory boxes point to the same Object, that is, whether they point to the same Object, rather than simply equal values
equals(Object o) compares whether the values of two objects are equal. Whenever we use the keyword new to create an Object, it will create a new memory location for the Object, for example:

// Java program to understand
// the concept of == operator

public class Test {
    public static void main(String[] args)
    {
        String s1 = "HELLO";
        String s2 = "HELLO";
        String s3 = new String("HELLO");

        System.out.println(s1 == s2); // true
        System.out.println(s1 == s3); // false
        System.out.println(s1.equals(s2)); // true
        System.out.println(s1.equals(s3)); // true
    }
}

more detail you can see

1. containKey(K key): whether there is a key. If yes, return true; if no, return false

    public boolean containsKey(K key) {
        int index = keyIndex(key);
        return index > -1;
    }

2. put(K key, V value): add a key value pair < key, value > to the Map. If the key already exists, directly Map the key to value. If it does not exist, add a key value pair at the end of the Map (each addition is continuous and uninterrupted)

    public void put(K key,V value) {
        int index = keyIndex(key);
        if (index == -1) {
            keys[size] = key;
            values[size] = value;         
            size = size + 1;
        } else {
            values[index] = value;
        }
    }

3. get(K key): returns the value corresponding to the key

    public V get(K key) {
        int index = keyIndex(key);
        return values[index];
    }

4. size(): returns the total number of key value pairs in the Map

    public int size() {
        return size;
    }

5. key(): returns all existing keys in the Map in the form of List

    public List<K> keys() {
        List<K> keylist = new ArrayList<>();
        for (int i = 0;i < keys.length; i++) {
            keylist.add(keys[i]);
        }
        return keylist;
    }

So far, we have completed all method s in ArrayMap and tested them in main():

    public static void main(String[] args) {
        ArrayMap<String, Integer> m = new ArrayMap<String, Integer>();
        m.put("horse", 3);
        m.put("fist", 6);
        m.put("house", 9);
    }

The results are as follows:

4.ArrayMap and Autoboxing Puzzle

If you write down the following test:

@Test
public void test() { 
    ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();
    am.put(2, 5);
    int expected = 5;
    assertEquals(expected, am.get(2));
}

Then you will get a compilation error message:

$ javac ArrayMapTest.java
ArrayMapTest.java:11: error: reference to assertEquals is ambiguous
    assertEquals(expected, am.get(2));
    ^
    both method assertEquals(long, long) in Assert and method assertEquals(Object, Object) in Assert match

The error message says that our call to assertEquals() is ambiguous, and both (long,long) and (Object,Object) calls are possible. Why is this caused?
Because calling am Get (2) actually returns Integer type, while expected is int type. In fact, our call is

assertEquals(int,Integer)

Related to the automatic conversion of Java, the steps from assertEquals(int,Integer) to assertEquals(long,long) are

• int widening to long
• Integer(am.get(2)) is int for automatic unpacking and long for int widening

The steps to change from assertEquals(int,Integer) to assertEquals(Object,Object) are

• int auto boxing to Integer

Both conversions are possible, so the compiler will not pass, and one solution is to cast

assertEquals((Integer) expected, am.get(2));

5. Generic methods

Consider the following get() method in ArrayMap above:

    public V get(K key) {
        int index = keyIndex(key);
        return values[index];
    }

In fact, there is a bug. Assuming that the key does not exist, keyIndex(key) will return - 1, and calling return values[-1] will cause ArrayIndexOutOfBoundException
So now we add a class MapHelper to solve this problem. The MapHelper contains two static methods:

• get(Map61B, key): returns the value corresponding to the key in the map. If it does not exist, it returns null
• maxKey(Map61B): returns the maximum value of all keys in the ArrayMap

Let's first try to write get(). Suppose we write this in order to adapt the key value pair < "horse", 3 > and so on:

    public static Integer get(Map61B<String, Integer>sim, String key) {
        return null;
    }

Obviously, it is inappropriate, because Map61B is actually a generic Map, which is not only applicable to < string, integer >, so how to make get() suitable for all types of key value pairs? Maybe you will imitate the get() method of ArrayMap and write it as

    public static V get(Map61B<K, V>sim, K key) {
        return null;
    }

However, the compiler will report errors because the compiler does not know what K and V stand for. Consider our previous skills by adding generics to the class header:

public class MapHelper <K,V>

The compiler error in the previous step disappeared, but how to change K and V to the type we need? Its working method is to instantiate MapHelper and pass parameters of packing type to it

MapHelper<String, Integer> m = new MapHelper<>();

We don't want to use the get() method in this way, so how to pass type parameters by avoiding instantiating generic classes?

That is, using generic methods, this time we will not add < > generics to the class header declaration, but before the return type of the method

public static <K,V> V get(Map61B<K,V> map, K key) {
    if map.containsKey(key) {
        return map.get(key);
    }
    return null;
}

Call example:

ArrayMap<Integer, String> isMap = new ArrayMap<Integer, String>();
System.out.println(mapHelper.get(isMap, 5));

You do not need to explicitly declare the specific types of < K, V > of the get() method. Java can automatically recognize that isMap is of < integer, string > type