良葛格的 Blog

炒一下泛型的冷飯

考慮你要製作一個節點物件，節點可內含的物件可以指定其型態（就如同List、Set等內含元素可指定型態），你可以使用泛型語法如下進行定義：

class Node<T> {
    Node<T> next;
    private T value;
    T getValue() {  
        return value;
    }
    
    void setValue(T value) {
        this.value = value;
    }
}

你使用<>括住一個代表型態的名稱，之後就可以先使用該名稱來宣告變數，名稱所代表的型態是未定的，你要在建立物件時指定型態，例如指定型態為String：

public class Main {
    public static void main(String[] args) {
        Node<String> first = new Node<String>();
        first.setValue("Justin");
        first.next = new Node<String>();
        first.next.setValue("momor");
    }
}

在上例中，將Node定義中的T指定為String，所以getValue()傳回String，而setValue()方法可以接受String，value的型態也是String。你也可以指定別的型態：

public class Main {
    public static void main(String[] args) {
        Node<Integer> first = new Node<Integer>();
        first.setValue(100);
        first.next = new Node<Integer>();
        first.next.setValue(200);
    }
}

在上例中，將Node定義中的T指定為Integer，所以getValue()傳回Integer，而setValue()方法可以接受Integer，value的型態也是Integer。泛型也可以用在方法定義上，例如在多維矩陣轉一維矩陣的例子中，若想讓方法更一般化，則可以如下撰寫：

class ArrayUtil {
    @SuppressWarnings(value={"unchecked"})
    public static <T> T[] toOneByColumn(T[][] array) {
        T[] arr = (T[]) Array.newInstance(
                           array[0].getClass().getComponentType(), 
                           array.length * array[0].length);
        for(int row = 0; row < array.length; row++) { 
            for(int column = 0; column < array[0].length; column++) { 
                arr[row + column * array.length] = array[row][column]; 
            } 
        }
        return arr;
    }
}

public class Main {
    public static void main(String[] args) {
        Integer[][] arr1 = {
                               {1, 2, 3},
                               {4, 5, 6}
                           };
        for(Integer i : ArrayUtil.<Integer>toOneByColumn(arr1)) {
            System.out.println(i);
        }
        
        String[][] arr2 = {
                              {"one",  "two",  "three"},
                              {"four", "five", "six"}
                          };
        for(String s : ArrayUtil.<String>toOneByColumn(arr2)) {
            System.out.println(s);
        }
    }
}

泛型也可以用來宣告不定長度引數，例如：

public class Main {
    public static void main(String[] args) {
        Main.<Integer>show(1, 2);
        Main.<String>show("one", "two", "three");
    }
    
    static <T> void show(T... values) {
        for(T v : values) {
            System.out.println(v);
        }
    }
}

在定義介面時，也可以使用泛型，例如在神奇的 foreach 看過的 java.util.Iterator[E]：

package java.util;

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

Iterator[E]可以在使用時宣告A的型態，一個在神奇的 foreach 看過的例子如下：

import java.util.*;
public class Some implements Iterable<String>{
    private String[] strs;
    private int index;
    public Some(int length) {
        strs = new String[length];
    }
    public void add(String element) {
        strs[index++] = element;
    }
    public Iterator<String> iterator() {
        return new Iterator<String>() {
                   private int index;
                   public boolean hasNext() {
                       return index < strs.length;
                   }
                   public String next() {
                       return strs[index++];
                   }
                   public void remove() {
                       strs[index] = null;
                   }
               };
    }
}
在定義泛型時，可以定義型態的邊界（Bound）。例如：
class Animal {}
class Human extends Animal {}
class Toy {}

class Duck<T extends Animal> {}

public class Main {
    public static void main(String[] args) {
        Duck<Animal> ad = new Duck<Animal>();
        Duck<Human> hd = new Duck<Human>();
        Duck<Toy> hd = new Duck<Toy>();  // 編譯錯誤
    }
}

在上例中，使用 extends 定義指定泛型真正型態時，必須是Animal的子類，你可以使用Animal與Human來指定型態，但不可以使用Toy指定型態，因為Toy不是Animal的子類。

一個實際應用可以用 快速排序法 中的例子來說明：
class Sort {
    public void quick(int[] number) {
        sort(number, 0, number.length-1);
    }
    
    private void sort(int[] number, int left, int right) {
        if(left < right) { 
            int q = partition(number, left, right); 
            sort(number, left, q-1); 
            sort(number, q+1, right); 
        } 

    }

    private int partition(int number[], int left, int right) {  
        int i = left - 1; 
        for(int j = left; j < right; j++) { 
            if(number[j] <= number[right]) { 
                i++; 
                swap(number, i, j); 
            } 
        } 
        swap(number, i+1, right); 
        return i+1; 
    } 

    private void swap(int[] number, int i, int j) {
        int t = number[i]; 
        number[i] = number[j]; 
        number[j] = t;
    }
}

在這個例子中，是以int來示範演算法的實作，如果要讓這個類別更一般化，可以排序任何型態的物件，則該型態必須具備可比較物件大小的方法，一個方式是要求要排序的物件實作java.lang.Comparable<T>介面。所以可以修改類別定義如下：
class Sort<T extends Comparable<T>> {
    void quick(T[] array) {
        sort(array, 0, array.length-1);
    }
    
    private void sort(T[] array, int left, int right) {
        if(left < right) { 
            int q = partition(array, left, right); 
            sort(array, left, q-1); 
            sort(array, q+1, right); 
        } 

    }

    private int partition(T[] array, int left, int right) {  
        int i = left - 1; 
        for(int j = left; j < right; j++) { 
            if(array[j].compareTo(array[right]) <= 0) {
                i++; 
                swap(array, i, j); 
            } 
        } 
        swap(array, i+1, right); 
        return i + 1; 
    } 

    private void swap(T[] array, int i, int j) {
        T t = array[i]; 
        array[i] = array[j]; 
        array[j] = t;
    }
}

只要你定義的類別實作了java.lang.Comparable<T>，就可以使用這個類別來進行排序，例如字串就實作了java.lang.Comparable<T>：
public class Main {
    public static void main(String[] args) {
       Sort<String> sort = new Sort<String>();
       String[] strs = {"3", "2", "5", "1"};
       sort.quick(strs);
       for(String s : strs) {
           System.out.println(s);
       }
    }
}
如果你定義了以下的類別：
class Node<T> {
    T value;
    Node<T> next;
    
    Node(T value, Node<T> next) {
        this.value = value;
        this.next = next;
    }
}
如果在以下的例子中：
class Fruit {}
class Apple extends Fruit {
    @Override
    public String toString() {
        return "Apple";
    }
}

class Banana extends Fruit {
    @Override
    public String toString() {
        return "Banana";
    }
}


public class Main {
    public static void main(String[] args) {
        Node<Apple> apple = new Node<Apple>(new Apple(), null);
        Node<Fruit> fruit = apple;  // 編譯錯誤，incompatible types
    }
}
在範例中，apple的型態是Node<Apple>，而fruit的型態為Node<Fruit>，你將apple所參考的物件
給fruit參考，那麼Node<Apple>該是一種Node<Fruit>呢？在上例中編譯器給你的答案為「不是」！

如果B是A的子型態，而Node<B>被視為一種Node<A>型態，則稱Node具有共變性（Covariance）或有彈性的（flexible）。如
果Node<A>被視為一種Node<B>型態，則稱Node具有逆變性（Contravariance）。如果不具共變性或逆變性，則Node是不可變
的（nonvariant）或嚴謹的（rigid）。

Java的泛型不支援共變性，不過可以使用型態通配字元?與extends來宣告變數，使其達到類似共變性，例如：
public class Main {
    public static void main(String[] args) {
        Node<Apple> apple = new Node<Apple>(new Apple(), null);
        Node<? extends Fruit> fruit = apple; // 類似共變性效果
    }
}
一個實際應用的例子是：
public class Main {
    public static void main(String[] args) {
        Node<Apple> apple1 = new Node<Apple>(new Apple(), null);
        Node<Apple> apple2 = new Node<Apple>(new Apple(), apple1);
        Node<Apple> apple3 = new Node<Apple>(new Apple(), apple2);
        
        Node<Banana> banana1 = new Node<Banana>(new Banana(), null);
        Node<Banana> banana2 = new Node<Banana>(new Banana(), banana1);

        show(apple3);
        show(banana2);
    }
    
    static void show(Node<? extends Fruit> n) {
        Node<? extends Fruit> node = n;
        do {
            System.out.println(node.value);
            node = node.next;
        } while(node != null);
    }
}
你的目的是可以顯示所有的水果節點，由於show()方法使用型態通配字元宣告參數，使得n具備類似共變性的效果，因此show()方法就可以顯示Node<Apple>也可以顯示Node<Banana>。

Java的泛型亦不支援逆變性，不過可以使用型態通配字元?與super來宣告變數，使其達到類似逆變性，例如：
public class Main {
    public static void main(String[] args) {
        Node<Fruit> fruit = new Node<Fruit>(new Fruit(), null);
        Node<? super Apple> apple = fruit;
        Node<? super Banana> banana = fruit;
    }
}
一個實際應用的例子如下：
class Fruit {
    int price;
    int weight;
    Fruit(int price, int weight) {
        this.price = price;
        this.weight = weight;
    }
}

class Apple extends Fruit {
     Apple(int price, int weight) {
         super(price, weight);
     }
}

class Banana extends Fruit {
     Banana(int price, int weight) {
         super(price, weight);
     }
}

interface Comparator<T> {
    int compare(T t1, T t2);
}

class Basket<T> {
    private T[] things;
    Basket(T... things) {
        this.things = things;
    }
    void sort(Comparator<? super T> comparator) {
        // 作一些排序
    }
}
籃子（Basket）中可以置放各種物品，並可以傳入一個比較器（Comparator）進行排序。假設你分別在兩個籃子中放置了蘋果（Apple）與香蕉（Banana）：
public class Main {
    public static void main(String[] args) {
        Comparator<Fruit> comparator = new Comparator<Fruit>() {
            public int compare(Fruit f1, Fruit f2) {
                return f1.price - f2.price;
            }
        };
        Basket<Apple> b1 = new Basket<Apple>(
                                 new Apple(20, 100), new Apple(25, 150));
        Basket<Banana> b2 = new Basket<Banana>(
                                 new Banana(30, 200), new Banana(25, 250));
        b1.sort(comparator);
        b2.sort(comparator);
    }
}
現在b1的型態為Basket<Apple>，而b2的型態為Basket<Banana>，你可以如上實作一個水果（Fruit）比較器，比較水果的價格進行排序，這可以同時適用於Basket<Apple>與Basket<Banana>。
在 物件相等性 討論過如何重新定義equals()方法，如果定義類別時使用了泛型，則有幾個地方要注意的，例如：
import java.util.*;

class Basket<T> {
    T[] things;
    Basket(T... things) {
        this.things = things;
    }
    
    @Override
    public boolean equals(Object o) {
        if(o instanceof Basket<T>) {  // 編譯錯誤
            Basket that = (Basket) o;
            return Arrays.deepEquals(this.things, that.things);
        }
        return false;
    }
}

如果你編譯這個程式，會發現以下的錯誤訊息：

illegal generic type for instanceof
if(o instanceof Basket<T>) {

在程式中instanceof對Basket<T>的型態判斷是不合法的，因為Java的泛型所採用的是型態抹除，模式比對時，僅比對Basket型態，不會針對當中的泛型真正之型態進行比對。

如果想要通過編譯，可以使用型態通配字元?：

import java.util.*;

class Basket<T> {
    T[] things;
    Basket(T... things) {
        this.things = things;
    }
    
    @Override
    public boolean equals(Object o) {
        if(o instanceof Basket<?>) {
            Basket that = (Basket) o;
            return Arrays.deepEquals(this.things, that.things);
        }
        return false;
    }
}

現在你可以使用equals()來比較兩個Basket是不是相同了：

public class Main {
    public static void main(String[] args) {
        Basket<Integer> b1 = new Basket<Integer>(1, 2);
        Basket<Integer> b2 = new Basket<Integer>(1, 2);
        Basket<Integer> b3 = new Basket<Integer>(2, 2);
        Basket<String> b4 = new Basket<String>("1", "2");
        System.out.println(b1.equals(b2));       // true
        System.out.println(b1.equals(b3));       // false
        System.out.println(b1.equals(b4));       // false
    }
}

看起來不錯，不過來看看下面這個例子：

public class Main {
    public static void main(String[] args) {
        Basket<String> b1 = new Basket<String>();
        Basket<Integer> b2 = new Basket<Integer>();
        System.out.println(b1.equals(b2)); // true
    }
}

Basket<Integer>與Basket<String>若是視作不同的型態，則b1與b2 應視為不相等，實際上，由於Java採用型態抹除的方式，結果就是認為在這種情況下，b1與b2是相等的。其實這也可以在以下的例子中看到：

public class Main {
    public static void main(String[] args) {
        List<Integer> l1 = new ArrayList<Integer>();
        List<String> l2 = new ArrayList<String>();
        System.out.println(l1.equals(l2));       // true
    }
}

List<Integer>、List<String>是不同的型態，但Java這麼想，l1、l2都是空串列，那它們不就是相等的嗎？這是採取型態抹除的結果。依此類推，Basket<Integer>與Basket<String>是不同的型態沒錯，但你的Basket定義就是比較是不是籃子（Basket<?>），以及實際籃子中放的東西是什麼，現在籃子中沒放東西，所以整個Basket的比較就會是相等的。

以下考慮繼承關係後的equals()、hashCode()定義：

import java.util.*;

class Basket<T> {
    T[] things;
    Basket(T... things) {
        this.things = things;
    }
    
    @Override
    public boolean equals(Object o) {
        if(o instanceof Basket<?>) {
            Basket that = (Basket) o;
            return that.canEquals(this) && 
                   Arrays.deepEquals(this.things, that.things);
        }
        return false;
    }
    
    public boolean canEquals(Object other) {
        return other instanceof Basket<?>;
    }
    
    @Override
    public int hashCode() {
        int sum = 1;
        for(T t : things) {
            sum = sum * 41 + t.hashCode();
        }
        return 41 * sum + things.hashCode();
    }
}

« 在變與不變之間 | Main | JavaScript 函式與 new... »

迴響:

發表迴響:

Search

follow caterpillar at http://twitter.com

良葛格的 Blog