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

Question

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

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

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

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

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

Спасибо

1

c++hashcode mod

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы не можете хранить такие большие числа в 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;
}

ОБНОВИТЬ
Я обнаружил, что Java hashCode может фактически переполниться и вернуть отрицательный хэш-код —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;
}

2