包装类的注意点

前言：

今天在刷leetcode76时候遇到一个奇怪的bug，发现是一个常见的笔试考题

补充：

2021.05.03 ：原理其实就是一个享元模式的应用，关于享元模式在并发编程笔记中有详细解释

1. bug

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for(int i = 0; i < t.length(); i++) need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);

        int left = 0, right = 0;
        int valid = 0;
        int start = 0, length = Integer.MAX_VALUE;
        while(right < s.length()){
            char c = s.charAt(right);
            if(need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                if(need.get(c) == window.get(c)){
                    valid++;
                } 
            }
            right++;

            
            while(valid == need.size()){
                
                if(right - left < length){
                    start = left;
                    length = right - left;
                }

                c = s.charAt(left);
                if(need.containsKey(c)){
                    if(window.get(c) == need.get(c)){
                        valid--;
                    } 
                    window.put(c, window.get(c) - 1);
                }
                left++;
            }
        }

        return length == Integer.MAX_VALUE ? "" : s.substring(start, start + length);

    }
}

本题是滑动窗口的典型题目，但是我发现，valid在字符串较大的实例总是不能自增。

也就是在14行和30行的window.get(c) == need.get(c)判断始终不成立

2. Integer源码分析

问题出在Integer包装类上，因为我们在hashmap中只能存放包装类，会把我们put的int类型自动装箱

我们可以看一下包装类的代码。

自动装箱调用valueOf方法

public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

IntegerCache 的源码如下

private static class IntegerCache {
    static final int low = -128;
    static final int high;
    static final Integer cache[];

    static {
        // high value may be configured by property
        int h = 127;
        String integerCacheHighPropValue =
            sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
        if (integerCacheHighPropValue != null) {
            try {
                int i = parseInt(integerCacheHighPropValue);
                i = Math.max(i, 127);
                // Maximum array size is Integer.MAX_VALUE
                h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
            } catch( NumberFormatException nfe) {
                // If the property cannot be parsed into an int, ignore it.
            }
        }
        high = h;

        cache = new Integer[(high - low) + 1];
        int j = low;
        for(int k = 0; k < cache.length; k++)
            cache[k] = new Integer(j++);

        // range [-128, 127] must be interned (JLS7 5.1.7)
        assert IntegerCache.high >= 127;
    }

    private IntegerCache() {}
}

观察源码，我们可以发现，在[IntegerCache.low, IntegerCache.high]之间的int类型在装箱后放在IntegerCache.cache数组里面的，所以在此范围之间的Integer的引用是相同的，所以在[-127, 128]范围==的判断能够成立，而超过之后==判断失效。

补充：Double 和 Float 没有缓存机制，都是直接返回新的对象；Integer、Short、Byte、Character 有缓存机制

3. debug代码

那么我们只要拆箱比较就好了，Integer转int使用Integer类的intValue方法

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for(int i = 0; i < t.length(); i++) need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);

        int left = 0, right = 0;
        int valid = 0;
        int start = 0, length = Integer.MAX_VALUE;
        while(right < s.length()){
            char c = s.charAt(right);
            if(need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                // debug
                if(need.get(c).intValue() == window.get(c).intValue()){
                    valid++;
                } 
            }
            right++;

            while(valid == need.size()){
                
                if(right - left < length){
                    start = left;
                    length = right - left;
                }

                c = s.charAt(left);
                if(need.containsKey(c)){
                    // debug
                    if(window.get(c).intValue() == need.get(c).intValue()){
                        valid--;
                    } 
                    window.put(c, window.get(c) - 1);
                }
                left++;
            }
        }

        return length == Integer.MAX_VALUE ? "" : s.substring(start, start + length);

    }

}

4. 相关经典笔试题

这里参考了帖子^[1]

第一题

Integer a = 10;
Integer b = 20;
Integer c = 30;
Integer d = 30;
Integer e = 300;
Integer f = 300;
Integer g = a + b;

c == d;
e == f;
c == g;
c == (a + b);
c.equals(a + b);

结果：true、false、true、true、true

第三个：由于运用了算术运算符(+)，因此右边的算式在进行计算之前会先调用 intVal() 方法进行拆箱，在进行相加，然后得到的结果30之后，由于前面是 Integer g，因此还会再调用 valueOf() 方法进行装箱。由于此时 cache() 数组中已经有了 30 了，因此直接指向缓存池中的 30 这个 Integer 对象。此时 c == g 比较的还是对象的地址是否相同

第四个：由于右边是 a+b，包含算术运算，因此会调用 intVal() 方法，将左边的 c 进行拆箱，之后又分别对 a 和 b 进行拆箱，即一共调用了三次拆箱过程，最后比较的是数值大小，而不是地址

第五个：通过 equals 的源码看到，传入的参数需要是一个对象，这就意味着，和 equals 比较的时候，一定是装完箱之后的结果a + b 的时候，a 和 b 各自执行 intVal() 方法进行拆箱，完成相加的计算之后，再对计算出的结果执行 valueOf() 方法进行装箱，此时再传入 equals 方法进行比较。equals 比较两个对象的时候，直接比较两个值拆箱之后的结果，即比较的是数值，本例中两个数值相同，所以输出为 true

public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
}

第二题

Integer a = 10;
Integer b = 20;
Long g = 30L;
Long h = 20L;

g == (a + b);
g.equals(a + b);
g.equals(a + h);

结果：true、false、true

和上面一样，同样是使用拆箱，第一题比较的拆完箱之后的值，但是需要注意的是，Integer 类型调用 Integer.valueOf 进行拆箱，而 Long 类型调用 Long.valueOf 进行拆箱

最后一个结果是 true，因为 a + h 会使小的精度转为大的精度，最终的 30 是 Long 类型的，因此结果是 true

第三题

Double i1 = 100.0;
Double i2 = 100.0;
Double i3 = 200.0;
Double i4 = 200.0;

i1 == i2
i3 == i4

结果：false、false

Double没有缓存机制

第四题

Boolean b1 = false;
Boolean b2 = false;
Boolean b3 = true;
Boolean b4 = true;

b1 == b2
b3 == b4
b1 == b3

结果：true、true、false

为什么会这样呢？看一下 Boolean 的 valueOf() 的源代码

1
2
3

public static Boolean valueOf(boolean b) {
    return (b ? TRUE : FALSE);
}

其中的 TRUE 和 FALSE，代表两个静态成员属性

1
2
3

public static final Boolean TRUE = new Boolean(true);

public static final Boolean FALSE = new Boolean(false);

因此可以知道了，每次传入的 true 或 false，都是指向同一个 Boolean 对象，因此他们的引用肯定相同了

参考资料

https://blog.csdn.net/babycan5/article/details/81942230 ↩
leetcode No.76 ↩

Java 基础

Java

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Redis分布式锁的深入理解 Previous

常见攻击HTTP协议的五大方式 Next

包装类注意点