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

我正在尝试生成从（比方说）无符号 32 位内部 ID 派生的非连续人类可读订单代码，该 ID 从 1 开始，并针对每个新订单自动递增。

在下面的示例代码中，每个$hash是独一无二的吗？ （我计划对$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 编码的结果md5($order_id)对我来说太长了。

在下面的示例代码中，每个$hash是独一无二的吗？

Almost.（我猜，这意味着“不，但是以一种很容易修复的方式”。）您的函数由一系列独立的步骤组成；当且仅当这些步骤中的每一步都是双射的（可逆的）时，整体函数才是双射的（可逆的）。 （你明白为什么吗？）

现在，每个步骤都具有以下形式之一：

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

with NUM_BITS != 0.

我们实际上可以将它们视为单一形式的变体，将前者视为almost相当于这个：

  $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;

and (x ^ y) ^ y == x ^ (y ^ y) == x ^ 0 == x，因此显然与常量值进行异或运算是可逆的（通过与相同值重新进行异或运算）；所以我们必须证明这是双射的：

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

每当NUM_BITS != 0.

现在，我没有写出严格的证明，所以我只是给出一个single如何扭转这种情况的合理示例。假设$key ^ ($key << 9) is

0010 1010 1101 1110 0010 0101 0000 1100

我们如何获得$key？嗯，我们知道最后九位$key << 9都是零，所以我们知道最后九位$key ^ ($key << 9)与最后九位相同$key. So $key好像

bbbb bbbb bbbb bbbb bbbb bbb1 0000 1100

so $key << 9好像

bbbb bbbb bbbb bb10 0001 1000 0000 0000

so $key好像

bbbb bbbb bbbb bb00 0011 1101 0000 1100

（通过异或运算$key ^ ($key << 9) with $key << 9), so $key << 9好像

bbbb b000 0111 1010 0001 1000 0000 0000

so $key好像

bbbb b010 1010 0100 0011 1101 0000 1100

so $key << 9好像

0101 1000 0111 1010 0001 1000 0000 0000

so $key好像

0111 0010 1010 0100 0011 1101 0000 1100

所以 。 。 。为什么我说“几乎”而不是“是”？为什么你的哈希函数不是完美双射？这是因为在 PHP 中，按位移位运算符>> and <<不是quite对称，同时$key = $key ^ ($key << NUM_BITS)是完全可逆的，$key = $key ^ ($key >> NUM_BITS)不是。 （在上面，当我写到这两种类型的步骤是“almost等价”，我真的meant那个“几乎”。这很重要！）你看，而<<像对待任何其他位一样对待符号位，并将其移出（在右侧引入零位），>>特别对待符号位，并“扩展”它：它在左侧引入的位等于符号位。 （注意：您的问题提到“无符号 32 位”值，但 PHP 实际上并不支持该值；它的按位运算始终处于开启状态signed整数。）

由于这个符号扩展，如果$key以一个开头0, then $key >> NUM_BITS以一个开头0， 而如果$key以一个开头1, then $key >> NUM_BITS也以一个开头1。在任一情况下，$key ^ ($key >> NUM_BITS)将从0。你已经损失了一点点熵。如果你给我$key ^ ($key >> 9)，并且不要告诉我是否$key是负数，那么我能做的最好的就是计算两个可能的值$key：一个负值，一个正值或零。

您执行两个使用右移而不是左移的步骤，因此您丢失了两位熵。 （我轻轻挥手——我实际上证明的是你输了at least一位和at most两位 - 但我相信，由于这些右移步骤之间的步骤的性质，您实际上会丢失两个完整位。）对于任何给定的输出值，恰好有四个不同的输入值可以产生它。所以它不是唯一的，但它是almost独特的;并且可以通过以下任一方法轻松修复：

• 将两个右移步骤更改为使用左移；或者
• moving both of the right-shift steps to the start of the function, before any left-shift steps, and saying that outputs are unique for inputs between 0 and 2³¹−1 rather than inputs between 0 and 2³²−1.