乐趣区

关于java:为什么不能将实数作为-HashMap-的-key

jiezi

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<Float, Integer> 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;
    }
}

这段代码在天真的我看来是没啥问题的，可就是没方法过，通过短暂的排查谬误，我写了以下代码加在下面的代码里运行 

public static void main(String[] args) {int[][] vals = {{2,3},{3,3},{-5,3}};
    Point[] points = new Point[3];
    for (int i=0; i<vals.length; 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<K, V> e;
     return (e = getNode(hash(key), key)) == null ? null : e.valu;
}

唔，先取得 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();

这是一个本地办法，看不到源码了，唔，，那我就应用它看看吧，测试一下不就好了吗, 我写了以下的测试代码:

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（）

  • 在程序执行期间，只有 equals 办法的比拟操作用到的信息没有被批改，那么对这同一个对象调用屡次，hashCode 办法必须始终如一地返回同一个整数。
  • 如果两个对象依据 equals 办法比拟是相等的，那么调用两个对象的 hashCode 办法必须返回雷同的整数后果。
  • 如果两个对象依据 equals 办法比拟是不等的，则 hashCode 办法不肯定得返回不同的整数。——《effective java》

那么咱们来看看，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 的时候产生了点微妙的事，于是我找到了所有的源头:

/**
* Returns a representation of the specified floating-point value
* according to the IEEE 754 floating-point "single format" bit
* layout.
*
* <p>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.
*
* <p>If the argument is positive infinity, the result is
* {@code 0x7f800000}.
*
* <p>If the argument is negative infinity, the result is
* {@code 0xff800000}.
*
* <p>If the argument is NaN, the result is {@code 0x7fc00000}.
*
* <p>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, 因为可能跟咱们料想的不统一

退出移动版