记一次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. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 记一次TreeMap NPE异常