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

Ответ 1

Почему бы вам не использовать вариант 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 Изменить:

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

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

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

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

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

Ответ 2

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

Ответ 3

long hash = string.hashCode();

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

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

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

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

Ответ 4

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

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

Ответ 5

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

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-битные хэши, поэтому, если вам нужно 64, вы можете просто обрезать.

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

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

Ответ 6

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

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() не существует и должен быть реализован каким-либо другим способом.

Ответ 7

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

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

Ответ 8

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

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

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

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

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