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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了php – 人类可读订单代码的完美哈希函数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3574字，纯文字阅读大概需要6分钟。

内容图文

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

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

<?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)对我来说太长了.

解决方法:

In my example code below, will every $hash be unique?

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

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

  $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？好吧,我们知道$key的最后九位<< 9都是零,所以我们知道$key ^($key<< 9)的最后9位与$key的最后9位相同.所以$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

(通过使用$key<< 9)对$key ^($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)不是完全可逆的. (上面,当我写到两种类型的步骤“几乎相同”时,我的意思是“差不多”.它有所不同！)你看,而<<像任何其他位一样处理符号位,并将其移出存在(在右侧引入零位),>>特别对待符号位,并“扩展”它：它在左边引入的位等于符号位. (N.B.你的问题提到“无符号32位”值,但PHP实际上并不支持它;它的按位运算总是在有符号整数上.)

由于此符号扩展,如果$key以0开头,则$key>> NUM_BITS以0开头,如果$key以1开头,则$key>> NUM_BITS也以1开头.在任何一种情况下,$key ^($key>> NUM_BITS)都将以0开头.您已经丢失了一位熵.如果你给我$key ^($key>> 9),并且不告诉我$key是否为负数,那么我能做的最好就是为$key计算两个可能的值：一个是负数,一个是正数 – 或零.

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

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

内容总结

以上是互联网集市为您收集整理的php – 人类可读订单代码的完美哈希函数全部内容，希望文章能够帮你解决php – 人类可读订单代码的完美哈希函数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端