Вопрос по java – Двойной в HashMap

14

Я думал об использовании Double как ключа к HashMap, но я знаю, что сравнения с плавающей запятой небезопасны, и это заставило меня задуматься. Является ли метод equals в классе Double также небезопасным? Если это так, это означает, что метод hashCode, вероятно, также неверен. Это будет означать, что использование Double в качестве ключа к HashMap приведет к непредсказуемому поведению.

Может ли кто-нибудь подтвердить мои предположения здесь?

Ваш Ответ

8   ответов
0

Это зависит от того, как вы храните и обращаетесь к вашей карте, да, аналогичные значения могут немного отличаться и, следовательно, не будут хэшировать одно и то же значение.

private static final double key1 = 1.1+1.3-1.6;
private static final double key2 = 123321;
...
map.get(key1);

было бы все хорошо, однако

map.put(1.1+2.3, value);
...
map.get(5.0 - 1.6);

было бы опасно

12

Short answer: Не делай этого

Long answer: Вот как будет вычисляться ключ:

Фактический ключ будетjava.lang.Double объект, так как ключи должны быть объектами. Вот ееhashCode() метод:

public int hashCode() {
  long bits = doubleToLongBits(value);
  return (int)(bits ^ (bits >>> 32));
}

doubleToLongBits() Метод в основном занимает 8 байтов и представляет их как длинные. Таким образом, это означает, что небольшие изменения в вычислении double могут много значить, и вы будете иметь ключевые пропуски.

Если вы можете рассчитать на заданное количество точек после точки - умножьте на 10 ^ (количество цифр после точки) и преобразуйте в int (например, - для 2 цифр умножьте на 100).

Это будет намного безопаснее.

Error: User Rate Limit Exceeded
8

Я думаю, вы правы. Хотя хэш двойных чисел является целым числом, двойной может испортить хэш. Вот почему, как упоминает Джош Блох в Effective Java, когда вы используете double в качестве входных данных для хеш-функции, вы должны использоватьdoubleToLongBits (), Точно так же используйте floatToIntBits для float.

В частности, чтобы использовать double в качестве хэша, следуя рецепту Джоша Блоха, вы должны сделать следующее:

public int hashCode() {
  int result = 17;
  long temp = Double.doubleToLongBits(the_double_field);
  result = 37 * result + ((int) (temp ^ (temp >>> 32)));
  return result;
}

Это из пункта 8 «Эффективной Java», «Всегда переопределяйте hashCode, если вы переопределяете равно». Это можно найти вэтот pdf главы из книги.

Надеюсь это поможет.

Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededDouble.hashCodeError: User Rate Limit ExceededDoubleError: User Rate Limit Exceeded
3

Короткий ответ: вероятно, это не сработает.

Честный ответ: все зависит.

Более длинный ответ. Хеш-код - это не проблема, это природа равных сравнений с плавающей запятой. Как указывает Nalandial и его комментаторы, в конечном итоге любое совпадение с хеш-таблицей все равно заканчивается использованием равных для выбора правильного значения.

Итак, вопрос в том, генерируются ли ваши двойники таким образом, что вы знаете, что равные действительно означают равные? Если вы читаете или вычисляете значение, сохраняете его в хеш-таблице, а затем позже читаете или вычисляете значение, используя точно такие же вычисления, то Double.equals будет работать. Но в противном случае это ненадежно: 1,2 + 2,3 не обязательно равно 3,5, это может быть 3,4999995 или что-то еще. (Не реальный пример, я только что это выдумал, но это то, что происходит.) Вы можете сравнивать значения с плавающей запятой и с достаточной долей достоверности для меньших или больших значений, но не для равных.

2

Может бытьBigDecimal получить вас, куда вы хотите пойти?

6

Это зависит от того, как вы будете его использовать.

Если вы довольны тем, что можете найти значение только на основеexact same bit pattern (или жеpotentially эквивалентный, такой как +/- 0 и различные NaN), тогда это могло бы быть хорошо.

В частности, все NaN будут считаться равными, но +0 и -0 будут считаться разными. Из документов дляDouble.equals:

Note that in most cases, for two instances of class Double, d1 and d2, the value of d1.equals(d2) is true if and only if

d1.doubleValue() == d2.doubleValue() also has the value true. However, there are two exceptions:

  • If d1 and d2 both represent Double.NaN, then the equals method returns true, even though Double.NaN==Double.NaN has the value false.
  • If d1 represents +0.0 while d2 represents -0.0, or vice versa, the equal test has the value false, even though +0.0==-0.0 has the value true.

This definition allows hash tables to operate properly.

Скорее всего, вы заинтересованы в "числах, очень близких к ключу" хотя, что делает его намного менее жизнеспособным. В частности, если вы собираетесь выполнить один набор вычислений, чтобы получить ключ один раз, а затем другой набор вычислений, чтобы получить ключ во второй раз, у вас возникнут проблемы.

Error: User Rate Limit Exceeded
java.sun.com/j2se/1.5.0/docs/api/java/lang/Double.htmlError: User Rate Limit Exceeded
5

Проблема не в хеш-коде, а в точности двойников. Это приведет к некоторым странным результатам. Пример:

    double x = 371.4;
    double y = 61.9;
    double key = x + y;    // expected 433.3

    Map<Double, String> map = new HashMap<Double, String>();
    map.put(key, "Sum of " + x + " and " + y);

    System.out.println(map.get(433.3));  // prints null

Расчетное значение (ключ) равно «433.29999999999995». что не соответствует 433.3, и поэтому вы не можете найти запись на карте (хэш-код, вероятно, также отличается, но это не главная проблема).

Если вы используете

map.get(key)

it should find the entry... []]

Error: User Rate Limit Exceededvery veryError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded anio
0

Используется хэш типа double, а не сам double.

Edit: Спасибо, Джон, на самом деле я этого не знал.

Я не уверен в этом (вам нужно просто взглянуть на исходный код объекта Double), но я думаю, что все проблемы с сравнениями с плавающей запятой позаботятся о вас.

Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededinitiallyError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы