Я хотел бы знать, существует ли функция от n-битных чисел до n-битных чисел, которая имеет следующие характеристики:
- должно быть биективным
- Оба и должны быть вычислены довольно быстро
- должен вернуть число, которое не имеет существенной корреляции с его вводом.
Обоснование таково:
Я хочу написать программу, которая работает с данными. Некоторая информация данных хранится в бинарном дереве поиска, где ключ поиска является символом алфавита. Со временем я добавляю дополнительные символы в алфавит. Новые символы просто получают следующий свободный номер. Следовательно, дерево всегда будет иметь небольшой уклон к более мелким ключам, что вызывает большую перебалансировку, чем я думаю, что это необходимо.
Моя идея состоит в том, чтобы искажать номера символов с помощью , чтобы они широко распространялись по всему диапазону . Поскольку номера символов имеют значение только во время ввода и вывода, что происходит только один раз, применение такой функции не должно быть слишком дорогим.
Я думал об одной итерации генератора случайных чисел Xorshift, но я не знаю, как отменить его, хотя теоретически это должно быть возможно.
Кто-нибудь знает такую функцию?
Это хорошая идея?
Ответы:
Вы можете использовать хеширование Фибоначчи , а именно
.hF(k)=k⋅5√−12−⌊k⋅5√−12⌋
Для вы получите n попарно различных чисел (примерно), равномерно распределенных в [ 0 , 1 ] . Масштабируя до [ 1 .. M ] и округляя (вниз), вы получите примерно равномерное распределение чисел в этом интервале.k=1,…,n n [0,1] [1..M]
Например, это масштабированные до [ 0..10000 ] (исходная последовательность слева, отсортированная справа):hF(1),…,hF(200) [0..10000]
Это пример того, что Кнут называет мультипликативным хешированием . Для размера слова компьютера, A некоторое целое число относительно простого числа w и M количество необходимых адресов, мы используемw A w M
как функция хеширования. Сказанное следует с (убедитесь, что вы можете вычислить его с достаточной точностью). Хотя это также работает с любым другим иррациональным числом, кромеϕ-1, это одно из двух чисел, которые приводят к «наиболее равномерно распределенным» числам.A/w=ϕ−1=5√−12 ϕ−1
Узнайте больше в книге «Искусство компьютерного программирования» , том 3 Дональда Кнута (глава 6.4 на стр. 513 во втором издании). В частности, вы поймете, почему полученные числа попарно различны (по крайней мере, если ) и как вычислить обратную функцию, если вы используете натуральное An≪M A и вместо ϕ - 1 .w ϕ−1
источник
Для битных входов эта функция работает:k
Ссылка: обратимая хеш-функция
источник