固定范围数字的双向散列


Two-way hashing of fixed range numbers

我需要创建一个函数,该函数以0-N范围内的单个整数为自变量,并返回相同范围内看似随机的数字。

每个输入数字应该始终有一个输出,并且应该始终相同。

这样的函数会产生这样的东西:

f(1) = 4
f(2) = 1
f(3) = 5
f(4) = 2
f(5) = 3

我相信这可以通过某种哈希算法来实现?我不需要任何复杂的东西,只是不需要像f(1) = 2f(2) = 3等太简单的东西。

最大的问题是,我需要这是可逆的。例如,上表应该是真的从左到右以及从右到左,使用不同的函数进行从左到左的转换也可以。

我知道最简单的方法是创建一个数组,对其进行混洗,然后将关系存储在数据库或其他文件中,但由于我需要N相当大,如果可能的话,我希望避免这种情况。

编辑:对于我的特殊情况,N是一个特定的数字,它正好是16777216(64^4)。

如果范围总是二次方——比如[016777216)——那么你可以使用exclusive或就像@MarkBaker建议的那样。如果你的范围不是二次方,它就不那么容易工作了。

你可以使用模N的加法和减法,尽管这些单独太明显了,所以你必须将它与其他东西结合起来。

你也可以做模N的乘法运算,但反过来很复杂。为了更简单,我们可以隔离最下面的八位,并将其相乘,然后以不干扰这些位的方式将其相加,这样我们就可以再次使用它们来反转运算。

我不懂PHP,所以我将用C语言给出一个例子。也许是一样的。

int enc(int x) {
  x = x + 4799 * 256 * (x % 256);
  x = x + 8896843;
  x = x ^ 4777277;
  return (x + 1073741824) % 16777216;
}

要解码,请按相反顺序播放操作:

int dec(int x) {
  x = x + 1073741824;
  x = x ^ 4777277;
  x = x - 8896843;
  x = x - 4799 * 256 * (x % 256);
  return x % 16777216;
}

1073741824必须是N的倍数,256必须是N因子,如果N不是2的幂,则不能(一定)使用exclusive或(^在C中是exclusive,我假设在PHP中也是)。其他数字你可以随意摆弄,添加和删除阶段。

在这两个函数中添加1073741824是为了确保x保持正;这是为了使模运算永远不会给出负的结果,即使在我们从x中减去值之后,这可能会使它在过渡期间变为负。

我提供了描述在生成研究数据集时如何"随机"地打乱9位数的SSN。这不会替换或散列SSN。它重新排序数字。如果你不知道数字被打乱的顺序,很难把它们放回正确的顺序。我有一种直觉,这不是提问者真正想要的。所以,如果这个答案被认为偏离了主题,我很乐意删除它。

我知道我有9个数字。因此,我从一个按顺序有9个索引值的数组开始:

$a = array(0,1,2,3,4,5,6,7,8);

现在,我需要把一个我能记住的键变成一种打乱数组的方式。每次对同一个键的洗牌顺序必须相同。我用了几个技巧。我用crc32把一个字变成一个数字。我使用srand/rand来获得随机值的可预测顺序。注意:mt_rand不再产生具有相同种子的相同随机数字序列,所以我必须使用rand。

srand(crc32("My secret key"));
usort($a, function($a, $b) { return rand(-1,1); });

数组$a仍然有数字0到8,但它们被打乱了。如果我使用相同的关键字,我每次都会得到相同的洗牌顺序。这让我每个月都重复一遍,得到同样的结果。然后,使用一个打乱的数组,我可以从SSN中挑选数字。首先,我确保它有9个字符(一些SSN是作为整数发送的,并且省略了前导0)。然后,我通过使用$a选择数字来构建一个掩码SSN。

$ssn = str_pad($ssn, 9, '0', STR_PAD_LEFT);
$masked_ssn = '';
foreach($a as $i) $masked_ssn.= $ssn{$i};

$masked_ssn现在将拥有$snn中的所有数字,但顺序不同。从技术上讲,有些关键字会使$a在洗牌后成为原始有序数组,但这种情况非常罕见。

希望这是有道理的。如果是这样的话,你可以做得更快。如果将原始字符串转换为字符数组,则可以打乱字符数组。你只需要每次都重新设定rand。

$ssn = "111223333"; // Assume I'm using a proper 9-digit SSN
$a = str_split($ssn);
srand(crc32("My secret key"));
usort($a, function($a, $b) { return rand(-1,1); });
$masked_ssn = implode('', $a);

从运行时的角度来看,这并不是很快,因为rand是一个相当昂贵的函数,而且在这里运行rand要多得多。如果你像我一样屏蔽了数千个值,你会想要使用一个只洗一次的索引数组,而不是对每个值都洗一次。

现在,我该如何撤消它?假设我对索引数组使用第一个方法。它将类似于$a={5,3,6,1,0,2,7,8,4}。这些是按屏蔽顺序的原始SSN的索引。所以,我可以很容易地构建原始的SSN。

$ssn = '000000000'; // I like to define all 9 characters before I start
foreach($a as $i=>$j) $ssn[$j] = $masked_ssn{$i};

正如您所看到的,$i在掩码SSN中从0计数到8$j计数5、3、6…,并将来自屏蔽SSN的每个值放在原始SSN的正确位置。

看起来您得到了很好的答案,但仍然有其他选择。线性同余生成器(LCG)可以提供1对1映射,并且使用欧几里德算法已知它是可逆的。对于24位

Xi = [(A * Xi-1) + C] Mod M
where M = 2^24 = 16,777,216
A = 16,598,013
C = 12,820,163

对于LCG的可逆性,请查看可逆伪随机序列生成器