Хорошая хеш-функция для строк
Я пытаюсь придумать хорошую хеш-функцию для строк. И я подумал, что было бы неплохо суммировать значения Юникода для первых пяти символов в строке (при условии, что он имеет пять, иначе остановитесь на том, где он заканчивается). Это хорошая идея или плохая?
Я делаю это на Java, но я не думаю, что это будет иметь большое значение.
15 ответов
Обычно хэши не будут делать сумм, иначе stop а также pots будет иметь такой же хэш.
и вы бы не ограничивали его первыми n символами, потому что в противном случае house и Houses будут иметь одинаковый хэш.
Обычно хэши принимают значения и умножают их на простое число (повышает вероятность создания уникальных хэшей). Таким образом, вы можете сделать что-то вроде:
int hash = 7;
for (int i = 0; i < strlen; i++) {
hash = hash*31 + charAt(i);
}
Если это вопрос безопасности, вы можете использовать криптографию Java:
import java.security.MessageDigest;
MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());
Возможно, вам следует использовать String.hashCode ().
Если вы действительно хотите реализовать hashCode самостоятельно:
Не поддавайтесь искушению исключить значимые части объекта из вычислений хеш-кода для повышения производительности - Джошуа Блох, Эффективная Java
Использование только первых пяти символов - плохая идея. Подумайте об иерархических именах, таких как URL: все они будут иметь один и тот же хэш-код (поскольку все они начинаются с "http://", что означает, что они хранятся в одном и том же сегменте в хэш-карте, демонстрируя ужасную производительность.
Вот история войны, перефразированная на String hashCode из " Эффективной Java":
Хеш-функция String, реализованная во всех выпусках до 1.2, проверяла не более шестнадцати символов, равномерно распределенных по всей строке, начиная с первого символа. Для больших коллекций иерархических имен, таких как URL, эта хеш-функция показала ужасное поведение.
Если вы делаете это на Java, то почему вы это делаете? Просто позвони .hashCode() на веревочке
Эта функция, предоставленная Ником, хороша, но если вы используете новое String(byte[] bytes) для преобразования в String, она не удалась. Вы можете использовать эту функцию для этого.
private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
public static String byteArray2Hex(byte[] bytes) {
StringBuffer sb = new StringBuffer(bytes.length * 2);
for(final byte b : bytes) {
sb.append(hex[(b & 0xF0) >> 4]);
sb.append(hex[b & 0x0F]);
}
return sb.toString();
}
public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException {
MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
return byteArray2Hex(messageDigest.digest());
}
Может быть, это может кому-то помочь
// djb2 hash function
unsigned long hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
Ходят слухи, что FNV-1 - хорошая хеш-функция для строк.
Для длинных строк (длиннее, скажем, около 200 символов) вы можете получить хорошую производительность с помощью хэш-функции MD4. Как криптографическая функция, она была взломана около 15 лет назад, но для не криптографических целей она все еще очень хорошая и удивительно быстрая. В контексте Java вам придется конвертировать 16-битные char значения в 32-битные слова, например, путем группировки таких значений в пары. Быстрая реализация MD4 в Java может быть найдена в sphlib. Вероятно, излишним в контексте заданий в классе, но в противном случае стоит попробовать.
Если вы хотите увидеть реализации отраслевого стандарта, я бы посмотрел на java.security.MessageDigest.
"Дайджесты сообщений - это безопасные однонаправленные хеш-функции, которые принимают данные произвольного размера и выводят хеш-значение фиксированной длины".
sdbm: этот алгоритм был создан для библиотеки базы данных sdbm (переопределение общедоступного домена ndbm)
static unsigned long sdbm(unsigned char *str)
{
unsigned long hash = 0;
int c;
while (c = *str++)
hash = c + (hash << 6) + (hash << 16) - hash;
return hash;
}
Вот ссылка, которая объясняет множество различных хеш-функций, сейчас я предпочитаю хеш-функцию ELF для вашей конкретной задачи. Он принимает в качестве входных данных строку произвольной длины.
public String hashString(String s) throws NoSuchAlgorithmException {
byte[] hash = null;
try {
MessageDigest md = MessageDigest.getInstance("SHA-256");
hash = md.digest(s.getBytes());
} catch (NoSuchAlgorithmException e) { e.printStackTrace(); }
StringBuilder sb = new StringBuilder();
for (int i = 0; i < hash.length; ++i) {
String hex = Integer.toHexString(hash[i]);
if (hex.length() == 1) {
sb.append(0);
sb.append(hex.charAt(hex.length() - 1));
} else {
sb.append(hex.substring(hex.length() - 2));
}
}
return sb.toString();
}
Это позволит избежать любого столкновения и будет быстрым, пока мы не будем использовать сдвиг в вычислениях.
int k = key.length();
int sum = 0;
for(int i = 0 ; i < k-1 ; i++){
sum += key.charAt(i)<<(5*i);
}
Хорошая идея работать с нечетным числом, когда пытаешься разработать хорошую функцию hast для строки. эта функция принимает строку и возвращает значение индекса, пока что ее работа довольно хороша. и имеет меньше столкновений. индекс колеблется от 0 до 300, может быть, даже больше этого, но я не поднялся до сих пор, даже с такими длинными словами, как "электромеханическая инженерия"
int keyHash(string key)
{
unsigned int k = (int)key.length();
unsigned int u = 0,n = 0;
for (Uint i=0; i<k; i++)
{
n = (int)key[i];
u += 7*n%31;
}
return u%139;
}
другое, что вы можете сделать, это умножить каждый символ int parse на индекс по мере его увеличения, как слово "медведь" (0*b) + (1*e) + (2*a) + (3*r), которое даст вам значение int для игры. первая вышеупомянутая хеш-функция сталкивается с "здесь" и "слышит", но все же отлично подходит для получения некоторых хороших уникальных значений. нижеприведенный не сталкивается с "здесь" и "слышать", потому что я умножаю каждый символ на индекс по мере его увеличения.
int keyHash(string key)
{
unsigned int k = (int)key.length();
unsigned int u = 0,n = 0;
for (Uint i=0; i<k; i++)
{
n = (int)key[i];
u += i*n%31;
}
return u%139;
}
Вот простая хеш-функция, которую я использую для хеш-таблицы, которую я построил. Это в основном для того, чтобы взять текстовый файл и хранить каждое слово в индексе, который представляет алфавитный порядок.
int generatehashkey(const char *name)
{
int x = tolower(name[0])- 97;
if (x < 0 || x > 25)
x = 26;
return x;
}
Что это в основном делает, так это слова хэшируются в соответствии с их первой буквой. Таким образом, слово, начинающееся с 'a', получило бы хеш-ключ 0, 'b' получило бы 1 и т. Д., А 'z' было бы 25. Числа и символы имели бы хеш-ключ 26. Это преимущество, которое это обеспечивает; Вы можете легко и быстро вычислить, где данное слово будет проиндексировано в хеш-таблице, так как все это в алфавитном порядке, что-то вроде этого: Код можно найти здесь: https://github.com/abhijitcpatil/general
Приводя следующий текст: Аттикус однажды сказал Джему: "Я бы предпочел, чтобы ты стрелял в консервные банки на заднем дворе, но я знаю, что ты пойдешь за птицами. Стреляй по всем голубым сойкам, если захочешь, но помни, что убить пересмешника - это грех ". Это был единственный раз, когда я слышал, как Аттикус говорил, что делать что-то - грех, и я спросил мисс Моди о Это. "Твой отец прав", - сказала она. "Пересмешники не делают ничего, кроме как делают музыку, чтобы мы могли наслаждаться. Они не едят сады людей, не гнездятся в кукурузных кроватках, они не делают ничего, а отдают свои сердца за нас. Вот почему грех убить пересмешника.
Это будет вывод:
0 --> a a about asked and a Atticus a a all after at Atticus
1 --> but but blue birds. but backyard
2 --> cribs corn can cans
3 --> do don’t don’t don’t do don’t do day
4 --> eat enjoy. except ever
5 --> for for father’s
6 --> gardens go
7 --> hearts heard hit
8 --> it’s in it. I it I it’s if I in
9 --> jays Jem
10 --> kill kill know
11 -->
12 --> mockingbird. music make Maudie Miss mockingbird.”
13 --> nest
14 --> out one one only one
15 --> people’s
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to That’s their thing they They to thing to time the That to the the tin to
20 --> us. up us
21 -->
22 --> why was was want
23 -->
24 --> you you you’ll you
25 -->
26 --> “Mockingbirds ” “Your ‘em “I’d