Ну это же элементарно: для перевода числа в N-разрядность просто делим его на N: остаток это значение разряда, частное это все высшие разряды.

Например 137 переводим в HEX:
137/16 = 8 частное 9 остаток
8 / 16 = 0 частное 8 остаток
Итого 137 = 89h

Какие ложные срабатывания? Если формат хранения допускает избыточность, то на берегу проверяй соответствие значения формату, т.е. в расчеты должны идти только правильные значения, мусор надо убирать на входе.

Делить не придется, надо будет складывать умножать. Мы же на вход получаем ключ в N-рязрядном представлении и его надо преобразовать в двоичное, т.е. в число, а для этого надо умножать, например 4 разряда:

Еще подумал, если умножать и складывать так

где N ^X заранее посчитано, то такая конструкция параллелится процом во время выполнения и займет пару тактов, т.е. не тормоз.

Ты меня запутал. Похоже мы по-разному понимаем твой пост 22051757
Я так понимаю что речь была о выходе за границы алфавита, т.е. при алфавите в 137 разрядов, чтобы не делить, делаем редукцию в 256, в результате часть разрядов ключа окажется за пределами алфавита, поэтому тут надо изобретать какое-то преобразование к алфавиту ключа. Причем алфавит еще и рваный, т.к. это строка. Можно без деления обойтись, например таблицей.


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

Как вариант алгоритма быстрой редукции 20 байт хэша в 12 байт алфавита:
1. При старте делаем таблицу 4 Кб (2 ¹² элементов) , где зациклен алфавит ключа: "1234567890123456....".
2. 12 раз от хэша взять по полтора байта (12 бит), использовать каждый как индекс массива, в итоге получаем разряд ключа.

Никаких делений не надо. Получение элемента по индексу массива легкая операция и плюсом проц запараллелит получение разных разрядов.

ИМХО одного байта для индекса недостаточно, т.к. тогда таблица будет 256 байт и значения будут неравномерно распределены, некоторые один раз, некоторые два, т.е. вероятность получения одних вдвое выше других. При 4 Кб (2 ¹² ) и алфавите 137 символов повторов будет 29-30, т.е. разброс 3%.

Тут маленькая проблема, одна цепочка может быть миллиарды ключей, сохранить в памяти целиком не получится. Думаю надо точечно хранить, например каждую миллионную точку

Я уже написал как: каждую миллионную точку, т.е. построить глобальное хранилище миллионных точек всех считающих потоков и синхронизировать в каждый. Т.е. в каждом считающем потоке будет миллион уже обсчитанных ключей, 10-12 Мб, возможно больше потребуется, тут все эмпирически определяется, хранилище надо будет синхронизировать регулярно и каждый свежий ключ проверять на наличие в хранилище. А может Амдал не даст развернуться и надо будет изобретать что-то еще.

Собственно можно уже написать, но зачем? Уже написано.

Не будет, тут объемы данных на порядки выше кэшей проца, тут бы в своп не уйти и то уже замечательно. Хотя уйти в своп в NMVe это не так уж и медленно.

PS Интересно, есть ли управление некэшированием, т.е. дать понять процу не кэшировать то, что заведомо известно в кэше искать не потребуется.

Верно, в данной задаче надо просчитывать чтобы не было свопа, а не непопадание в кэши.


Это общие рекомендации. Я их вообще не понимаю, хотя догадываюсь что они основаны на ожидании какой-нибудь задачи, которая увидит сколько есть реальной памяти и постарается занять ее всю. В виндовсе по умолчанию на всякий случай еще умножили на 1.5.

Например если я воткнул 32 Гб оперативки в свой комп, то я ожидаю что свопа не будет вообще, но виндовс по дефолту займет 48 Гб под своп на моем SSD в 110 Гб (((

Я в виндовсе всегда принудительно выставляю минимальный размер свопа 16 Мб, максимальный - рекомендуемый 1.5 от размера памяти. Еще гибернайт выключаю, т.к. состояние памяти туда скидывается перед усыплением, но по факту он нафиг не нужен, т.к. все ширпотребные проги периодически сохраняют свое несохраненное состояние и при старте после сбоя предлагают к нему вернуться.
Реальный размер свопа у меня обычно 16 Мб, иногда до 1 Гб вырастает на компах где памяти 2-4 Гб.