Может есть алгоритм равномерного распределения на основе хэша SHA256?
Есть массив [1... n] объектов. Кол-во элементов может увеличиваться, т.е. n постепенно растет.
Мы получаем произвольный хэш SHA256. Хочется иметь какой-то алгоритм, который определяет для этого хэша номер объекта из массива, таким образом, чтобы при поступлении очередного хэша брался новый произвольный номер в массиве, но при этом соблюдались условия:
1. Распределение должно быть близким к равномерному
2. Метод должен быть воспроизводимым, т.е. при выпадении определенно хэша, должен выдавать ту же позицию в массиве каждый раз, когда выпадает этот хэш
3. Допустимо для разных хэшей соответствие одной и той же позиции в массиве, при соблюдении условия 1.
4. Хэшей будет больше чем n.
Александр, Тогда только запоминать, какому хэшу соответствует какой номер и приписывать новые хэши к тем номерам, у которых пока минимальное число закреплённых хэшей.
В предельном случае это потребует таблицы соответствия на 2256 элементов.
Александр, Без запоминания не получится.
Если любой пришедший хэш A отображался в значение k, где 1 ⩽ k ⩽ n, то при смене размера массива вновь пришедший хэш A по прежнему должен отображаться в k. Поскольку, A - любой хэш, то всё равно будет выполняться условие k ⩽ n.
Денис Загаевский, о псевдоравномерном. это идеал, к которому хочется стремиться.
количество хэшей растет гораздо быстрее количества элементов в массиве.
Александр,
"Метод должен быть воспроизводимым, т.е. при выпадении определенно хэша, должен выдавать ту же позицию в массиве каждый раз, когда выпадает этот хэш"
Это невозможно обеспечить при таких условиях.
Если вам надо, чтобы после увеличения n, хеши выдавали те же позиции - то это невозможно сделать равномерно без запоминания. Потому что пусть n=10 изначально - тогда ЛЮБОЙ хеш должен выдать значение меньше 10. А потом при увеличении n любой хеш, все-равно должен выдать 0-9. Пусть даже n станет 100000 - нельзя использовать добавленные позиции, кроме 10 первых.
Если вы хеш таблицу придумываете, то там при увеличении n все существующие хеши пересчитываются с новым n и все элементы переезжают на новые позиции. Как будто n всегда и было таким.
Нет, не хэш таблицу. Там ситуация такая, что есть массив участников, и им надо выдавать награды на основе хэша. Вот надо никого не обидеть и дать возможность проверить, что начислено честно, по алгоритму. может я задачу не так формулирую просто и есть другой путь.
Простой
