Ligh0x74's Blog

2023-10-09发表2025-01-18更新语言 / Java4 分钟读完 (大约536个字)

JDK-8299339 : HashMap merge and compute methods can cause odd resizing pathologies

贴一下去年发现的 Bug，嘿嘿。

导致 Bug 的示例代码如下：

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>(2);

        map.merge(1, 1, Integer::sum);
        map.merge(2, 1, Integer::sum);

        map.forEach((k, v) -> {
            map.merge(k, -1, Integer::sum);
            System.out.println(k);
        });
    }
}

Java Bug DataBase 链接，里面比较详细的讨论了发生的问题，由于当时急着发出去，我的评论有点乱，而且是中文翻译为英文的，有点拉。

今天重新回顾一下 Bug，顺便简单解释一下。上述代码的输出为 2，期望输出是 2 和 1（顺序不重要）。问题在于，在两次 merge 之后，map 包含的元素数量 2 已经超过扩容阈值 1，下一次扩容发生在迭代中，导致不正确的输出。具体来说，在 resize 方法中，有 oldTab[j] = null; 操作，即转移元素到新数组时，会将旧数组的所有元素置为 null，从而旧数组的迭代器扫描不到剩余的元素。总的来说，即使在遍历的过程中，没有发生结构性的修改，在特定情况下使用 merge 方法修改 HashMap 依然会导致问题。特定情况是指，在遍历之前 HashMap 的包含的元素数量超过扩容阈值，然后在遍历的过程中使用 merge 方法。

ORACLE 的内部人员首先说明，由于调用 Map 上的方法可能产生破坏迭代的副作用，所以不建议在迭代的过程中调用 Map 上的方法，特别是具有副作用的方法，建议重写代码避免这种情况。然后提到 merge 方法确实有问题，即元素数量超过阈值也没有立即扩容，它和 put 方法的实现不同。评论中还列出其他具有类似副作用的方法，以及其他产生副作用的情况，详细看链接。

2023-08-12发表2023-08-12更新语言 / C++几秒读完 (大约66个字)

禁用编译器扩展以确保程序符合 C++ 标准

g++ 编译器可以通过添加 -pedantic-errors 选项来禁用扩展：

1	g++ main.cpp -pedantic-errors

程序示例：

int main() {
    int n = 1024;
    int a[n];
    return 0;
}

运行结果：

1 2	// 禁用前正常运行 error: ISO C++ forbids variable length array 'a' // 禁用后报错

2023-07-30发表2024-09-02更新语言 / Java1 分钟读完 (大约166个字)

Java 快速输入输出

输入

Scanner 会使用正则表达式解析输入，而 BufferedReader 直接读取输入，所以 Scanner 更慢。

输出

System.out（类型为 PrintStream）的 autoFlush 属性默认为 True，所以 System.out 更慢。

模板

class FastIO extends PrintWriter {
    private BufferedReader br;
    private StringTokenizer st;

    public FastIO() {
        this(System.in, System.out);
    }

    public FastIO(InputStream in, OutputStream out) {
        super(out);
        br = new BufferedReader(new InputStreamReader(in));
    }

    public FastIO(String input, String output) throws FileNotFoundException {
        super(output);
        br = new BufferedReader(new FileReader(input));
    }

    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}

测试

INOUTEST - Enormous Input and Output Test

输入

输出

模板

测试

链接

分类

最新文章

归档

标签

链接