8_泛型.md

泛型

泛型的概念

在集合中存储对象并在使用前进行类型转换是多么的不方便。泛型防止了那种情况的发生。它提供了编译期的类型安全，确保你只能把正确类型的对象放入集合中，避免了在运行时出现ClassCastException。

不使用泛型

/**
 * 这样做的一个不好的是Box里面现在只能装入String类型的元素，今后如果我们需要装入Integer等其他类型的元素，
 * 还必须要另外重写一个Box，代码得不到复用，使用泛型可以很好的解决这个问题。
 */
public class Box {
    private String object;

    public void set(String object) {
        this.object = object;
    }

    public String get(){
        return object;
    }
}

使用泛型

public class  GenericBox<T> {
    // T stands for "Type"
    private T t;
    public void set(T t) { this.t = t; }
    public T get() { return t; }
}

限定通配符和非限定通配符

限定通配符

限定通配符对类型进行了限制。有两种限定通配符：

一种是<? extends T>它通过确保类型必须是T及T的子类来设定类型的上界，

另一种是<? super T>它通过确保类型必须是T及T的父类设定类型的下界。

泛型类型必须用限定的类型来进行初始化，否则会导致编译错误。

非限定通配符
表示了非限定通配符，因为可以用任意类型来替代。

public class BoundaryCharExample {
    //查找一个泛型数组中大于某个特定元素的个数
    public static <T> int countGreaterThan(T[] array,T elem){
        int count = 0;
        for (T e : array) {
            if (e > elem) { // compiler error
                ++count;
            }
        }
        return count;
    }
    /*
    * comliler error:但是这样很明显是错误的，
    * 因为除了short, int, double, long, float, byte, char等原始类型，
    * 其他的类并不一定能使用操作符" > "
    * 解决 --> 使用限定通配符/边界符
    * */
}

使用限定通配符改进

public class BoundaryCharExample2 {
    public static <T extends Comparable<T>> int countGreaterThan(T[] array,T elem){
        //<T extends Comparable<T>>就是通配符，类型必须是 Comparable<T>及其子类
        int count = 0;
        for (T e : array) {
            if (e.compareTo(elem)>0) {
                ++count;
            }
        }
        return count;
    }
}

面试题：List<? extends T> 和List <? super T>之间有什么区别 ?

List<? extends T>可以接受任何继承自T的类型的List，

List<? super T>可以接受任何T的父类构成的List。
例如List<? extends Number>可以接受List或List。

PECS(Producer Extends Consumer Super)原则

PECS原则即Producer Extends,Consumer Super原则

Producer Extends：如果你需要一个只读List，用它来produce T，那么使用? extends T。

Consumer Super：如果你需要一个只写List，用它来consume T，那么使用? super T。

public class GenericExample {
    public static void main(String[] args) {
        List<? extends Fruit> fruits = new ArrayList<Apple>();
        //? extends Fruit表示的是Fruit及其子类
        
        // Compile Error: can't add any type of object:
        //fruits.add(new Apple());
        //fruits.add(new Orange());
        //fruits.add(new Fruit());
        //fruits.add(new Object());
        //fruits.add(null); // Legal but uninteresting
    }
}

Compile Error: can't add any type of object: 从编译器的角度去考虑。因为List<? extends Fruit> fruits它自身可以有多种含义：因为List<? extends Fruit> fruits它自身可以有多种含义(参照下面的代码 GenericReading.java)：

List<? extends Fruit> fruits = new ArrayList<Fruit>();

List<? extends Fruit> fruits = new ArrayList<Apple>();

List<? extends Fruit> fruits = new ArrayList<Orange>();

// 这里Apple和Orange都是Fruit子类

当我们尝试add一个Apple的时候，fruits可能指向new ArrayList();

当我们尝试add一个Orange的时候，fruits可能指向new ArrayList();

当我们尝试add一个Fruit的时候，这个Fruit可以是任何类型的Fruit，

而fruits可能只想某种特定类型的Fruit，编译器无法识别所以会报错。

所以对于实现了<? extends T>的集合类只能将它视为 Producer 向外提供元素（只能读）, ，而不能作为 Consumer 来向外获取元素。

/**
 * 对于实现了<? extends T>的集合类只能将它视为Producer向外提供(get)元素,
 * 而不能作为Consumer来对外获取(add)元素。
 */
public class GenericReading {
    private List<Apple> apples = Arrays.asList(new Apple());
    private List<Fruit> fruit = Arrays.asList(new Fruit());

    private class Reader<T>{ //Reader<T> 是自定义的泛型类
         /*T readExact(List<T> list){ 
             return list.get(0);
         }*/
        T readExact(List<? extends T> list){// 使用通配符来解决这个问题
            // ? extends T 表示 T 及 T 的子类
            return list.get(0); //TODO :get()方法
        }
    }

    @Test
    public void test(){
        Reader<Fruit> fruitReader=new Reader<Fruit>();
        //Fruit f=fruitReader.readExact(apples);
        // 使用 readExact(List<T> list)  
        // Errors: List<Fruit> cannot be applied to List<Apple>.
        
        Fruit f=fruitReader.readExact(apples);//正确
        System.out.println(f);
    }
}

/**
 *
使用super的坏处是以后不能get容器里面的元素了，
 原因很简单，我们继续从编译器的角度考虑这个问题，
对于List<? super Apple> list，它可以有下面几种含义：
List<? super Apple> list = new ArrayList<Apple>();
List<? super Apple> list = new ArrayList<Fruit>();
List<? super Apple> list = new ArrayList<Object>();
当我们尝试通过list来get一个Apple的时候，可能会get得到一个Fruit，这个Fruit可以是Orange等其他类型的Fruit。
*/
public class GenericWriting {
    private List<Apple> apples = new ArrayList<Apple>();
    private List<Orange> oranges = new ArrayList<Orange>();
    private List<Fruit> fruit = new ArrayList<Fruit>();

    <T> void writeExact(List<T> list, T item) {
        list.add(item); //TODO :这里是 add
    }

    // ? super T 
    // T 及 T 的父类
    <T> void writeWithWildcard(List<? super T> list, T item) {
        list.add(item);
    }

    void func1(){
        writeExact(apples,new Apple());
        writeExact(fruit,new Apple());
    }

    void func2(){
        writeWithWildcard(apples, new Apple());
        writeWithWildcard(fruit, new Apple());
    }

    @Test
    public void test(){
        func1();
        func2();
    }
}

JDK 8 Collections.copy() 源码:

public static <T> void copy(List<? super T> dest, List<? extends T> src) {
        //dest 就是 只写的 List
        //src 就是 只读的 List
        int srcSize = src.size();
        if (srcSize > dest.size())
            throw new IndexOutOfBoundsException("Source does not fit in dest");

        if (srcSize < COPY_THRESHOLD ||
            (src instanceof RandomAccess && dest instanceof RandomAccess)) {
            for (int i=0; i<srcSize; i++)
                dest.set(i, src.get(i));
        } else {
            ListIterator<? super T> di=dest.listIterator();
            ListIterator<? extends T> si=src.listIterator();
            for (int i=0; i<srcSize; i++) {
                di.next();
                di.set(si.next());
            }
        }
    }

类型擦除

类型擦除简介

Java 中的泛型是伪泛型。

类型擦除就是Java泛型只能用于在编译期间的静态类型检查，然后编译器生成的代码会擦除相应的类型信息，这样到了运行期间实际上JVM根本不知道泛型所代表的具体类型。这样做的目的是因为Java泛型是1.5之后才被引入的，为了保持向下兼容。对于这一点，如果阅读 Java 集合框架的源码，可以发现有些类其实并不支持泛型。

public class Node<T> {
    private T data;
    private Node<T> next;
    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }
    public T getData() { return data; }
}

编译器做完相应的类型检查之后，实际上到了运行期间上面这段代码实际上将转换成：

public class Node {
    private Object data; //T转换成Object
    private Node next;
    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
    public Object getData() { return data; }
}

这意味着不管我们声明 Node 还是Node，到了运行期间，JVM 统统视为Node。

解决：

public class Node<T extends Comparable<T>> { 
    //Node<T extends Comparable<T>> 是Comaparable即其子类
    private T data;
    private Node<T> next;
    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }
    public T getData() { return data; }
}

这样编译器就会将 T 出现的地方替换成 Comparable 而不再是默认的 Object 了：

public class Node {
    private Comparable data;
    //将T出现的地方替换成Comparable
    private Node next;
    public Node(Comparable data, Node next) {
        this.data = data;
        this.next = next;
    }
    public Comparable getData() { return data; }
}

类型擦除带来的问题

在 Java 中不允许创建泛型数组

public class Problem1 {
    public static void main(String[] args) {
        // List<Integer> [] listsOfArray = new List<Integer>[2];  
        // compile-time error
        /*
        解析：
        compile-time error,我们站在编译器的角度来考虑这个问题:
        先来看一下下面这个例子：
        Object[] strings = new String[2];
        strings[0] = "hi";   // OK
        strings[1] = 100;    // An ArrayStoreException is thrown.
        字符串数组不能存放整型元素，
        而且这样的错误往往要等到代码**运行的时候**才能发现，编译器是无法识别的。

        接下来我们再来看一下假设Java支持泛型数组的创建会出现什么后果：
        Object[] stringLists = new List<String>[];  
        // compiler error, but pretend it's allowed
        stringLists[0] = new ArrayList<String>();   // OK
        // An ArrayStoreException should be thrown, but the runtime can't detect it.
        stringLists[1] = new ArrayList<Integer>();

        假设我们支持泛型数组的创建，由于运行时期类型信息已经被擦除，
        JVM 实际上根本就不知道 new ArrayList<String>() 和 new ArrayList<Integer>() 的区别。
        * */
        // 可以使用如下语句创建集合数组
        // List<Integer> [] listsOfArray = (List<Integer> [])new Object[2];

        Class c1 = new ArrayList<String>().getClass();
        Class c2 = new ArrayList<Integer>().getClass();
        //因为存在类型擦除，实际上就是c1和c2使用的是同一个.class文件
        System.out.println(c1 == c2); // true
    }
}

对于泛型代码，Java 编译器实际上还会偷偷帮我们实现一个 Bridge Method。

public class Node<T> {
    public T data;
    public Node(T data) { this.data = data; }
    public void setData(T data) {
        System.out.println("Node.setData");
        this.data = data;
    }
}

public class MyNode extends Node<Integer> {
    public MyNode(Integer data) { super(data); }
    public void setData(Integer data) {
        System.out.println("MyNode.setData");
        super.setData(data);
    }
}

看完上面的分析之后，你可能会认为在类型擦除后，编译器会将Node和MyNode变成下面这样：

public class Node {
    public Object data;
    public Node(Object data) { this.data = data; }
    public void setData(Object data) {
        System.out.println("Node.setData");
        this.data = data;
    }
}

public class MyNode extends Node {
    public MyNode(Integer data) { super(data); }
    public void setData(Integer data) { 
        //TODO:子类中的两个setData()方法是重载关系，不是重写关系；因为参数类型不同
        //**要实现多态的话，所调用的方法必须在子类中重写**,
        // 也就是说这里是要重写 setData(Object) 方法,来实现多态
        System.out.println("MyNode.setData");
        super.setData(data);
    }
}

实际上 Java 编译器对上面代码自动还做了一个处理：

public class MyNode extends Node {
        //TODO： Bridge Method generated by the compiler
        public void setData(Object data) {
            setData((Integer) data);
            //TODO:setData((Integer) data)，这样String无法转换成Integer。
            //TODO:所以当编译器提示 unchecked warning 的时候，
            //我们不能选择忽略，不然要等到运行期间才能发现异常。
        }
    
        public void setData(Integer data) {
            System.out.println("MyNode.setData");
            super.setData(data);
        }
}

Java 泛型很大程度上只能提供静态类型检查,然后类型的信息就会被擦除，所以利用类型参数创建实例的做法编译器不会通过。

public static <E> void append(List<E> list) {
    E elem = new E();  // compile-time error
    list.add(elem);
}

使用反射解决:

public static <E> void append(List<E> list, Class<E> cls) throws Exception {
    E elem = cls.newInstance();   
    // TODO:使用反射创建E类型的实例
    list.add(elem);
}

无法对泛型代码直接使用 instanceof 关键字，因为 Java 编译器在生成代码的时候会擦除所有相关泛型的类型信息。

JVM 在运行时期无法识别出ArrayList和ArrayList的之间的区别：

public static <E> void rtti(List<E> list) {
    if (list instanceof ArrayList<Integer>) {  // compile-time error
        // ...
    }
}

ArrayList, ArrayList, LinkedList, ... 和上面一样，有这个问题。

使用通配符解决：

public static void rtti(List<?> list) { //TODO:? 表示非限定通配符
    if (list instanceof ArrayList<?>) {  // OK; instanceof requires a reifiable type(具体的类型)
        // ...
    }
}

泛型的应用

泛型实现 LRU 缓存

LRU(Least Recently Used,最近最久未使用)缓存思想：

(1)固定缓存大小，需要给缓存分配一个固定的大小

(2)每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新

(3)需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存

实现思路：使用LinkedHashMap来实现LRU缓存。

LinkedHashMap的一个构造函数：

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

传入的第三个参数:

accessOrder为true的时候，就按访问顺序对LinkedHashMap排序，

accessOrder为false的时候,就按插入顺序(默认情况)。

当把accessOrder设置为true后（按照访问顺序），就可以将最近访问的元素置于最前面。这样就可以满足上述的(2)。

LinkedHashMap是自动扩容的，当table数组中元素大于Capacity * loadFactor的时候，就会自动进行两倍扩容。但是为了使缓存大小固定，就需要在初始化的时候传入容量大小和负载因子。为了使得到达设置缓存大小不会进行自动扩容，需要将初始化的大小进行计算再传入，将初始化大小设置为(缓存大小 / loadFactor) + 1，这样就可以在元素数目达到缓存大小时，也不会进行扩容了。这样就解决了上述的(1)。

实现

public class LRUCache<K,V> {
    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTORY = 0.75f;
    private LinkedHashMap<K, V> map;;

    public LRUCache(int cacheSize){
        MAX_CACHE_SIZE=cacheSize;
        int capacity=(int)Math.ceil(MAX_CACHE_SIZE/DEFAULT_LOAD_FACTORY)+1;
        //初始化大小设置为(缓存大小 / loadFactor) + 1，这样就可以在元素数目达到缓存大小时，也不会进行扩容
        map=new LinkedHashMap<K,V>(capacity,DEFAULT_LOAD_FACTORY,true){
            //true表示按照访问顺序
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size()>MAX_CACHE_SIZE;
            }
        };
    }

    //为了线程安全所有方法都是同步方法
    public synchronized void put(K key,V value){
        map.put(key,value);
    }

    public synchronized V get(K key){
        return map.get(key);
    }

    public synchronized void remove(K key){
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K,V>> getAll(){
        return map.entrySet();
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        for(Map.Entry<K,V> entry:map.entrySet()){
            sb.append(String.format("%s: %s\n",entry.getKey(),entry.getValue()));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LRUCache<Integer,Integer> lru=new LRUCache<Integer, Integer>(5); 
        //该缓存的容量是5
        lru.put(1, 1);
        lru.put(2, 2);
        lru.put(3, 3);
        System.out.println(lru);
        lru.get(1); //这里访问了 key=1的元素
        //按照访问顺序排序 --> key=1的元素是最新才访问的，所以key=2的元素是最近最久未访问的元素
        System.out.println(lru);

        lru.put(4,4);
        lru.put(5,5);
        lru.put(6,6);
        //容器的容量是5，当超过该容量时，会删除最近最久未访问的元素，也就是删除了key=2的元素
        System.out.println(lru);
    }
}

输出结果：

泛型实现 FIFO 缓存

FIFO设计思路：FIFO就是先进先出，可以使用LinkedHashMap进行实现。

LinkedHashMap 的构造函数：

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

当第三个参数传入为false或者是默认的时候，就可以实现按插入顺序排序，就可以实现FIFO缓存了。

public class FIFOCache<K,V> {
    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTORY = 0.75f;
    private LinkedHashMap<K, V> map;

    public FIFOCache(int cacheSize) {
        this.MAX_CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
        map=new LinkedHashMap<K,V>(capacity,DEFAULT_LOAD_FACTORY,false){
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }

    public synchronized void put(K key,V value){
        map.put(key,value);
    }

    public synchronized V get(K key){
        return map.get(key);
    }

    public synchronized void remove(K key){
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K,V>> getAll(){
        return map.entrySet();
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        for(Map.Entry<K,V> entry:map.entrySet()){
            sb.append(String.format("%s: %s\n",entry.getKey(),entry.getValue()));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        //按照插入顺序
        FIFOCache<Integer,Integer> fifo=new FIFOCache<Integer, Integer>(5);
        fifo.put(1, 1);
        fifo.put(2, 2);
        fifo.put(3, 3);
        System.out.println(fifo);
        fifo.get(1);
        System.out.println(fifo);

        fifo.put(4,4);
        fifo.put(5,5);
        fifo.put(6,6);
        System.out.println(fifo);
    }
}

输出结果：

泛型的实现方式

Java 的泛型是一种伪泛型，编译为字节码时参数类型会在代码中被擦除，单独记录在 Class 文件的 attributes 域内，而在使用泛型处做类型检查与类型转换。

假设参数类型的占位符为T，擦除规则(保留上界)如下：

(1) 擦除后变为 Object

(2) <? extends A> 擦除后变为 A

(3) <？ super A> 擦除后变为 Object

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Expand file tree

泛型

泛型的概念

限定通配符和非限定通配符

PECS(Producer Extends Consumer Super)原则

类型擦除

类型擦除简介

类型擦除带来的问题

泛型的应用

泛型实现 LRU 缓存

泛型实现 FIFO 缓存

泛型的实现方式

Search code, repositories, users, issues, pull requests...

FilesExpand file tree

8_泛型.md

Latest commit

History

8_泛型.md

File metadata and controls

泛型

泛型的概念

限定通配符和非限定通配符

PECS(Producer Extends Consumer Super)原则

类型擦除

类型擦除简介

类型擦除带来的问题

泛型的应用

泛型实现 LRU 缓存

泛型实现 FIFO 缓存

泛型的实现方式

Expand file tree