Блог

Я возлюсь с хэш-функциями, переношу некоторые классические семейства, такие как murmur или fnv, и создаю свои собственные, на самом деле, для развлечения. Я знаю, что js не совсем идеальная среда для этого, но неважно.

Самое большое препятствие, с которым я сталкиваюсь, — это тот факт, что js использует удвоения для большинства арифметических операций. Почти каждая отдельная хэш-функция, которую я когда-либо видел, использует целочисленное переполнение путем умножения. Например, я беру ввод 7 и умножаю его на некоторое большое простое число, например 0x5bd1e995, это умножение усиливает значимость этого небольшого ввода в каждый отдельный бит результата, который действительно хорош для хэш-функций.

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

Несколько способов, которые я нашел для решения этой проблемы, заключаются в

1. Перед умножением умножьте входные данные по модулю, чтобы убедиться, что результат не превышает Number.MAX_SAFE_INTEGER
2. Выполните умножение после разделения входных данных на два 16-битных значения и рекомбинируйте
3. Используйте различные магические числа в зависимости от входных данных, чтобы убедиться, что я остаюсь в двойном диапазоне целых чисел

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

Пожалуйста, загляните в Math.imul.

Это умножает числа на 32-битные целые числа и просто усекает биты переполнения.