Хорошая хеш-функция для строк

160

Я пытаюсь придумать хорошую хеш-функцию для строк. И я подумал, что было бы хорошей идеей суммировать значения Юникода для первых пяти символов в строке (при условии, что у него есть пять, иначе остановитесь там, где он заканчивается). Это хорошая идея или плохая?

Я делаю это на Java, но я не думаю, что это будет иметь большое значение.

Лейф Андерсен
источник
4
Хорошие хеш-функции сильно зависят от входных данных хеш-функции и требований алгоритма. Такой хеш будет не очень хорош, если все ваши строки начинаются с одинаковых пяти символов, например. Это также приведет к нормальному распределению.
WhirlWind
1
Возможный дубликат 98153
Михаил
14
Почему ты не можешь использовать Stringсобственный hashCode()?
Барт Киерс
@WhirlWind, правда, я не уверен, что будут строки, кроме того, что это будет, вероятно, текст на английском языке.
Лейф Андерсен
@Barl, главным образом потому, что мой профессор сказал нам реализовать наш собственный хеш-функтор ... и причина, по которой я не хотел использовать Java, заключалась в том, что он был универсальным, и я предположил бы, что более конкретный хеш-функтор будет лучше.
Лейф Андерсен

Ответы:

161

Обычно хэш не будет делать суммы, в противном случае stopи potsбудет иметь тот же хэш.

и вы бы не ограничивали его первыми n символами, потому что иначе дом и домики имели бы одинаковый хеш.

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

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}
jonathanasdf
источник
@jonathanasdf Как вы можете сказать, что он всегда дает вам уникальный ключ хеша. Есть ли математическое доказательство? Я думаю, что мы должны взять мод хэша с другим большим простым числом, в противном случае возникает проблема переполнения.
Devsda
17
@devsda Он не говорил, что всегда уникален, он сказал, что, скорее всего, будет уникальным. Что касается того, почему быстрый поиск в Google показывает эту статью: computinglife.wordpress.com/2008/11/20/…, объясняющую, почему 31 использовался для хеширования строк Java. Математического доказательства не дано, но оно объясняет общую концепцию того, почему простые числа работают лучше.
Pharap
2
Большое спасибо за разъяснение идеи улучшения хэширования. Просто для двойной проверки - возвращаемое значение hashCode () будет использоваться Java для сопоставления с некоторым индексом таблицы перед сохранением объекта. Итак, если hashCode () возвращает m, он делает что-то вроде (m mod k), чтобы получить индекс таблицы размера k. Это правильно?
whitehat
1
"hash = hash * 31 + charAt (i);" производит тот же хеш для спота, топов, стопов, оптов и потов.
Джек Строб
1
@ Мак Я верю, что вы правы. Не знаю, о чем я думал.
Джек Штрауб
139

Если это вопрос безопасности, вы можете использовать криптографию Java:

import java.security.MessageDigest;

MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

источник
93
Ницца. У меня есть приложение для машинного обучения, которое выполняет статистические НЛП на большом корпусе. После нескольких начальных этапов морфологической нормализации исходных слов в тексте я выбрасываю строковые значения и вместо этого использую хэш-коды. Во всем моем корпусе насчитывается около 600 000 уникальных слов, и с помощью функции хеш-кода java по умолчанию я получаю около 3,5% коллизий. Но если я SHA-256 строковое значение, а затем сгенерировать хеш-код из переваренной строки, коэффициент столкновения составляет менее 0,0001%. Спасибо!
Бенджизм с
3
Спасибо за предоставление информации о столкновениях и количестве слов. Очень полезно.
Филипп
19
@benjismith Один на миллион слишком велик ... "менее 0,0001%" - это косвенный способ сказать "ровно 0"? Я действительно сомневаюсь, что вы видели столкновение SHA-256, потому что это никогда не наблюдалось нигде, никогда; даже для 160-битного SHA-1. Если у вас есть две строки, которые выдают один и тот же SHA-256, сообщество безопасности будет радо их увидеть; ты будешь всемирно известным ... очень неясным способом. См. Сравнение функций SHA
Тим Сильвестр
7
@TimSylvester, вы не поняли. Я не нашел столкновения SHA-256. Я вычислил SHA-256 и затем передал результирующие байтовые последовательности в типичную функцию Java "hashCode", потому что мне нужен был 32-битный хеш. Вот где я обнаружил столкновения. Ничего примечательного :)
benjismith
1
Разве нет разницы между «хешированием» и «шифрованием»? Я понимаю, что MessageDigest - это односторонняя функция хеширования, верно? Кроме того, когда я использовал эту функцию, я получил хешированную строку как множество ненужных UTF-символов, когда открыл файл в LibreOffice. Можно ли получить хешированную строку в виде случайного набора буквенно-цифровых символов вместо ненужных символов UTF?
Nav
38

Вы, вероятно, должны использовать String.hashCode () .

Если вы действительно хотите реализовать hashCode самостоятельно:

Не поддавайтесь искушению исключить значимые части объекта из вычислений хеш-кода для повышения производительности - Джошуа Блох, Эффективная Java

Использование только первых пяти символов - плохая идея . Подумайте об иерархических именах, таких как URL: все они будут иметь одинаковый хэш-код (поскольку все они начинаются с «http: //», что означает, что они хранятся в одном и том же сегменте в хэш-карте, демонстрируя ужасную производительность.

Вот история войны, перефразированная на String hashCode из « Эффективной Java »:

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

Frederik
источник
1
Если кто-то использует коллекцию с двойным хэшированием, может быть целесообразно, чтобы первый хэш был действительно быстрым и грязным. Если у вас есть тысяча длинных строк, половина из которых отображается с помощью crummy-функции на одно конкретное значение, а половина - на разные значения, производительность в таблице с одним хэшем будет плохой, но производительность в двойном таблица хеширования, где второй хэш проверяет всю строку, может быть почти вдвое больше, чем таблица с одиночным хэшированием (поскольку половина строк не должна быть полностью хэширована). Однако ни одна из стандартных коллекций Java не выполняет двойное хеширование.
суперкат
Ссылка «Эффективная Java» не работает @Frederik
KGs
17

Если вы делаете это на Java, то почему вы это делаете? Просто позвони .hashCode()на строку

Pyrolistical
источник
2
Я делаю это как часть класса, и часть задания заключается в написании нескольких различных хеш-функций. Профессор сказал нам обратиться за помощью к «лучшим».
Лейф Андерсен
20
Если вам нужно, чтобы вы были согласованы между версиями и реализациями JVM, вам не следует полагаться на это .hashCode(). Скорее используйте некоторый известный алгоритм.
Стивен Остермиллер
7
Алгоритм String::hashCodeуказан в JDK, поэтому он так же переносим, ​​как и само существование класса java.lang.String.
ишавит
12

ГуаваHashFunction ( Javadoc ) обеспечивает достойное не крипто-сильное хеширование.

Майк Самуэль
источник
1
Это все еще в бета-версии этого комментария
ThomasRS
1
А теперь я 404.
Шон
8

Эта функция, предоставленная Ником, хороша, но если вы используете новое 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());
}

Может быть, это может кому-то помочь

Фест Тамакло
источник
Вы можете просто передать байтовый массив в messageDigest.update ().
szgal
byteArray2Hex () - это именно то, что я искал! Большое спасибо :)
Krzysiek
5
// 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;
}

Логика источника позади хеш-функции djb2 - SO

Пратик Деогхаре
источник
1
Я думаю, что это просто простое число, с которого нужно начинать, чтобы у нас было меньше столкновений.
CornSmith
5

Ходят слухи, что FNV-1 - хорошая хеш-функция для строк.

Для длинных строк (длиннее, скажем, около 200 символов) вы можете получить хорошую производительность с помощью хеш-функции MD4 . Как криптографическая функция, она была взломана около 15 лет назад, но для не криптографических целей она все еще очень хорошая и удивительно быстрая. В контексте Java вам придется преобразовывать 16-битные charзначения в 32-битные слова, например, группируя такие значения в пары. Быстрая реализация MD4 в Java может быть найдена в sphlib . Вероятно, излишним в контексте заданий в классе, но в противном случае стоит попробовать.

Томас Порнин
источник
Эта хеш-функция намного лучше, чем та, которая поставляется с Java.
clankill3r
3

Если вы хотите увидеть реализации отраслевого стандарта, я бы посмотрел на java.security.MessageDigest .

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

Дин Дж
источник
1

вот ссылка, которая объясняет множество различных хеш-функций, сейчас я предпочитаю хеш-функцию ELF для вашей конкретной задачи. Он принимает в качестве входных данных строку произвольной длины.

Yefei
источник
1

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;
}
Anchal
источник
0
         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();
}
Хараф JRA
источник
-1

Хорошая идея работать с нечетным числом, когда пытаешься разработать хорошую функцию 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;
}
kanthonye
источник
-1

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

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 dont dont dont do dont do day
4 --> eat enjoy. except ever
5 --> for for fathers
6 --> gardens go
7 --> hearts heard hit
8 --> its in it. I it I its 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 --> peoples
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to Thats 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 youll you
25 --> 
26 --> Mockingbirds  Your em Id
user2311285
источник
2
Хорошая хеш-функция распределяет значения поровну по сегментам.
Джонатан Петерсон
-1

Это позволит избежать любого столкновения и будет быстрым, пока мы не будем использовать сдвиг в вычислениях.

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }
Камаль Эль-Дин Шаир
источник