人类可读订单代码的完美哈希函数

Question

我正在尝试生成非顺序的人类可读订单代码,这些订单代码派生自(比方说)一个从1开始的无符号32位内部id,并为每个新订单自动递增.

在我下面的示例代码中,每个$hash都是唯一的吗？(我计划对其进行base34编码$hash,使其具有人类可读性.)

<?php
function int_hash($key) {
  $key = ($key^0x47cb8a8c) ^ ($key<<12);
  $key = ($key^0x61a988bc) ^ ($key>>19);
  $key = ($key^0x78d2a3c8) ^ ($key<<5);
  $key = ($key^0x5972b1be) ^ ($key<<9);
  $key = ($key^0x2ea72dfe) ^ ($key<<3);
  $key = ($key^0x5ff1057d) ^ ($key>>16);
  return $key;
}

for($order_id = 1; $order_id <= PHP_INT_MAX; ++$order_id) {
  $hash = int_hash($order_id);
}
?>

如果没有,有没有关于如何更换的建议int_hash？

结果说,base34编码a md5($order_id)对我来说太长了.

Answer 1

在我下面的示例代码中,每个$hash都是唯一的吗？

几乎.(我猜,这意味着"不,但是以一种容易修复的方式".)你的功能包括一系列独立的步骤; 当且仅当这些步骤中的每一步都是时,整体功能才是双射的(可逆的).(你知道为什么吗？)

现在,每个步骤都有以下形式之一:

  $key = ($key ^ CONSTANT) ^ ($key >> NUM_BITS);
  $key = ($key ^ CONSTANT) ^ ($key << NUM_BITS);

与NUM_BITS != 0.

我们实际上可以将这些视为单个表单的变体,通过查看前者几乎等同于此:

  $key = invert_order_of_bits($key); # clearly bijective
  $constant = invert_order_of_bits(CONSTANT);
  $key = ($key ^ $constant) ^ ($key << NUM_BITS);
  $key = invert_order_of_bits($key); # clearly bijective

所以我们需要的是证明这一点:

  $key = ($key ^ CONSTANT) ^ ($key << NUM_BITS);

是双射的.现在,XOR是可交换和关联的,所以上面等同于:

  $key = $key ^ ($key << NUM_BITS);
  $key = $key ^ CONSTANT;

并且(x ^ y) ^ y == x ^ (y ^ y) == x ^ 0 == x,如此明显地,具有恒定值的异常是可逆的(通过以相同的值重新异或); 所以我们要表明的是这是双射的:

  $key = $key ^ ($key << NUM_BITS);

每当NUM_BITS != 0.

现在,我不写一个严格的证明,所以我只给一个单一的如何扭转这种说理,出来的例子.假设$key ^ ($key << 9)是

0010 1010 1101 1110 0010 0101 0000 1100

我们如何获得$key？好吧,我们知道最后9位$key << 9都是零,所以我们知道最后9位与最后9位$key ^ ($key << 9)相同$key.所以$key看起来像

bbbb bbbb bbbb bbbb bbbb bbb1 0000 1100

所以$key << 9看起来像

bbbb bbbb bbbb bb10 0001 1000 0000 0000

所以$key看起来像

bbbb bbbb bbbb bb00 0011 1101 0000 1100

(由-ING XOR $key ^ ($key << 9)用$key << 9),所以$key << 9看起来像

bbbb b000 0111 1010 0001 1000 0000 0000

所以$key看起来像

bbbb b010 1010 0100 0011 1101 0000 1100

所以$key << 9看起来像

0101 1000 0111 1010 0001 1000 0000 0000

所以$key看起来像

0111 0010 1010 0100 0011 1101 0000 1100

所以...为什么我说"差不多"而不是"是"？为什么你的哈希函数不完全是双射的？这是因为在PHP中,按位移位运算符>>和<<不是很对称的,而$key = $key ^ ($key << NUM_BITS)完全是可逆的,$key = $key ^ ($key >> NUM_BITS)是不是.(上面,当我写这两种类型的步骤" 几乎相同"时,我的意思是"差不多".它有所不同!)你看,然后<<像对待任何其他位一样处理符号位,并将其移出存在(在右边引入一个零位),>>特别处理符号位,并"扩展"它:它在左边引入的位等于符号位.(注意:你的问题提到"无符号32位"值,但PHP实际上并不支持它;它的按位运算总是在有符号整数上.)

由于这种符号扩展,如果$key有一个开头0,然后$key >> NUM_BITS用一开始0,如果$key有一个开始1,随后$key >> NUM_BITS也开始了1.无论哪种情况,$key ^ ($key >> NUM_BITS)都会以a开头0.你已经失去了一点熵.如果你给我$key ^ ($key >> 9),并且不告诉我是否$key为负,那么我能做的最好的是计算两个可能的值$key:一个是负数,一个是正数还是零.

您执行两个使用右移而不是左移的步骤,因此您丢失了两位熵.(我微微挥手 - 我实际证明的是你至少丢失了一位,最多两位 - 但我相信,由于这些右移步骤之间的步骤的性质,实际上你输了两个满位.)对于任何给定的输出值,有四个不同的输入值可以产生它.所以它不是唯一的,但它几乎是独一无二的; 它可以通过以下方式轻松修复:

• 将两个右移步骤改为使用左移; 要么
• 在任何左移步骤之前将两个右移步骤移动到函数的开始,并且说输出对于0到2 ³¹ -1之间的输入而不是0到2 ³² -1 之间的输入是唯一的.