【转】java8中谨慎使用实数作为HashMap的key!

傷城~ 2022-01-06 08:05 200阅读 0赞

# [java8中谨慎使用实数作为HashMap的key!][java8_HashMap_key] #

java8中一个hashCode()函数引发的血案  
java8中一个hashCode()函数引发的血案  
1.起因  
2.实数的hashCode()  
3.总结  
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;  
\}  
\}  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
这段代码在天真的我看来是没啥问题的，可就是没办法过，经过长久的排查错误，我写了以下代码加在上面的代码里运行

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));  
\}  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
它输出的，竟然是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);  
1  
结果是True，没问题啊，我凌乱了……  
一定是java底层代码错了! 我没错……  
又是一阵debug,我找到了这条语句:

map.put(d, map.get(d) == null ? 1 : map.get(d) + 1);  
1  
我觉得map.get()很有问题, 它的源代码是这样的:

public V get(Object key) \{ 
Node<K,V> e; 
return (e = getNode(hash(key), key)) == null ? null : e.value; 
\} 
1 
2 
3 
4 
唔，先获得hash()是吧，那我找到了它的hash函数:

static final int hash(Object key) \{  
int h;  
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
\}  
1  
2  
3  
4  
再来，这里是要比较h 和key的hashCode是吧,那我们去看hashCode()函数

public native int hashCode();  
1  
这是一个本地方法，看不到源码了，唔，，那我就使用它看看吧，测试一下不就好了吗,我写了以下的测试代码:

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());  
\}  
1  
2  
3  
4  
5  
结果竟然是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));  
1  
2  
输出是True 和 False  
好吧，二者调用equals() 方法不相等，看来是满足了书里说的逻辑的  
那我们看看Float底层equals函数咋写的:

public boolean equals(Object obj) \{  
return (obj instanceof Float)  
&& (floatToIntBits(((Float)obj).value) ==  
floatToIntBits(value));  
\}  
1  
2  
3  
4  
5  
哦，原来是把Float转换成Bits的时候发生了点奇妙的事，于是我找到了一切的源头:

/\*\* 
\* 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; 
\} 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
40 
41 
这文档挺长的，也查了其它资料，看了半天终于搞懂了 
就是说Java浮点数的语义一般遵循IEEE 754二进制浮点算术标准。IEEE 754标准提供了浮点无穷，负无穷，负零和NaN（非数字）的定义。在使用Java过程中，一些特殊的浮点数通常会让大家很迷惑

详情请查看这篇文章: 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));  
1  
2  
3  
4  
结果:  
0  
\-2147483648  
0  
\-2147483648

就是说，存储-0.0, 竟然用的是0x80000000  
这也是我们熟悉的Integer.MIN\_VALUE

3.总结  
java中浮点数的表示比较复杂，特别是牵涉到-0.0, NaN, 正负无穷这种，所以不适宜用来作为Map的key, 因为可能跟我们预想的不一致  
\---------------------  
作者：0x落尘  
来源：CSDN  
原文：https://blog.csdn.net/qq\_30219017/article/details/79689492  
版权声明：本文为博主原创文章，转载请附上博文链接！

转载于:https://www.cnblogs.com/kira2will/p/11024990.html

[java8_HashMap_key]: https://blog.csdn.net/qq_30219017/article/details/79689492