Как сделать хорошую хэш-функцию для больших строк? - PullRequest
Новая
       8

Как сделать хорошую хэш-функцию для больших строк?

1 голос
/ 15 июля 2011

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

public class GoodHashFunctor implements HashFunctor {

    @Override
    public int hash(String item) {

        String binaryRepString = "";

        for(int i = 0; i < item.length(); i++){
            // Add the String version of the binary version of the integer  version of each character in item
            binaryRepString += Integer.toBinaryString((int)(item.charAt(i)));
        }


        long longVersion = Long.parseLong(binaryRepString, 2) % Integer.MAX_VALUE;


        return (int) longVersion;

    }

}

Однако, когда я пытаюсь хешировать большие строки (около 10-15 символов), я получаю ошибки, потому что когда он пытается parseLong, он умирает, потому что этослишком большое число.

Что вы все думаете, я должен делать?И мой профессор сказал, что мы не можем использовать hashCode ()

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

int hash=7;

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

Но я бы не столкнулся ста же проблема?Я полагаю, что Strings, возможно, потребуется намного больше времени, чтобы сломать это новым способом.Я не знаю, я довольно запутался ...

Ответы [ 2 ]

0 голосов
/ 15 июля 2011

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

  • как долго вводится

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

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

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

Как примечание: очевидно, что ваш += в Long работает только для коротких строк. Но даже с другой хэш-функцией вы не получите уникальные значения хеш-функции для каждой возможной строки, которую вы можете вписать в 64-битную Long (Java): вы можете различать только 2 ^ 64 строки даже с совершенным хешем функция. В общем, если у вас есть хеш-таблица, которая отображает aKey-> anObject, вы по-прежнему сохраняете исходный ключ (а не только хеш-значение, которое представляет этот сегмент), чтобы вы могли сравнить его с запрошенной строкой ключа.

В зависимости от ваших требований, вы можете заглянуть в тему криптографических хеш-функций , чтобы решить, хотите ли вы те . Однако сначала взгляните на очень хорошую запись в Википедии, в которой перечислены хороших хеш-функций и, что более важно, ситуации, для которых они хороши: http://en.wikipedia.org/wiki/Hash_function

0 голосов
/ 15 июля 2011

Зачем вам нужно преобразовывать каждый символ в строку (и это тоже в двоичном виде) перед преобразованием его в long?Почему бы просто не иметь значение long, к которому вы добавляете char?

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

Редактировать: Я понимаю, что вы не хотите просто суммировать их, потому что у всех анаграмм будет одинаковое значение хеш-функции.Но я думаю, вы уже знаете, как этого избежать.Обратите внимание, что, объединяя биты, вы в основном добавляете биты к значению после смещения их на несколько позиций.то есть «10101» + «10001» - это то же самое, что 1010100000 + 10001 - 21 << 5 + 17. </p>

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

Еще одна вещь, на которую следует обратить внимание, это то, что long имеет только 64 бита.Вы можете упаковать в него столько всего char до того, как он начнет переполняться.Таким образом, большинство практических хеш-функций принимают значение по модулю некоторого числа.Конечно, это означает, что существует только ограниченное количество возможных значений хеш-функции для неограниченного количества входных строк.Столкновения неизбежны, но правильно выбранные значения для вашего сдвига / множителя и мода могут минимизировать количество столкновений.

...