牛客網(wǎng):為什么不能將實(shí)數(shù)作為 HashMap 的 key?

1.起因

讓我關(guān)注到這一點(diǎn)的起因是一道題:牛客網(wǎng)上的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.

大意就是給我一些點(diǎn)的X,Y坐標(biāo)，找到過(guò)這些點(diǎn)最多的直線，輸出這條線上的點(diǎn)數(shù)量。

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

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?1;?i++)?{????????????Map?map?=?new?HashMap<>(16);????????????//?記錄垂直點(diǎn)數(shù);?當(dāng)前和Points[i]在一條線上的最大點(diǎn)數(shù);?和Points[i]垂直的點(diǎn)數(shù)????????????int?ver?=?0,?cur,?dup?=?0;????????????for?(int?j?=?i?+?1;?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;????}}

這段代碼在天真的我看來(lái)是沒(méi)啥問(wèn)題的，可就是沒(méi)辦法過(guò)，經(jīng)過(guò)長(zhǎng)久的排查錯(cuò)誤，我寫(xiě)了以下代碼加在上面的代碼里運(yùn)行

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

也就是說(shuō)，它認(rèn)為(3-3) / (3-2) 和 (3-3) / (-5-2) 不同? 什么鬼…

經(jīng)過(guò)debug,發(fā)現(xiàn)上述結(jié)果分別是0.0和-0.0

0.0 難道不等于 -0.0 ?

這時(shí)我心里已經(jīng)一陣臥槽了，不過(guò)我還是寫(xiě)了驗(yàn)證代碼:

System.out.println(0.0 == -0.0);

結(jié)果是True，沒(méi)問(wèn)題啊，我凌亂了……

一定是java底層代碼錯(cuò)了! 我沒(méi)錯(cuò)……

又是一陣debug,我找到了這條語(yǔ)句:

map.put(d, map.get(d) == null ? 1 : map.get(d) + 1);

我覺(jué)得map.get()很有問(wèn)題, 它的源代碼是這樣的:

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

唔，先獲得hash()是吧，那我找到了它的hash函數(shù):

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

再來(lái)，這里是要比較h 和key的hashCode是吧,那我們?nèi)タ磆ashCode()函數(shù)

public native int hashCode();

這是一個(gè)本地方法，看不到源碼了，唔，，那我就使用它看看吧，測(cè)試一下不就好了嗎,我寫(xiě)了以下的測(cè)試代碼:

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());    }

結(jié)果竟然是True和False !!!

這個(gè)源頭終于找到了, 0.0 和 -0.0 的hashCode值是不同的 !

經(jīng)過(guò)一番修改，我通過(guò)了這道題(其實(shí)精度也會(huì)有問(wèn)題，應(yīng)該使用BigDecimal的，不過(guò)牛客網(wǎng)要求沒(méi)那么高。后來(lái)我想了想只有把直線方程寫(xiě)成Ax+By+C=0的形式才能完全避免精度問(wèn)題)

接下來(lái)，探討下實(shí)數(shù)的hashCode()函數(shù)是個(gè)啥情況:

2.實(shí)數(shù)的hashCode（）

• 在程序執(zhí)行期間，只要equals方法的比較操作用到的信息沒(méi)有被修改，那么對(duì)這同一個(gè)對(duì)象調(diào)用多次，hashCode方法必須始終如一地返回同一個(gè)整數(shù)。

• 如果兩個(gè)對(duì)象根據(jù)equals方法比較是相等的，那么調(diào)用兩個(gè)對(duì)象的hashCode方法必須返回相同的整數(shù)結(jié)果。

• 如果兩個(gè)對(duì)象根據(jù)equals方法比較是不等的，則hashCode方法不一定得返回不同的整數(shù)。——《effective java》

那么我們來(lái)看看，0.0和-0.0調(diào)用equals方法是否相等:

System.out.println(new?Float(0.0).equals(0.0f));System.out.println(new Float(0.0).equals((float) -0.0));

輸出是True 和 False

好吧，二者調(diào)用equals() 方法不相等，看來(lái)是滿足了書(shū)里說(shuō)的邏輯的

那我們看看Float底層equals函數(shù)咋寫(xiě)的:

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

哦，原來(lái)是把Float轉(zhuǎn)換成Bits的時(shí)候發(fā)生了點(diǎn)奇妙的事，于是我找到了一切的源頭:

/*** 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;}

這文檔挺長(zhǎng)的，也查了其它資料，看了半天終于搞懂了

就是說(shuō)Java浮點(diǎn)數(shù)的語(yǔ)義一般遵循IEEE 754二進(jìn)制浮點(diǎn)算術(shù)標(biāo)準(zhǔn)。IEEE 754標(biāo)準(zhǔn)提供了浮點(diǎn)無(wú)窮，負(fù)無(wú)窮，負(fù)零和NaN（非數(shù)字）的定義。在使用Java過(guò)程中，一些特殊的浮點(diǎn)數(shù)通常會(huì)讓大家很迷惑

當(dāng)浮點(diǎn)運(yùn)算產(chǎn)生一個(gè)非常接近0的負(fù)浮點(diǎn)數(shù)時(shí)，會(huì)產(chǎn)生“-0.0”，而這個(gè)浮點(diǎn)數(shù)不能正常表示

我們可以輸出一波0.0和-0.0的數(shù)據(jù):

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));

結(jié)果:

0-21474836480-2147483648

就是說(shuō)，存儲(chǔ)-0.0, 竟然用的是0x80000000

這也是我們熟悉的Integer.MIN_VALUE

3.總結(jié)

java中浮點(diǎn)數(shù)的表示比較復(fù)雜，特別是牽涉到-0.0, NaN, 正負(fù)無(wú)窮這種，所以不適宜用來(lái)作為Map的key, 因?yàn)榭赡芨覀冾A(yù)想的不一致

來(lái)源：blog.csdn.net/qq_30219017/article/details/79689492

如有文章對(duì)你有幫助，

“在看”和轉(zhuǎn)發(fā)是對(duì)我最大的支持！

一款牛逼的Java面試題庫(kù)，點(diǎn)擊下圖查看詳細(xì)內(nèi)容