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

Question

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

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

Answer 1

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

Answer 2

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

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }

Answer 3

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

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

Answer 4

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

Answer 5

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