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

Question

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

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

Answer 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 миллиарда различных ключей) вы, безусловно, сэкономите, независимо от того, какой сценарий вам нужен. Придумать варианты использования для 128-битных ключей (340 282 366 920 938 463 463 374 607 431 миллиарда возможных ключей) практически невозможно.

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

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

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

Answer 2

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

Answer 3

long hash = string.hashCode();

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

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

Answer 7

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

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 клонирование происходит намного быстрее.

Answer 8

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

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

Answer 9

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

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

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

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

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