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

Question

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

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

Answer 1

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

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

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

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}

Answer 2

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

import java.security.MessageDigest;

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

Answer 3

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

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

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

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

Вот история войны, перефразированная на хеш-коде String из " Effective Java ":

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

Answer 4

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

Answer 5

Guava's HashFunction ( javadoc ) обеспечивает достойное не криптостойкое хеширование.

Answer 6

Эта функция, предоставленная Ником, хороша, но если вы используете новую строку (byte [] bytes) для преобразования в строку, она не удалась. Вы можете использовать эту функцию для этого.

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());
}

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

Answer 7

// 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

Answer 8

FNV-1 , по слухам, является хорошей хэш-функцией для строк.

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

Answer 9

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

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

Answer 10

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;
}