C ++ hashCode - работа с большими числами (+ операция с модом) - PullRequest
Новая
       30

C ++ hashCode - работа с большими числами (+ операция с модом)

0 голосов
/ 04 мая 2018

Я работаю над проектом, который включает программирование Java hashCode () хеш-функции,
формула .

Входные строки (т. Е. «Добавление триггерного блока C») были сгенерированы случайным образом и сохранены в текстовом файле. Также, если результирующий хэш не находится в пределах диапазона (0 <хэш <N), его необходимо скорректировать => хэш% N).

У меня проблемы с алгоритмом hashCode (), поскольку результат только для одного символа строки слишком велик (т. Е. 1.408 * 10 ^ 30), чтобы его можно было сохранить в обычной переменной. Я пытался использовать некоторые библиотеки, которые позволяют вам хранить очень большие числа, но ни одна из них не позволяет вам выполнить операцию мода, если хэш превышает параметр N.

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

Спасибо

1 Ответ

0 голосов
/ 04 мая 2018

Вы не можете хранить большие числа в C ++, но это, безусловно, возможно, если N не является гигантским числом. Хитрость заключается в том, чтобы выполнить % N во время цикла по строке, чтобы ваш номер никогда не переполнялся.

Вы можете использовать этот метод - https://math.stackexchange.com/a/453108, чтобы найти (A ^ B)% N, то есть (31 ^ 200)% N. 

//This is the algorithm mentioned in the above link
const size_t N = 1e9 + 7;
size_t bigPower(size_t x, size_t p) {
    size_t ans = 1;

    while(p > 0){
        if(p % 2 == 1)
            ans = (ans*x)%N;
        x = (x*x)%N;
        p /= 2;
    }

return ans;
}

Тогда следуйте формуле, не переполняйте цифры. 

size_t hashCode(const string& s) {
    size_t result = 0;
    for(size_t i = 0; i< s.size(); i++) {
        result += (s[i] * bigPower(31, s.size()-1-i))%N;
        result %= N;
    }

    return result;
}

UPDATE Я обнаружил, что Java hashCode может фактически переполниться и вернуть отрицательный хэш-код - HashCode, дающий отрицательные значения . Таким образом, если вы хотите, чтобы ваш хэш-код вел себя как Java, вы также можете разрешить переполнение. 

//This might produce the exact same hashCode as Java.
int hashCode(const string& s) {
    int result = 0;
    for(int i = 0; i< s.size(); i++) {
        int m = 1;
        for(int j=0; j<s.size()-1-i; j++) {
            m *= 31;
        }
        result += (s[i] * m);
    }

    return result;
}
...