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

создать хэш SHA-1 а затем замаскировать самые низкие 64bits.

long hash = string.hashCode();

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

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

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

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

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

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

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

ответ на сегодня (2018). Сифаш.

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

библиотека гуавы имеет один: https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--

на Apache commons lang?

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

отказ от ответственности: это решение применимо, если вы хотите эффективно хэшировать отдельные слова естественного языка. Это неэффективно для хэширования длинного текста или текста, содержащего неалфавитные символы.

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

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

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

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