记一次TreeMap NPE异常

问题

近期在工程中使用TreeMap存储键值对，并重写Comparator的compare方法对key进行排序。

其中key值为账户要素拼接的字符串，形如"用户id-币种名称-记账方向-场景码"。
例如 3283743202_wave_de_wave00123

在批量put一波数据后，再遍历keySet中键值对是否存在，出现了部分NULL的情况，导致先生异常，也算是比较奇怪，因此进行了排查。

直接看代码

Map<String, Object> collectMap = new TreeMap<>(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            long o1Id = Long.parseLong(o1.split("_")[0]);
            long o2Id = Long.parseLong(o2.split("_")[0]);
            if (o1Id == o2Id) {
                return o1.compareTo(o2);
            } else {
                return (int) (o1Id - o2Id);
            }
        }
    });

put数据如下

TreeMap Case 1.png TreeMap Case 2.png TreeMap Case 3.png

其中containKey("3283743202_wave_de_wave00123")的结果为False

原因分析

TreeMap的出现意义在于，可使键值对按一定的规律进行排序，通过自定义Comparator接口实现。

如上数据准备后，各节点按比较器大小排序，debug可以看到key=3283743202_wave_de_wave00123的键值对已经存储下来，但是在查询的时候无法获取。通过观察可以看到，排序后的键值对并非我们的初衷，根据重写的comparator逻辑，应该是主要根据用户ID进行正向排序，但用户ID为3283743202的值却排在79118246之前，违背排序规则。

红黑树.png

同时由于TreeMap的底层实现基于二叉查询树，在查询过程中，从root结点遍历，当前遍历结点与查询键值比较后，再决定left还是right遍历，直至叶子NIL节点。而3283743202在存储数据后出现在最左节点处，但由于3283743202数值偏大，在遍历过程不断往right结点遍历，所以最终找不到与该值相匹配的结果。

原因在于comparator的实现，其中有一行代码为return (int) (o1Id - o2Id);，将long类型数值的差值强转成int类型返回，这就会导致long值的增大导致的值溢出，导致排序逻辑异常。

Java中，long型由8个字节数存储，而int为4个字节存储，其中各自的最高bit位表示正负。
如果long强转为int过程中由于底层存储机制的问题，导致值溢出，可能使得正值变负、负值变正。

基于上述原因，考虑TreeMap的排序逻辑也与键值对存储次序相关，会使得排序结果不一。所以上述3283743202找不到键值对的情况偶现。

优化

将long类型的数值不再通过强转而通过固定1或-1来表示。

Map<String, Object> collectMap = new TreeMap<>(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            long o1Id = Long.parseLong(o1.split("_")[0]);
            long o2Id = Long.parseLong(o2.split("_")[0]);
            if (o1Id == o2Id) {
                return o1.compareTo(o2);
            } (o1Id > o2Id) {
                return 1;
            } else {
                return -1;
            }
        }
    });

总结

1. 类型有风险，强转需谨慎
2. 剖析底层源码，了解实现原理