搜索

同事把实数作为 HashMap 的key，领导发飙了...

全栈架构社区

共 585字，需浏览 2分钟

 ·

2021-12-31 12:36

来源：blog.csdn.net/qq_30219017/article/details/79689492
1.起因
让我关注到这一点的起因是一道题:牛客网上的max-points-on-a-line
题目是这么描述的:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
大意就是给我一些点的X,Y坐标，找到过这些点最多的直线，输出这条线上的点数量
于是我就敲出了以下的代码:
import java.util.HashMap;
import java.util.Map;

//class Point {
//    int x;
//    int y;
//    Point(int a, int b) { x = a; y = b; }
//}

public class Solution {
    public int maxPoints(Point[] points) {
        if (points.length <= 2) {
            return points.length;
        }

        int max = 2;
        for (int i = 0; i < points.length - 1; i++) {
            Map map = new HashMap<>(16);
            // 记录垂直点数; 当前和Points[i]在一条线上的最大点数; 和Points[i]垂直的点数
            int ver = 0, cur, dup = 0;
            for (int j = i + 1; j < points.length; j++) {
                if (points[j].x == points[i].x) {
                    if (points[j].y != points[i].y) {
                        ver++;
                    } else {
                        dup++;
                    }
                } else {
                    float d = (float)((points[j].y - points[i].y) / (double) (points[j].x - points[i].x));
                    map.put(d, map.get(d) == null ? 1 : map.get(d) + 1);
                }
            }

            cur = ver;
            for (int v : map.values()) {
                cur = Math.max(v, cur);
            }

            max = Math.max(max, cur + dup + 1);
        }
        return max;
    }
}
这段代码在天真的我看来是没啥问题的，可就是没办法过，经过长久的排查错误，我写了以下代码加在上面的代码里运行，搜索公众号互联网架构师复“2T”，送你一份惊喜礼包。
public static void main(String[] args) {
    int[][] vals = {{2,3},{3,3},{-5,3}};
    Point[] points = new Point[3];

    for (int i=0; i        points[i] = new Point(vals[i][0], vals[i][1]);
    }

    Solution solution = new Solution();

    System.out.println(solution.maxPoints(points));
}
它输出的，竟然是2
也就是说，它认为(3-3) / (3-2) 和 (3-3) / (-5-2) 不同? 什么鬼…
经过debug,发现上述结果分别是0.0和-0.0
0.0 难道不等于 -0.0 ?
这时我心里已经一阵卧槽了，不过我还是写了验证代码:
System.out.println(0.0 == -0.0);
结果是True，没问题啊，我凌乱了……
一定是java底层代码错了! 我没错……
又是一阵debug,我找到了这条语句:
map.put(d, map.get(d) == null ? 1 : map.get(d) + 1);
我觉得map.get()很有问题, 它的源代码是这样的:
public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
唔，先获得hash()是吧，那我找到了它的hash函数:
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
再来，这里是要比较h 和key的hashCode是吧,那我们去看hashCode()函数
public native int hashCode();
这是一个本地方法，看不到源码了，唔，，那我就使用它看看吧，测试一下不就好了吗,我写了以下的测试代码:搜索公众号互联网架构师复“2T”，送你一份惊喜礼包。
    public static void main(String[] args) {
        System.out.println(0.0 == -0.0);
        System.out.println(new Float(0.0).hashCode() == 
            new Float(-0.0).hashCode());
    }
结果竟然是True和False !!!
这个源头终于找到了, 0.0 和 -0.0 的hashCode值是不同的 !
经过一番修改，我通过了这道题(其实精度也会有问题，应该使用BigDecimal的，不过牛客网要求没那么高。后来我想了想只有把直线方程写成Ax+By+C=0的形式才能完全避免精度问题)
接下来，探讨下实数的hashCode()函数是个啥情况:
2.实数的hashCode()
那么我们来看看，0.0和-0.0调用equals方法是否相等:
System.out.println(new Float(0.0).equals(0.0f));
System.out.println(new Float(0.0).equals((float) -0.0));
输出是True 和 False
好吧，二者调用equals() 方法不相等，看来是满足了书里说的逻辑的
那我们看看Float底层equals函数咋写的:
public boolean equals(Object obj) {
    return (obj instanceof Float)
           && (floatToIntBits(((Float)obj).value) == 
                   floatToIntBits(value));
}
哦，原来是把Float转换成Bits的时候发生了点奇妙的事，于是我找到了一切的源头:搜索公众号互联网架构师复“2T”，送你一份惊喜礼包。
    /**
     * Returns a representation of the specified floating-point value
     * according to the IEEE 754 floating-point "single format" bit
     * layout.
     *
     * 
Bit 31 (the bit that is selected by the mask
     * {@code 0x80000000}) represents the sign of the floating-point
     * number.
     * Bits 30-23 (the bits that are selected by the mask
     * {@code 0x7f800000}) represent the exponent.
     * Bits 22-0 (the bits that are selected by the mask
     * {@code 0x007fffff}) represent the significand (sometimes called
     * the mantissa) of the floating-point number.
     *
     * 
If the argument is positive infinity, the result is
     * {@code 0x7f800000}.
     *
     * 
If the argument is negative infinity, the result is
     * {@code 0xff800000}.
     *
     * 
If the argument is NaN, the result is {@code 0x7fc00000}.
     *
     * 
In all cases, the result is an integer that, when given to the
     * {@link #intBitsToFloat(int)} method, will produce a floating-point
     * value the same as the argument to {@code floatToIntBits}
     * (except all NaN values are collapsed to a single
     * "canonical" NaN value).
     *
     * @param   value   a floating-point number.
     * @return the bits that represent the floating-point number.
     */
    public static int floatToIntBits(float value) {
        int result = floatToRawIntBits(value);
        // Check for NaN based on values of bit fields, maximum
        // exponent and nonzero significand.
        if (((result & FloatConsts.EXP_BIT_MASK) ==
              FloatConsts.EXP_BIT_MASK) &&
             (result & FloatConsts.SIGNIF_BIT_MASK) != 0)
            result = 0x7fc00000;
        return result;
    }
这文档挺长的，也查了其它资料，看了半天终于搞懂了
就是说Java浮点数的语义一般遵循IEEE 754二进制浮点算术标准。IEEE 754标准提供了浮点无穷，负无穷，负零和NaN（非数字）的定义。在使用Java过程中，一些特殊的浮点数通常会让大家很迷惑
当浮点运算产生一个非常接近0的负浮点数时，会产生“-0.0”，而这个浮点数不能正常表示
我们可以输出一波0.0和-0.0的数据:
System.out.println(Float.floatToIntBits((float) 0.0));
System.out.println(Float.floatToIntBits((float) -0.0));
System.out.println(Float.floatToRawIntBits(0.0f));
System.out.println(Float.floatToRawIntBits((float)-0.0));
结果:
0
-2147483648
0
-2147483648
就是说，存储-0.0, 竟然用的是0x80000000
这也是我们熟悉的Integer.MIN_VALUE
3.总结
java中浮点数的表示比较复杂，特别是牵涉到-0.0, NaN, 正负无穷这种，所以不适宜用来作为Map的key, 因为可能跟我们预想的不一致

全栈架构社区交流群

 「全栈架构社区」建立了读者架构师交流群，大家可以添加小编微信进行加群。欢迎有想法、乐于分享的朋友们一起交流学习。

扫描添加好友邀你进架构师群，加我时注明【姓名+公司+职位】

看完本文有收获？请转发分享给更多人

往期资源：


Flutter 移动应用开发实战 视频（开发你自己的抖音APP）
Java面试进阶训练营 第2季（分布式篇）
Java高级 - 分布式系统开发技术视频
浏览 7
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
同事把实数作为 HashMap 的key，领导发飙了...
开发者全社区
0
同事把实数作为 HashMap 的key，领导发飙了...
互联网架构师
0
同事把实数作为 HashMap 的key，领导发飙了...
Java引导者
0
同事把实数作为 HashMap 的key，领导发飙了...
Java专栏
0
为什么不能将实数作为 HashMap 的 key？
Java后端编程
0
为什么不建议使用实数作为 HashMap 的 key？
程序IT圈
0
面试官：为什么不能将实数作为 HashMap 的 key？
Java之间
0
为什么不建议使用实数作为 HashMap 的 key？
Java技术栈
0
java8中谨慎使用实数作为HashMap的key
java1234
0
为什么不建议使用实数作为 HashMap 的 key？
浪尖聊大数据
0
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报