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

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

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

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

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

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

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

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

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

long hash = string.hashCode();

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

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

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

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

Сделайте что-нибудь вроде этого:

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-битный вариант, и я думаю, вы обнаружите, что он не использует столько ЦП, сколько вы думаете.

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

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

В сети доступно множество реализаций, если вы погуглите «CRC64 Java»