Я ищу хэш-функцию, которая:
Почему бы вам не использовать вариант 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'} будут иметь одинаковый хеш-код.
Создайте хэш SHA-1, а затем замаскируйте самые младшие 64 бит.
long hash = string.hashCode();
Да, верхние 32 бита будут равны 0, но вы, вероятно, исчерпаете аппаратные ресурсы, прежде чем столкнетесь с проблемами с хэш-коллизиями. Хэш-код в String довольно эффективен и хорошо протестирован.
Обновление Я думаю, что вышеупомянутое удовлетворяет простейшую вещь, которая могла бы работать, однако я согласен с идеей @sfussenegger о расширении существующего хеш-кода String.
Помимо наличия хорошего хэш-кода для вашей строки, вы можете захотеть переименовать хэш-код в своей реализации. Если ваше хранилище используется другими разработчиками или используется с другими типами, это может помочь распределить ваши ключи. Например, Java HashMap основан на хэш-таблицах с силовыми характеристиками длины, поэтому он добавляет эту функцию для обеспечения того, чтобы младшие биты были достаточно распределены.
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-битный вариант, и я думаю, вы обнаружите, что он не использует столько CPU, сколько вы думаете.
Я использовал такой код, чтобы получить хеши для огромных наборов данных (теперь, вероятно, миллиарды объектов), чтобы окутать их во многие бэкэнд-магазины. Он должен работать на все, что вам нужно. Обратите внимание, что я думаю, что вы можете только вызвать 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() не существует и должен быть реализован каким-либо другим способом.
Вы смотрите на Apache commons lang?
Но для 64-разрядных (и 128) вам нужны некоторые трюки: правила, изложенные в книге "Эффективная Java" Джошуа Блоха, помогут вам создать 64-битный хэш легко (просто используйте long вместо int). Для 128 бит вам нужны дополнительные хаки...
ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Это решение применимо, если вы хотите эффективно использовать отдельные слова естественного языка. Это неэффективно для хэширования более длинного текста или текста, содержащего неалфавитные символы.
Я не знаю о функции, но здесь идея, которая может помочь:
Затем вы могли бы использовать оставшиеся 12 бит для кодирования длины строки (или ее по модулю) для дальнейшего уменьшения коллизий или создания 12-битного хэш-кода с использованием традиционной хэш-функции.
Предполагая, что ваш ввод текстовый, я могу себе представить, что это приведет к очень немногим столкновениям и будет недорогим для вычисления (O (n)). В отличие от других решений до сих пор этот подход учитывает проблемную область для уменьшения конфликтов. Он основан на детекторе Anagram, описанном в "Программировании жемчуга" (см. здесь).