Как бы вы интерпретировали поведение моей C-хэш-функции (тип Fowler – Noll – Vo_hash_function)?

Question

Я не понимаю, почему значение "хеш" значения интергера становится меньше в / после цикла 3.

Я бы предположил, что это произойдет, потому что ограничение uint 2,147,483,647.НО ... когда я пытаюсь идти шаг за шагом, значение равно 2146134658 ?.Я не так хорош в математике, но он должен быть ниже, чем ограничение.

#define FNV_PRIME_32 16777619
#define FNV_OFFSET_32 2166136261U

unsigned int hash_function(const char *string, unsigned int size)
{
    unsigned int str_len = strlen(string);

    if (str_len == 0) exit(0);

    unsigned int hash = FNV_OFFSET_32;

    for (unsigned int i = 0; i < str_len; i++)
    {
        hash = hash ^ string[i]; 
        // Multiply by prime number found to work well
        hash = hash * FNV_PRIME_32;
        if (hash > 765010506)
            printf("YO!\n");
        else
            printf("NOO!\n");
    }
    return hash % size;
}  

Если вам интересно, если это утверждение только для меня.

if (hash > 765010506)
    printf("YO!\n");
else
    printf("NOO!\n");

765010506значение для хэша после следующего запуска цикла.

Answer 1

Я не понимаю, почему значение "хеш" значения интергера уменьшается в / после цикла 3.

Вся целочисленная арифметика без знака в C равна модульная арифметика ,Для unsigned int это по модулю UINT_MAX + 1;для unsigned long, по модулю ULONG_MAX + 1 и т. д.

(a по модулю m означает остаток от a, деленный на m; в C * a % m, если оба a и m являются целочисленными типами без знака.)

На многих современных архитектурах unsigned int является 32-разрядным целочисленным типом без знака с UINT_MAX == 4294967295.

Давайте посмотрим, что это означает на практике для умножения (на 65520, что оказывается интересным значением; 2 ¹⁶ - 16):

unsigned int  x = 1;
int           i;
for (i = 0; i < 10; i++) {
    printf("%u\n", x);
    x = x * 65520;
}

Вывод

1
65520
4292870400
50327552
3221291008
4293918720
16777216
4026531840
0
0

Что?Как?Почему результат заканчивается нулем?Этого не может быть!

Конечно, можно.Фактически, вы можете математически показать, что это происходит в конце концов, когда множитель является четным, и по модулю это имеет отношение к степени двойки (2 ³² , здесь).

Ваш конкретный множительстранно, однако;Итак, он не страдает от вышесказанного.Тем не менее, он все еще оборачивается из-за операции по модулю.Если мы повторим то же самое с вашим множителем 16777619 и немного более длинной последовательностью,

unsigned int  x = 1;
int           i;
for (i = 0; i < 20; i++) {
    printf("%u\n", x);
    x = x * 16777619;
}

, мы получим

1
16777619
637696617
1055306571
1345077009
1185368003
4233492473
878009595
1566662433
558416115
1485291145
3870355883
3549196337
924097827
3631439385
3600621915
878412353
2903379027
3223152297
390634507

Фактически, получается, что эта последовательность равна 1 073 741 824итераций (до повторения), и они никогда не дадут, например, 0, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14 или 15 - то есть, если они начинаются с 1Для получения результата, меньшего чем 16 777 619 (16 689 137), требуется даже 380 итераций.

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

Answer 2

Я предполагаю, что это произойдет, потому что ограничение uint составляет 2 147 483 647.

Максимальное значение 32-разрядного целого числа без знака составляет примерно 4 миллиарда (2 ³² - 1 = 4 294 967 295).Число, о котором вы думаете, является максимальным значением целого числа со знаком (2 ³¹ - 1).

2,146,134,658 немного меньше, чем 2 ³¹ (поэтому он может уместиться даже в 32-разрядное целое число без знака), но он все еще очень близок к пределу.Умножение на FNV_PRIME_32 - примерно 2 ²⁴ - даст примерно 2 ⁵⁵ , что приведет к переполнению.