為什麼不能將實數作為 HashMap 的 key?

語言: CN / TW / HK

關注公眾號:IT老哥,每天閱讀一篇乾貨文章,一年後你會發現一個不一樣的自己。

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; } } ```

這段程式碼在天真的我看來是沒啥問題的,可就是沒辦法過,經過長久的排查錯誤,我寫了以下程式碼加在上面的程式碼裡執行

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, 因為可能跟我們預想的不一致

關注公眾號:IT老哥,每天閱讀一篇乾貨文章,一年後你會發現一個不一樣的自己。