关于java:cs61b-week5-Generics-Autoboxing

正如咱们后面所学的，咱们能定义泛型类，比方 LinkedListDeque<Item> 和 ArrayDeque<Item>
当咱们想去实例化一个应用泛型类的对象时，则必须把泛型替换为一种具体的类型。
回忆一下，Java 有 8 种初始类型，初始类型之外的其余类型均是援用类型。
对于泛型而言，咱们并不能将 <> 中的 generic type 替换为初始类型，比方:
ArrayDeque<int> 是一种语法错误，相同，咱们应用 ArrayDeque<Integer>
对于每一种初始类型，其都关联一种援用类型，这些援用类型叫做 ”wrapper classes”（装箱类）

咱们假如应用泛型时必须作手动转换，行将初始类型转换为泛型

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();}
}

如上的代码应用起来有一点宜人。侥幸的是，Java 可能主动地做隐式转换，因而，以上代码咱们只需这样写:

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 可能进行主动装箱与拆箱,
假如咱们传递一个初始类型的变量，然而 Java 期待的是装箱类型，则会主动装箱，调用 blah(new Integer(20))

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

假如咱们传递一个装箱类型的变量，但 Java 期待的是初始类型，则会主动拆箱

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

正告 :
在谈到主动装箱和解箱时，有几件事须要留神。

数组永远不会被主动装箱或主动拆箱，比方你有一个整数数组 int[] x，并试图将其地址放入 Integer[] 类型的变量，编译器将不容许你的程序编译。
主动装箱和拆箱对性能也肯定的影响。也就是说，依赖主动装箱和拆箱的代码会比不应用这种主动转换的代码慢。
此外，装箱类型比初始类型应用更多的内存。在大多数古代编译器上，你的代码必须持有对 Object 的 64bits 援用，且每个 Object 还须要 64 位的开销，用来存储 Object 的动静类型等等。

除了主动装箱与拆箱之外，Java 还有主动加宽，比方有一个函数, 传值是double:

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

然而当咱们传入 int 时

int x = 20;
blahDouble(x);

Java 会认为 int 比double窄，因而会将 int 主动加宽
反之，如果想要将更宽的初始类型转换为更窄的，须要强制类型转换

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

不变量是指某一变量一旦进行赋值操作之后，其任何操作都不能使之被扭转，应用 final 关键字去指定一个变量为不变量
例如，在 Java 中，Integer,String 是不变量，即便 String 内置很多函数，例如

charAt(int i): 获取字符串第 i 项
compareTo(String s): 与另一字符串比拟，字典序
concat(String s)：链接另一字符串
split(String r): 宰割字符串

以上函数均不是对原字符串做破坏性的批改，而是生成一个新的字符串正本返回，原字符串的值并不会受到影响，例如以下 Data 类则是一个不变量:

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;}
}

这个类是不可变的, 当实例化 Date()后，再也无奈更改其任何属性的值。
留神：

将援用申明为 final 并不会使援用指向的对象不可变！例如，思考以下代码片段：
```
 public final ArrayDeque<String>() deque = new ArrayDeque<String>();
```
援用 deque 不能被从新赋值，也就是不能再让 deque 指向一个新的 ArrayDeque，然而 deque 所指向的 ArrayDeque 的值能够扭转，比方 addLast(),addFirst()等等
申明 final 并非必须的，有时候申明变量为 private 一样能够做到禁止内部拜访与批改该变量, 然而应用 reflection API，甚至能够对公有变量进行更改！咱们的不变性概念是基于咱们没有应用这个非凡性能。

本节咱们将发明一个属于咱们本人的 ArrayMap，而非应用 Java 内置的 Map, 根据的数据结构是数组，并且应用泛型:
首先给出 Map61B 的接口:

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();}

而后咱们创立一个 Array Map 去 implements 该接口, 其中蕴含的成员变量如下:

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;

}

构造函数:

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

keyIndex(K key): 查询键 key，如果存在，返回 key 在 keys[]数组中的下标，不存在返回 -1

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

留神咱们初始化的 keys[]有 10 个大小 (容许更多), 循环终止为 i < size，而非 keys.length 是因为 keys[] 数组外面存在一些为 null 的空位，咱们只需比拟理论已增加的 key 的 size 即可，那些 null 值不用比拟
其次，为什么不应用 keys[i] == key? 而应用 keys[i].equals(key)
因为 == 实际上是指 两个援用的内存盒指向的 Object 雷同 ，即是否指向同一个 Object, 而非单纯的值相等
而 equals(Object o)则比拟 两个 Object 的值是否相等，每当咱们应用关键字 new 创立一个 Object 时，它都会为该对象创立一个新的内存地位, 举例:

// 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

containKey(K key): 是否存在键 key，是返回 true，否返回 false

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

put(K key, V value): 向 Map 中新增键值对 <key,value>, 如果已存在 key，则间接将 key 映射至 value，如果不存在则在 Map 开端新增键值对(每次增加均为间断，非间断)

 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;
     }
 }

get(K key)：返回键 key 所对应的值 value

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

size(): 返回 Map 中总的键值对的数目
```
 public int size() {return size;}
```

key(): 以 List 模式返回 Map 中所有存在的 key

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

至此，咱们实现了 ArrayMap 中的所有 method，在 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);
    }

失去后果如下:

如果你写下如下测试:

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

那么你将会失去编译谬误的信息:

$ 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

报错信息说咱们对 assertEquals()的调用不置可否，其中 (long,long) 和(Object,Object)型的调用均有可能，为何会造成这样的起因呢？
因为调用 am.get(2)实际上是返回 Integer 型，而 expected 是 int 型，实际上咱们的调用是

assertEquals(int,Integer)

与 Java 的主动转换无关，从 assertEquals(int,Integer)变成 assertEquals(long,long)的步骤是

int 加宽为 long
Integer(am.get(2))主动拆箱为 int ,int 加宽为 long

从 assertEquals(int,Integer)变成 assertEquals(Object,Object)的步骤是

int 主动装箱为 Integer

两种转换均有可能，因而编译器不会通过，解决办法之一则是强制类型转换

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

思考以下咱们下面 ArrayMap 外面的 get()办法:

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

其实存在 bug, 假如 key 不存在则 keyIndex(key)会返回 -1，再调用 return values[-1]则会引起 ArrayIndexOutOfBoundException
因而当初咱们增加一个 class MapHelper 去解决这个问题，MapHelper 中蕴含两个 static 办法:

get(Map61B, key): 返回在 map 中 key 对应的 value，如果不存在, 返回 null
maxKey(Map61B): 返回 ArrayMap 中所有 keys 的最大值

咱们首先来尝试写一下 get()，假如咱们为了适配上文中的键值对 <“horse”, 3> 等等，这样写:

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

显然是不适合的，因为 Map61B 实际上是泛型 Map，他并不是只实用于 <String, Integer>，那么如何让 get()适宜所有类型的键值对呢？兴许你会模拟 ArrayMap 的 get()办法，写成

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

然而编译器会报错，因为编译器并不知道 K, V 代表什么，思考咱们之前的技巧，通过给 class header 增加泛型:

public class MapHelper <K,V>

上一步的编译器报错隐没了，然而如何将 K,V 改成咱们须要的类型呢？其工作形式是须要去实例化 MapHelper，并向其中传递装箱类型的参数

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

咱们并不心愿通过这样的形式去应用 get()办法，那么如何以防止实例化泛型类的形式去传递类型参数呢?

也就是应用 泛型办法 ，这次咱们不再去类头申明增加 <> 泛型，而是在 办法的返回类型之前 增加

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

调用举例:

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

你并不需要显示地申明 get()办法的 <K, V> 的具体类型，Java 可能自动识别出 isMap 是 <Integer,String> 类型

关于java:cs61b-week5-Generics-Autoboxing

1. 主动装箱与拆箱

Widening

2.Immutability 不变量

3.ArrayMap

4.ArrayMap and Autoboxing Puzzle

5. 泛型办法