Возможно, true и false — это 1 и 0, но в Java они хешируются до 1231 и 1237.

Спросите любого участника Jeopardy!, каковы числовые значения true и false, и он, вероятно, ответит: «0 и 1. Я имею в виду, что такое 0 и 1? Что такое 1 и 0?»

Общеизвестно, что почти все компьютеры работают в двоичном формате. Это легко отображает дихотомии на 0 и 1. И поэтому вполне логично, что логическое значение true будет равно 1, а логическое значение false будет 0.

Но этот, казалось бы, простой вопрос, как оказалось, включает в себя множество тонкостей, которые мы принимаем как должное каждый раз, когда пишем оператор if или любой другой вид условного выражения в современном языке программирования.

Первая из этих тонкостей — «ширина данных». В настоящее время 64-битные процессоры кажутся довольно стандартными. Говорим ли мы о целых числах со знаком или без знака, 64 бит кажется достаточным для представления гораздо большего количества целых чисел, чем нам может понадобиться в любой день.

Даже во времена 8-битных процессоров может показаться расточительным тратить целый байт (8 бит) на одно логическое значение (пожалуйста, не придавайте слишком большого значения моему выбору заглавных букв на этом этапе).

Если я правильно понимаю, программисты втиснули бы целых восемь независимых булевых значений в один байт. Затем к логическим значениям можно будет получить доступ с помощью побитовых операций, таких как XOR и NOT.

Например, предположим, что вам нужно получить доступ к логическому значению бита 5 в байте флагов. Это будет бит четыре бита от бита 0, самого младшего бита. Поскольку 2⁴ = 16, вы можете использовать флаги побитово И 16. Если результат равен 16, логическое значение равно true, но если оно равно 0, это false.

Теперь предположим, что вам нужно, чтобы ваша программа что-то делала, если какой-либо бит в байте флагов равен 1. Вы можете сделать флаги побитовыми И беззнаковыми 255 (со знаком -1). Затем это true, если результатом является любое ненулевое число, false, если оно равно 0.

На самом деле стандарт Американского национального института стандартов (ANSI) для C++ определяет, что false равно 0, а true — любое ненулевое значение.

В своей книге Portable C++ Патриция Гинке говорит, что безопаснее проверять, что логическое значение не равно false, чем проверять, что оно равно true.

Учитывая, что condition объявлено как логическое значение, Гинке говорит, что condition == true может не всегда работать на всех компиляторах и платформах C++, поэтому лучше использовать condition != false. Это кажется мне каким-то окольным путем, каламбур.

С Java и C# мы не беспокоимся о том, что что-то будет true на одной машине и false на другой.

Таким образом, большинство программистов на Java и C# могут блаженно не обращать внимания на фактические числовые значения, которые виртуальная машина Java или среда CLR используют для представления true и false, не говоря уже о фактической базовой машине.

Однако есть еще один контекст, в котором true и false сопоставляются с числовыми значениями, и это контекст хэш-кодов.

Когда примитив boolean обернут в объект Boolean, он должен иметь какой-то хэш-код (с этого момента, пожалуйста, прочтите мой выбор заглавных букв).

В частности, объект Boolean, обертывающий примитив boolean со значением true, имеет хэш-код 1231, а значение 1237 соответствует false.

Я впервые обнаружил эти значения в Scala REPL (я объясню Scala чуть позже). Эти значения не являются тайной, хотя я мог бы с таким же успехом получить их из Документации Oracle Java для Boolean:

хэш-код

public int hashCode()

Возвращает хэш-код для этого объекта Boolean.

Переопределение: hashCode в классе Object
Возвраты: целое число 1231, если этот объект представляет true; возвращает целое число 1237, если этот объект представляет false.
См. также: Object.equals(java.lang.Object), System.identityHashCode(java.lang.Object)

Хэш-код — это 32-битное целое число со знаком, которое потенциально можно использовать в хеш-таблице (например, java.util.IdentityHashMap) для однозначной идентификации различных объектов в хеш-таблице.

Например, String, содержащий Hello, world! хэши в виде −1880044555 и String, содержащие Hello, World! хэши как 1498789909 (эти значения я взял из Scala REPL и проверил их в Scastie).

В Java все объекты наследуют equals() и hashCode() от Object. Они оба могут быть переопределены, когда это необходимо, и ваша IDE считает, что переопределение одного требует переопределения другого (конечно, если вы не перенастроите соответствующую подсказку).

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

Итак, они начинают писать

    @Override
    public boolean equals(Object obj) 

и почти сразу IDE выдает предупреждение о том, что hashCode() отсутствует. NetBeans и IntelliJ предложат вам написать hashCode(), Eclipse, вероятно, тоже.

Некоторые программисты, вероятно, просто принимают то, что IDE пишет для hashCode(). Однако, если у вас нет сжатых сроков, может быть хорошей идеей тщательно изучить сгенерированную функцию.

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

Самое важное в хэш-коде то, что два объекта, которые считаются равными, должны иметь одинаковый хеш-код. Модульный тест может выглядеть примерно так:

    if (objectA.equals(objectB)) {
        assertEquals(objectA.hashCode(), objectB.hashCode());
    }

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

    if (objectA.equals(objectB)) {
        assertEquals(objectA.hashCode(), objectB.hashCode());
    } else {
        assertNotEquals(objectA.hashCode(), objectB.hashCode());
    }

Очевидно, что лучший способ убедиться, что два одинаковых объекта имеют одинаковый хеш-код, — это использовать одни и те же поля, определяющие равенство, для определения хэш-кода.

Часто класс Fraction является удобным и простым для понимания примером, за который я благодарен Кэю Хорстманну; он довольно часто использует его в своей книге Scala для нетерпеливых.

Две дроби равны, если равны их числители и равны также их знаменатели.

Если они еще не находятся в наименьших терминах, мы должны поместить их в наименьшие члены перед выполнением сравнения, чтобы, например, программа распознала, что -7/14 = -1/2.

Кроме того, чтобы не усложнять ситуацию, мы должны потребовать, чтобы знаменатель всегда был положительным целым числом. Чтобы повторно использовать предыдущий пример, 7/−14 нужно преобразовать сначала в −7/14, а затем в −1/2.

На самом деле, порядок этих шагов не имеет значения, пока наш конструктор Fraction позаботится о них, так что equals() может безопасно полагаться на то, что дроби уже являются наименьшими, а знаменатель является положительным целым числом.

Для моего собственного проекта я написал Fraction, чтобы использовать 64-битные целые числа со знаком в качестве числителя и знаменателя. Моя реализация также включает double для численного приближения дроби, которую я считаю непригодной для использования в equals().

Но даже если бы мы использовали 32-разрядные целые числа со знаком для числителя и знаменателя, у нас все еще была бы проблема с записью Fraction.hashCode(): примитив int имеет только 2³² различных значений, но Fraction может представлять как минимум 3 × 2³¹ − 1 различных чисел. .

И это при подсчете только дробей со знаменателем 1, которые являются целыми числами, и единичных дробей (то есть дробей с числителем 1). Ясно, что Fraction может представлять намного больше чисел, чем это.

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

Затем FractionTest следует протестировать несколько равных долей независимо от вероятности в реальном варианте использования, но для отдельных долей следует ограничиться долями, которые могут возникнуть при фактическом использовании.

Наша заглушка hashCode() для провала первого теста, вероятно, может просто возвращать 0 для каждой дроби. Что ж, это может на самом деле пройти тест на равные дроби, но обязательно провалит тест на разные дроби.

Затем мы можем изменить hashCode(), чтобы умножить знаменатель на 2¹⁶ без учета переполнения, а затем добавить числитель по модулю 2¹⁶.

Тогда -1/2 может хэшироваться как 131071 или 196607, в зависимости от того, как мы получим числитель по модулю 2¹⁶. Однако -1/65538 также будет хешироваться как 131071 или 196607.

Вы можете решить, что это вполне подходит для того, что вам нужно Fraction, например, если вы не собираетесь помещать Fraction объекты в хеш-таблицу, или вы собираетесь это сделать, но не возражаете против небольшое снижение производительности в маловероятном случае, если вы будете помещать дроби со знаменателями 65536 отдельно в хеш-таблицу.

Теперь предположим, что мы реализуем GaussianFraction, представляющее число вида a + bi, где a и b — это обычные дроби, к которым мы привыкли, а i — главный квадратный корень из −1 (другой квадратный корень равен −i).

Мы говорим о таких числах, как −1/2 + i/2 (здесь b = 1/2), что является решением уравнения 2x ² + 2x + 1. GaussianFraction, вероятно, содержит два объекта Fraction, один для a и один для b.

Очевидно, нам нужна возможность проверить, равны ли две «гауссовские дроби», а это значит, что нам также понадобятся хэш-коды.

В 32-разрядное целое число со знаком втиснуться еще сложнее, но мы, вероятно, можем просто выполнить некоторые арифметические действия с хэш-кодами a и b, чтобы получить хэш-код для a + bi, например умножение хэш-кода для a на хэш-код для b.

Ничто из этого не является проблемой при реализации Boolean.hashCode(), поскольку boolean может иметь только два возможных значения: true или false. Так почему бы просто не хешировать их как 1 и 0?

Потому что какому-то другому объекту с полем Boolean может потребоваться использовать Boolean.hashCode() для собственного хеш-кода, точно так же, как GaussianFraction.hashCode() может зависеть от Fraction.hashCode().

Если false хеширует как 0, а true хэширует как 1, умножение хеш-кодов других полей на Boolean.hashCode() может быть бесполезным. Добавление Boolean.hashCode() может быть не намного лучше.

Но с хешированием true как 1231 и false как 1237 сложение и умножение могут работать намного лучше для создания уникальных хэш-кодов, чем с 1 и 0.

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

Я думаю, что, вероятно, было бы приемлемо использовать примитив boolean, а затем использовать оператор if для хеширования true и false до любых числовых значений, которые имеют смысл для вашего конкретного случая использования. Что-то вроде этого:

    @Override
    public int hashCode() {
        int hash = 1;
        // ...do some stuff with the hash codes of object fields...
        if (this.someFlag) {
            hash *= 3;
        } else {
            hash *= 17;
        }
        return hash;
    }

Конечно, я сомневаюсь, что будет какая-то существенная разница в производительности между этим способом и использованием Boolean.hashCode().

Вместо того, чтобы откладывать публикацию на поиски реального примера, я просто воспользуюсь игрушечным примером: подсказки Jeopardy!.

Я предполагаю, что авторы, вероятно, просто пишут подсказки в Microsoft Word, хотя у них может быть собственный шаблон. Microsoft Excel также имел бы смысл.

Что касается механизма передачи подсказок от писателей на экраны подсказок, программного обеспечения для редактирования видео и официального архива подсказок, я предполагаю, что это программа на C или C++, хотя JavaScript также правдоподобен (вставьте здесь стандартное объяснение того, почему JavaScript сильно отличается от Java).

Как вы знаете, у каждой подсказки Jeopardy! указана сумма в долларах, которую ответивший игрок может выиграть или проиграть; но если это Daily Double, игрок может поставить другую сумму.

Наш объект JeopardyClue может иметь следующие поля с соответствующими геттерами и сеттерами: String category, short dollarAmount (при условии, что игроки всегда должны ставить целые суммы в долларах), Boolean dailyDoubleFlag, String clue, String correctResponse, Date intendedAirDate.

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

Я не понимаю, почему хэш-код флага Daily Double должен фигурировать в расчете хэш-кода подсказки, но, поскольку это игрушечный пример, давайте просто скажем, что он должен.

Вот подсказка за 400 долларов в категории «Люди мира» в игре Jeopardy!, впервые вышедшей в эфир 14 июня 2018 г.: «Яванцы — самая многочисленная этническая группа этой нации». «Что такое Индонезия?» Диана Хсу ответила правильно.

Этот может иметь вид -2128310992 без умножения на dailyDoubleFlag.hashCode(), 94255344 с.

Обратите внимание, что, поскольку 2128310992 является 30-битным числом, умножение -2128310992 на 10-битное число вызывает переполнение, которое приводит к положительному целому числу, а не к -2632720697104, абсолютное значение которого является 41-битным числом.

Подсказка на 600 долларов в той же категории была Daily Double, Сюй поставил 1200 долларов: «Африканеров когда-то называли этим именем, означающим «фермер». «Кто такие буры?» Или, может быть, она ответила: «Что такое бур?» В любом случае, это правильно.

Это может иметь вид 1102500808 без умножения на dailyDoubleFlag.hashCode(), -31170888 с.

Этого, вероятно, достаточно для того, чтобы вы поняли идею. Если вы хотите выполнить это упражнение для всей игры от 14 июня 2018 года, неофициальная стенограмма игры доступна на J-Archive.com.

Боковая панель: хэш-коды в Scala

В Scala все является объектом: объекты — это объекты, примитивы — это объекты, а функции — это объекты. А поскольку Scala построена поверх Java, объекты имеют хэш-коды, а примитивы и функции также имеют хеш-коды. Например:

scala> (Math.abs(_: Double)).hashCode
res15: Int = 2099559808
scala> (Math.abs(_: Int)).hashCode
res16: Int = 284101091

Скорее всего, вы получите разные результаты даже в рамках одного сеанса Scala REPL… Мне не удалось воспроизвести эти результаты в Scastie, но мне удалось воспроизвести результаты для некоторых «примитивов».

Все, что в Scala является объектом, означает, что Scala REPL — отличный способ поиграть с хэш-кодами и другими стандартными свойствами стандартных классов Java, а также со стандартными свойствами классов Java и/или Scala, которые вы создаете.

В общем, я считаю предпочтительнее использовать REPL для такого рода исследований. Запускать проект в IDE только для того, чтобы написать несколько операторов println, или даже написать исходный файл в Блокноте и скомпилировать его в командной строке, кажется излишеством для таких разовых вещей, как эта.

Для хеш-кодов примитивов Java в Scala REPL, вероятно, лучше всего получить их хэш-коды «как примитивы», а не пытаться создавать экземпляр оболочки.

scala> 7.hashCode
res16: Int = 7
scala> -7.hashCode
res17: Int = -7
scala> Math.PI.hashCode
res18: Int = 340593891
scala> true.hashCode
res19: Int = 1231
scala> false.hashCode
res20: Int = 1237

Эти результаты должны быть одинаковыми для всех сеансов Scala REPL, пока Oracle не изменит соответствующие реализации hashCode().

Если вам действительно интересно, каким был бы хеш-код объекта, если бы класс не переопределял Object.hashCode(), вы всегда можете сделать System.identityHashCode().

scala> System.identityHashCode(res16)
res21: Int = 224237360
scala> System.identityHashCode(7)
res22: Int = 224237360
scala> System.identityHashCode(res17)
res23: Int = 1098912468
scala> System.identityHashCode(-7)
res24: Int = 1098912468
scala> System.identityHashCode(res18)
res25: Int = 773074354
scala> System.identityHashCode(Math.PI)
res26: Int = 949389896
scala> System.identityHashCode(res19)
res27: Int = 1469015613
scala> System.identityHashCode(1231)
res28: Int = 827221909
scala> System.identityHashCode(res20)
res29: Int = 1249746110
scala> System.identityHashCode(1237)
res30: Int = 1576743136
scala> System.identityHashCode(7)
res31: Int = 224237360
scala> System.identityHashCode(-7)
res32: Int = 1098912468

Я предполагаю, что они не будут согласованы между экземплярами REPL. Тем не менее, я был удивлен тем, насколько последовательными являются системные хэш-коды для целых чисел.

В Scala есть несколько классов, таких как RichInt, которые расширяют возможности некоторых стандартных типов Java. Интересно, переопределяют ли они хеш-коды Java? Это может быть обсуждение в другой день.

Но сейчас вы, возможно, по какой-то причине чувствуете голод.