Как рассчитать коллизии по этой хэш-функции?

Question

Я сделал простую хеш-функцию (если ее можно назвать таковой), которая преобразует строку в двойную.

Он работает, беря значение первого символа и удваивая его, затем умножая на косинус следующего символа, затем умножая на косинус следующего символа и так далее...

это функция:

double hash (string str) {
    double hash = (double)str[0];

    for (int i = 1; i < str.length(); i++) {
        hash *= cos((double)str[i]);
    }

    return hash;
}

Так как же рассчитать вероятность столкновения в этой функции?

Я нашел одну формулу, которая идет 1 - e^(k(k-1)/(2k)), но из того, что я читал, работает только в том случае, если хеш-функция является хорошей функцией (она распределяет хэш-значения равномерно, как хороший RNG, или что-то типа того).

Answer 1

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

В твоем случае hash('abc') = (cos('a') * cos('b')) * cos('c'), который равен hash('cab') = (cos('c') * cos('a')) * cos('b')За исключением, возможно, некоторых незначительных ошибок с плавающей запятой.