Что такое хорошая 64-битная hash-функция в Java для текстовых строк?

Я ищу хеш-функцию, которая:

  1. Хэши текстовые строки хорошо (например, несколько столкновений)
  2. Написано на Java и широко используется
  3. Бонус: работает в нескольких полях (вместо меня конкатенация их и применение hashа на конкатенированной строке)
  4. Бонус: имеет 128-битный вариант.
  5. Бонус: Не интенсивность процессора.

Почему бы вам не использовать long вариант по умолчанию String.hashCode() (где некоторые действительно умные ребята, безусловно, прилагают усилия к тому, чтобы сделать его эффективным – не говоря уже о тысячах разработчиков, которые уже смотрели на этот код)?

 // adapted from String.hashCode() public static long hash(String string) { long h = 1125899906842597L; // prime int len = string.length(); for (int i = 0; i < len; i++) { h = 31*h + string.charAt(i); } return h; } 

Если вы ищете еще больше бит, возможно, вы можете использовать BigInteger Edit:

Как я упоминал в комментарии к ответу @brianegge, для hashей с более чем 32 битами не так много сокращений и, скорее всего, не для hashей с более чем 64 бит:

Я мог представить огромную hash-таблицу, распространяемую на десятках серверов, возможно, хранение десятков миллиардов отображений. Для такого сценария @brianegge по-прежнему имеет действительную точку здесь: 32 бит позволяют использовать 2 х 32 (около 4,3 млрд.) Разных хеш-ключей. Предполагая сильный алгоритм, вы все равно должны иметь довольно мало коллизий. С 64-разрядным (18 446 744 073 000 различных ключей) вы, безусловно, сохраняете, независимо от того, какой безумный сценарий вам нужен. Мысль об использовании для 128-битных ключей (340,282,366,920,938,463,463,374,607,431 billion возможных ключей) в значительной степени невозможна.

Чтобы объединить hash для нескольких полей, просто сделайте XOR умножить один на простой и добавить их:

 long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2); 

Небольшое простое место, чтобы избежать равного хеш-кода для коммутируемых значений, т. Е. {'Foo', 'bar'} и {'bar', 'foo'} не равны и должны иметь другой hash-код. XOR плохо, поскольку он возвращает 0, если оба значения равны. Следовательно, {'foo', 'foo'} и {'bar', 'bar'} будут иметь одинаковый hash-код.

Создайте hash SHA-1, а затем замаскируйте самые младшие 64 бит.

 long hash = string.hashCode(); 

Да, верхние 32 бита будут равны 0, но вы, вероятно, исчерпаете аппаратные ресурсы, прежде чем столкнуться с проблемами с хеш-коллизиями. Хэш-код в String довольно эффективен и хорошо протестирован.

Обновление. Я думаю, что вышеописанное удовлетворяет простейшую вещь, которая могла бы работать , однако я согласен с идеей @sfussenegger о расширении существующего хеш-кода String.

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

  h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); 

Почему бы не использовать многочлен CRC64. Они достаточно эффективны и оптимизированы, чтобы убедиться, что все биты подсчитаны и распределены по пространству результатов.

Существует множество реализаций, доступных в сети, если вы используете Google CRC64 Java,

Сделайте что-то вроде этого:

 import java.io.ByteArrayOutputStream; import java.io.DataOutputStream; import java.io.IOException; import java.math.BigInteger; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; public class Test { public static void main(String[] args) throws NoSuchAlgorithmException, IOException { ByteArrayOutputStream baos = new ByteArrayOutputStream(); DataOutputStream dos = new DataOutputStream(baos); try { MessageDigest md = MessageDigest.getInstance("MD5"); SomeObject testObject = new SomeObject(); dos.writeInt(testObject.count); dos.writeLong(testObject.product); dos.writeDouble(testObject.stdDev); dos.writeUTF(testObject.name); dos.writeChar(testObject.delimiter); dos.flush(); byte[] hashBytes = md.digest(baos.toByteArray()); BigInteger testObjectHash = new BigInteger(hashBytes); System.out.println("Hash " + testObjectHash); } finally { dos.close(); } } private static class SomeObject { private int count = 200; private long product = 1235134123l; private double stdDev = 12343521.456d; private String name = "Test Name"; private char delimiter = '\n'; } } 

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

Наконец BigInteger позволит вам превратить выходные байты в более простой в использовании номер. Алгоритмы MD5 и SHA1 генерируют 128-битные hashи, поэтому, если вам нужно 64, вы можете просто усечь.

SHA1 должен hash почти ничего хорошего, и с нечастыми столкновениями (это 128-бит). Это работает с Java, но я не уверен, как это реализовано. Это может быть довольно быстро. Он работает на нескольких полях в моей реализации: просто DataOutputStream их все на DataOutputStream и вам хорошо идти. Вы могли бы даже сделать это с reflectionм и аннотациями (возможно, @HashComponent(order=1) чтобы показать, какие поля попадают в hash и в каком порядке). У этого есть 128-битный вариант, и я думаю, вы обнаружите, что он не использует столько CPU, сколько вы думаете.

Я использовал такой код, чтобы получить хеши для огромных наборов данных (теперь, вероятно, миллиарды объектов), чтобы окутать их во многие бэкэнд-магазины. Он должен работать на все, что вам нужно. Обратите внимание, что я думаю, что вы можете просто вызвать MessageDigest.getInstance() один раз, а затем clone() с этого момента: IIRC клонирование происходит намного быстрее.

Обрати строку, чтобы получить еще 32-битный hash-код, а затем объединить два:

 String s = "astring"; long upper = ( (long) s.hashCode() ) << 32; long lower = ( (long) s.reverse().hashCode() ) - ( (long) Integer.MIN_VALUE ); long hash64 = upper + lower; 

Это псевдокод; метод String.reverse() не существует и должен быть реализован каким-либо другим способом.

Ответ на сегодня (2018). SipHash.

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

В библиотеке Guava есть один: https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24–

Вы смотрите на Apache ?

Но для 64-битных (и 128) вам нужны некоторые трюки: правила, изложенные в книге «Эффективная Java» Джошуа Блоха, помогут вам создать 64-битный hash легко (просто используйте long вместо int). Для 128 бит вам нужны дополнительные хаки …

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Это решение применимо, если вы хотите эффективно использовать отдельные слова естественного языка. Это неэффективно для hashирования более длинного текста или текста, содержащего неалфавитные символы.

Я не знаю о функции, но вот идея, которая может помочь:

  • Посчитайте 52 из 64 бит, чтобы представить, какие буквы присутствуют в строке. Например, если присутствуют «a», вы должны установить бит [0], для бита бит «b» 1 для бит бит «A» [26]. Таким образом, только текст, содержащий точно такой же набор букв, будет иметь одну и ту же «подпись».

Затем вы можете использовать оставшиеся 12 бит для кодирования длины строки (или ее по модулю) для дальнейшего уменьшения коллизий или создания 12-битного hash-кода с использованием традиционной функции hashирования.

Предполагая, что ваш ввод является текстовым, я могу себе представить, что это приведет к очень немногим столкновениям и будет недорогим для вычисления (O (n)). В отличие от других решений до сих пор этот подход учитывает проблемную область для уменьшения коллизий. Он основан на детекторе Anagram, описанном в «Programming Pearls» (см. Здесь ).

  • Вычислить подобие косинуса с учетом 2 строк предложения
  • Как исправить двойные кодированные символы UTF8 (в таблице utf-8)
  • Преобразование DateTime из строки C #
  • Сколько памяти использует строка в Java 8?
  • Как определить, содержит ли строка строку с неверными кодированными символами
  • как заменить одиночную обратную косую черту в R
  • Домен верхнего уровня из URL-адреса в C #
  • Как преобразовать / разобрать из String в char в java?
  • Вычисление частоты каждого слова в предложении в java
  • Присвоение массиву char значения в C
  • Как вы получаете строку из MemoryStream?
  • Interesting Posts

    Безопасность Java: плагины для песочницы, загруженные с помощью URLClassLoader

    Как UPSERT (MERGE, INSERT … ON DUPLICATE UPDATE) в PostgreSQL?

    Форматирование DATE в oracle

    Вызывать толкатель, когда mysql изменился

    «adb» не распознается как внутренняя или внешняя команда, операционная программа или командный файл

    Building Boost 1.52 с MinGW

    Переадресация назад так же, как и труба?

    Создайте дату с дневного месяца и года с помощью T-SQL

    Ошибка установки Simulia Abaqus в Linux (Mint 17.2)

    Каковы отношения между Any, AnyVal, AnyRef, Object и как они отображаются при использовании в Java-коде?

    Значение этого в обработчике событий React

    Jquery Ajax Загрузка изображения

    Как заставить кнопку колеса мыши выполнить двойной щелчок в окнах 7?

    Как вы входите в систему / аутентифицируете пользователя с битами Asp.Net MVC5 RTM с использованием AspNet.Identity?

    Обоснование для Матчи, бросающего IllegalStateException, когда метод ‘matching’ не вызван

    Давайте будем гением компьютера.