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

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

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

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

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

Спасибо


c++ mod hashcode
person Revokenz    schedule 04.05.2018    source источник
comment
Пробовали ли вы en.cppreference.com/w/cpp/string/basic_string/hash . результат может быть сохранен в size_t.   -  person gchen    schedule 04.05.2018
comment
Я не пробовал использовать его, пока вы не упомянули об этом, но, к сожалению, это не помогает моей проблеме. size_t также не позволяет хранить такие большие числа, как те, с которыми я работаю. Если у вас есть другие идеи, хм. Спасибо   -  person Revokenz    schedule 04.05.2018
comment
Я думал, ты хочешь хешировать строку?   -  person gchen    schedule 04.05.2018
comment
Да. Но на основе алгоритма на вики-странице для hashCode() числа слишком велики. Например, значение только для первого символа строки, о которой я упоминал, будет: 65 * 31 ^ (20-1) = 1,408593044298 * 10 ^ 30, что является значением, которое не может быть сохранено даже в size_t, как вы предложили.   -  person Revokenz    schedule 04.05.2018
comment
Я понимаю. Но вы не можете использовать формулу напрямую, вам нужно %N, прежде чем она станет слишком большой.   -  person gchen    schedule 04.05.2018
comment
Да, это, наверное, сработает, но тогда это будет нарушением условий проекта. %N можно использовать для окончательного хэша только в том случае, если он превышает значение N. Может быть, другого пути нет, и это было бы единственным решением этой проблемы. Итак, вы говорите, что нужно использовать %N в результате функции pow?   -  person Revokenz    schedule 04.05.2018
comment
... Это не имеет значения, потому что конечный результат будет таким же. (А+В)%Н == (А%Н+В%Н)%Н   -  person gchen    schedule 04.05.2018

Ответы (1)


arrow_upward
2
arrow_downward

Вы не можете хранить такие большие числа в 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;
}
person gchen    schedule 04.05.2018
comment
Кажется, я наконец понял это. По какой-то причине это не работало с обычным двойником, но мне удалось это исправить. Спасибо за предложение, действительно ценю, что вы потратили свое время на это - person Revokenz; 05.05.2018