cs61b week5 -- Generics, Autoboxing java

1.自动装箱与拆箱
正如我们前面所学的，我们能定义泛型类，比如LinkedListDeque和ArrayDeque
当我们想去实例化一个使用泛型类的对象时，则必须把泛型替换为一种具体的类型。
回想一下，Java有8种初始类型，初始类型之外的其他类型均是引用类型。
对于泛型而言，我们并不能将<>中的generic type替换为初始类型，比如:
ArrayDeque是一种语法错误，相反，我们使用ArrayDeque
对于每一种初始类型，其都关联一种引用类型，这些引用类型叫做"wrapper classes"（装箱类）
cs61b week5 -- Generics, Autoboxing
文章图片

我们假设使用泛型时必须作手动转换，即将初始类型转换为泛型

public class BasicArrayList { public static void main(String[] args) { ArrayList L = new ArrayList(); 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 L = new ArrayList(); 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的动态类型等等。

文章图片

Widening 除了自动装箱与拆箱之外，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);

2.Immutability 不变量
不变量是指某一变量一旦进行赋值操作之后，其任何操作都不能使之被改变，使用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() deque = new ArrayDeque();

引用deque不能被重新赋值，也就是不能再让deque指向一个新的ArrayDeque，但是deque所指向的ArrayDeque的值可以改变，比如addLast(),addFirst()等等
声明final并非必须的，有时候声明变量为private一样可以做到禁止外部访问与修改该变量,但是使用reflection API，甚至可以对私有变量进行更改！我们的不变性概念是基于我们没有使用这个特殊功能。

3.ArrayMap
本节我们将创造一个属于我们自己的ArrayMap，而非使用Java内置的Map,依据的数据结构是数组，并且使用泛型:
首先给出Map61B的接口:

package Map61B; import java.util.List; public interface Map61B { /* 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 keys(); }

然后我们创建一个Array Map去implements该接口,其中包含的成员变量如下:

package Map61B; import java.util.List; import java.util.ArrayList; public class ArrayMapimplements Map61B { 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 == operatorpublic 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，则直接将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 keys() { List 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 m = new ArrayMap(); m.put("horse", 3); m.put("fist", 6); m.put("house", 9); }

得到结果如下:

文章图片

4.ArrayMap and Autoboxing Puzzle
如果你写下如下测试:

@Test public void test() { ArrayMap am = new ArrayMap(); 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));

5.泛型方法
考虑以下我们上面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(Map61Bsim, String key) { return null; }

显然是不合适的，因为Map61B实际上是泛型Map，他并不是只适用于，那么如何让get()适合所有类型的键值对呢？也许你会模仿ArrayMap的get()方法，写成

public static V get(Map61Bsim, K key) { return null; }

但是编译器会报错，因为编译器并不知道K, V代表什么，考虑我们之前的技巧，通过给class header添加泛型:

public class MapHelper

上一步的编译器报错消失了，但是如何将K,V改成我们需要的类型呢？其工作方式是需要去实例化MapHelper，并向其中传递装箱类型的参数

MapHelper m = new MapHelper<>();

我们并不希望通过这样的方式去使用get()方法，那么如何以避免实例化泛型类的方式去传递类型参数呢?
也就是使用泛型方法，这次我们不再去类头声明添加<>泛型，而是在方法的返回类型之前添加

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

调用举例:

ArrayMap isMap = new ArrayMap(); System.out.println(mapHelper.get(isMap, 5));

你并不需要显示地声明get()方法的的具体类型，Java能够自动识别出isMap 是类型
Type upper bounds 完成了get()方法，让我们来写一下maxKey()：

public static K maxKey(Map61B map) { List keylist = map.keys(); K largest = map.get(0); for (K k: keylist) { if (k > largest) { largest = k; } } return largest; }

在前面的课程中我们知道，> 操作符只适用于初始类型之间的大小比较，而不适用于比较对象，回忆一下我们上节课的做法，使用方法compareTo()来进行对象之间的比较

public static K maxKey(Map61B map) { List keylist = map.keys(); K largest = map.get(0); for (K k: keylist) { if (k.compareTo(largest)) { largest = k; } } return largest; }

但是直接使用compareTo()肯定是不允许的，原因是该方法在MapHelper中并不存在，需要我们使用Java内置的Comparable接口，在泛型方法上直接extends的做法叫:type upper bounds

public static , V> K maxKey(ArrayMap am) { ... if (k.compareTo(largest) > 0) { ... }

【cs61b week5 -- Generics, Autoboxing】这里也许有人会疑问，为何不使用implements,而是extends，请注意，此处extends的含义与继承关系中的含义不同

文章图片

Just remember, in the context of inheritance, the extends keyword is active in giving the subclass the abilities of the superclass
On the other hand, in the context of generics, extends simply states a fact: You must be a subclass of whatever you're extending. When used with generics (like in generic method headers), extends imposes a constraint rather than grants new abilities.