为什么不建议你使用实数作为HashMap的key？

点击关注公众号&＃xff0c;实用技术文章及时了解

来源&＃xff1a;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坐标&＃xff0c;找到过这些点最多的直线&＃xff0c;输出这条线上的点数量

于是我就敲出了以下的代码:

import java.util.HashMap;
import java.util.Map;//class Point {
//    int x;
//    int y;
//    Point(int a, int b) { x &＃61; a; y &＃61; b; }
//}public class Solution {public int maxPoints(Point[] points) {if (points.length <&＃61; 2) {return points.length;}int max &＃61; 2;for (int i &＃61; 0; i < points.length - 1; i&＃43;&＃43;) {Map map &＃61; new HashMap<>(16);// 记录垂直点数; 当前和Points[i]在一条线上的最大点数; 和Points[i]垂直的点数int ver &＃61; 0, cur, dup &＃61; 0;for (int j &＃61; i &＃43; 1; j < points.length; j&＃43;&＃43;) {if (points[j].x &＃61;&＃61; points[i].x) {if (points[j].y !&＃61; points[i].y) {ver&＃43;&＃43;;} else {dup&＃43;&＃43;;}} else {float d &＃61; (float)((points[j].y - points[i].y) / (double) (points[j].x - points[i].x));map.put(d, map.get(d) &＃61;&＃61; null ? 1 : map.get(d) &＃43; 1);}}cur &＃61; ver;for (int v : map.values()) {cur &＃61; Math.max(v, cur);}max &＃61; Math.max(max, cur &＃43; dup &＃43; 1);}return max;}
}

这段代码在天真的我看来是没啥问题的&＃xff0c;可就是没办法过&＃xff0c;经过长久的排查错误&＃xff0c;我写了以下代码加在上面的代码里运行

public static void main(String[] args) {int[][] vals &＃61; {{2,3},{3,3},{-5,3}};Point[] points &＃61; new Point[3];for (int i&＃61;0; i}

它输出的&＃xff0c;竟然是2

也就是说&＃xff0c;它认为(3-3) / (3-2) 和 (3-3) / (-5-2) 不同? 什么鬼…

经过debug,发现上述结果分别是0.0和-0.0

0.0 难道不等于 -0.0 ?

这时我心里已经一阵卧槽了&＃xff0c;不过我还是写了验证代码:

System.out.println(0.0 &＃61;&＃61; -0.0);

结果是True&＃xff0c;没问题啊&＃xff0c;我凌乱了……

一定是java底层代码错了! 我没错……

又是一阵debug,我找到了这条语句:

map.put(d, map.get(d) &＃61;&＃61; null ? 1 : map.get(d) &＃43; 1);

我觉得map.get()很有问题, 它的源代码是这样的:

public V get(Object key) {Node e;return (e &＃61; getNode(hash(key), key)) &＃61;&＃61; null ? null : e.value;
}

唔&＃xff0c;先获得hash()是吧&＃xff0c;那我找到了它的hash函数:

static final int hash(Object key) {int h;return (key &＃61;&＃61; null) ? 0 : (h &＃61; key.hashCode()) ^ (h >>> 16);
}

再来&＃xff0c;这里是要比较h 和key的hashCode是吧,那我们去看hashCode()函数

public native int hashCode();

这是一个本地方法&＃xff0c;看不到源码了&＃xff0c;唔&＃xff0c;&＃xff0c;那我就使用它看看吧&＃xff0c;测试一下不就好了吗,我写了以下的测试代码:

public static void main(String[] args) {System.out.println(0.0 &＃61;&＃61; -0.0);System.out.println(new Float(0.0).hashCode() &＃61;&＃61; new Float(-0.0).hashCode());}

结果竟然是True和False !!!

这个源头终于找到了, 0.0 和 -0.0 的hashCode值是不同的 !

经过一番修改&＃xff0c;我通过了这道题(其实精度也会有问题&＃xff0c;应该使用BigDecimal的&＃xff0c;不过牛客网要求没那么高。后来我想了想只有把直线方程写成Ax&＃43;By&＃43;C&＃61;0的形式才能完全避免精度问题)

接下来&＃xff0c;探讨下实数的hashCode()函数是个啥情况:

2.实数的hashCode()

• 在程序执行期间&＃xff0c;只要equals方法的比较操作用到的信息没有被修改&＃xff0c;那么对这同一个对象调用多次&＃xff0c;hashCode方法必须始终如一地返回同一个整数。

• 如果两个对象根据equals方法比较是相等的&＃xff0c;那么调用两个对象的hashCode方法必须返回相同的整数结果。

• 如果两个对象根据equals方法比较是不等的&＃xff0c;则hashCode方法不一定得返回不同的整数。——《effective java》

那么我们来看看&＃xff0c;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

好吧&＃xff0c;二者调用equals() 方法不相等&＃xff0c;看来是满足了书里说的逻辑的

那我们看看Float底层equals函数咋写的:

public boolean equals(Object obj) {return (obj instanceof Float)&& (floatToIntBits(((Float)obj).value) &＃61;&＃61; floatToIntBits(value));
}

哦&＃xff0c;原来是把Float转换成Bits的时候发生了点奇妙的事&＃xff0c;于是我找到了一切的源头:

/*** 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* {&＃64;code 0x80000000}) represents the sign of the floating-point* number.* Bits 30-23 (the bits that are selected by the mask* {&＃64;code 0x7f800000}) represent the exponent.* Bits 22-0 (the bits that are selected by the mask* {&＃64;code 0x007fffff}) represent the significand (sometimes called* the mantissa) of the floating-point number.** 

If the argument is positive infinity, the result is* {&＃64;code 0x7f800000}.** 

If the argument is negative infinity, the result is* {&＃64;code 0xff800000}.** 

If the argument is NaN, the result is {&＃64;code 0x7fc00000}.** 

In all cases, the result is an integer that, when given to the* {&＃64;link #intBitsToFloat(int)} method, will produce a floating-point* value the same as the argument to {&＃64;code floatToIntBits}* (except all NaN values are collapsed to a single* "canonical" NaN value).** &＃64;param   value   a floating-point number.* &＃64;return the bits that represent the floating-point number.*/public static int floatToIntBits(float value) {int result &＃61; floatToRawIntBits(value);// Check for NaN based on values of bit fields, maximum// exponent and nonzero significand.if (((result & FloatConsts.EXP_BIT_MASK) &＃61;&＃61;FloatConsts.EXP_BIT_MASK) &&(result & FloatConsts.SIGNIF_BIT_MASK) !&＃61; 0)result &＃61; 0x7fc00000;return result;}

这文档挺长的&＃xff0c;也查了其它资料&＃xff0c;看了半天终于搞懂了

就是说Java浮点数的语义一般遵循IEEE 754二进制浮点算术标准。IEEE 754标准提供了浮点无穷&＃xff0c;负无穷&＃xff0c;负零和NaN&＃xff08;非数字&＃xff09;的定义。在使用Java过程中&＃xff0c;一些特殊的浮点数通常会让大家很迷惑

当浮点运算产生一个非常接近0的负浮点数时&＃xff0c;会产生“-0.0”&＃xff0c;而这个浮点数不能正常表示

我们可以输出一波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

就是说&＃xff0c;存储-0.0, 竟然用的是0x80000000

这也是我们熟悉的Integer.MIN_VALUE

3.总结

java中浮点数的表示比较复杂&＃xff0c;特别是牵涉到-0.0, NaN, 正负无穷这种&＃xff0c;所以不适宜用来作为Map的key, 因为可能跟我们预想的不一致

推荐&＃xff1a;

主流Java进阶技术&＃xff08;学习资料分享&＃xff09;

PS&＃xff1a;因为公众号平台更改了推送规则&＃xff0c;如果不想错过内容&＃xff0c;记得读完点一下“在看”&＃xff0c;加个“星标”&＃xff0c;这样每次新文章推送才会第一时间出现在你的订阅列表里。点“在看”支持我们吧&＃xff01;