人間が読むことができる注文コードの完璧なハッシュ関数

Question

私は、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の交換方法について何か提案がありますか？

md5($order_id)をコードするbase34の結果は、私の好みのためには長すぎます。

Answer 1

私の例のコードでは、$hashは一意になりますか？

ほぼ。（あなたが「いいえ、しかし容易に修正できる方法で」を意味すると思います。）あなたの機能は一連の独立したステップで構成されています。それらのステップのすべてが1つだけである場合に限り、全体関数は全単射（可逆的）である。

（？あなたはなぜ参照ください）さて、各ステップは、以下のいずれかの形式がありますNUM_BITS != 0と

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

。

私たちは、実際にこのほぼ同等前者を表示することにより、単一の形のバリエーションとして、これらを扱うことができます。

$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ので、明らかに一定値とXOR-INGのは（同じ値で再XOR-INGのにより）可逆的です。いつでもNUM_BITS != 0

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

：私たちは示さなければならないすべては、これが全単射であるということです。

今、私は厳密な証明を書いていないので、の単一のを逆にする方法の例を挙げます。 $key^($key << 9)は、我々は$keyを入手するにはどうすればよい

0010 1010 1101 1110 0010 0101 0000 1100 

であると仮定？さて、$key << 9の最後の9ビットがすべてゼロであることがわかっているので、$key^($key << 9)の最後の9ビットは、最後の9ビットの$keyと同じです。だから、$keyので$key << 9が

bbbb bbbb bbbb bb10 0001 1000 0000 0000 

のように見えるので、$keyはそう$key << 9が

のように見える、（$key << 9と$key^($key << 9)をXOR-INGのことで）

bbbb bbbb bbbb bb00 0011 1101 0000 1100 

のように見えます

​​

のように見えます

bbbb b000 0111 1010 0001 1000 0000 0000 

ので$keyはそう$key << 9がそう$keyだから

0111 0010 1010 0100 0011 1101 0000 1100 

のように見えます

0101 1000 0111 1010 0001 1000 0000 0000 

のように見えます

bbbb b010 1010 0100 0011 1101 0000 1100 

のように見えます。 。 。なぜ私は「はい」ではなく「ほとんど」と言いますか？なぜあなたのハッシュ関数は完全に全身ではないのですか？ PHPでは、ビット単位のシフト演算子>>と<<はと全く同じではなく、の対称ではなく、$key = $key^($key << NUM_BITS)は完全に可逆ですが、$key = $key^($key >> NUM_BITS)はそうではありません。 （上記の2つのステップが「」と書かれたとき、私は実際にはがを意味していたということです。違いがあります！）<<は他のビットと同じように扱いますそれをシフトさせて（右にゼロビットを持ち込む）、>>は符号ビットを特別に扱い、それを「伸ばし」ます。左に持ち込むビットは符号ビットに等しくなります。 （NBは、あなたの質問は、「符号なし32ビット」の値に言及したが、PHPは実際にはサポートされません。そのビット演算はに常に符号付き整数。）

により、この符号拡張し、0と$key開始した場合、その後、 $key >> NUM_BITSは0で始まり、が1で始まる場合、$key >> NUM_BITSも1で始まります。いずれの場合も、$key^($key >> NUM_BITS)は0で始まります。あなたはちょうど1ビットのエントロピーを失ってしまった。あなたが私に$key^($key >> 9)を与えて、$keyが否定的であるかどうかを教えてくれないなら、$keyの2つの可能な値を計算するのが一番良いです。一つは負、一つは正またはゼロです。

左シフトの代わりに右シフトを使用する2つのステップを実行するので、2ビットのエントロピーが失われます。 （私は手を振っわずか—だ、私が実際に実証されたすべてのあなたが少なくとも 1ビットと高々 2ビット—を失うということですが、私は、そのため、これらの権利の間のステップの性質に自信 - シフト・ステップでは、実際には2つのフル・ビットを失います。）任意の出力値に対して、それを生成できる正確に4つの異なる入力値があります。だからユニークではありませんが、それはです。ほとんどです。

左シフトを使用する2つの右シフトステップを変更します。または
• 右シフトステップの両方を左シフトステップの前に移動し、出力が0と2の間の入力で一意であると言うと、 − 1の入力ではなく、0と2の間の入力