Perl で一意の識別子を作成するにはどうすればよいですか?

Question

さまざまなユーザーが実行したテスト結果のファイル指向データベースを作成しています。このためには、データベース内のすべてのエントリに対して一意の ID を生成する必要があります。ID は次の要件を満たす必要があります。

• ID はかなり小さくする必要があります (最大 6 文字)。
• すべてのテスト ケースとユーザーの組み合わせごとに、毎回同じ ID が生成される必要があります

私が試したのは、シード値 31 の単純な BKDR ハッシュ関数であり、次のように ord() 関数を使用しました。

@chars = split(//,$hash_var);

$hash = 0;
$seed = 31;

foreach $char ( @chars ) {
   if( $char !~ m/\d/ ) {
       $hash = ( $seed * $hash ) + ord( $char );
   }  
   else {
       $hash = ( $seed * $hash ) + $char ;
   }
}

$hash = ( $hash & 0x7FFFFFFF ) % 1000;
$hash = "$chars[0]$chars[$#chars]$hash" ;

これにより、さまざまな組み合わせで同じ結果が得られる場合があります。つまり、一意性が観察されません。これを達成する他の方法はあるのでしょうか?シード値を変更すると、一意性の実現に役立ちますか?

Answer 1

あなたの問題の一部は、あなたが浮動小数点演算を使用していて、BKDRはほぼ確実に整数演算を希望していることかもしれません。あなたが言っているバグを修正することができます。

my @chars = split(//,$hash_var);

my $hash = 0;
my $seed = 31;

for my $char ( @chars ) {
   use integer;
   if( $char !~ m/\d/ ) {
       $hash = ( $seed * $hash ) + ord( $char );
   }  
   else {
       $hash = ( $seed * $hash ) + $char ;
   }
}

$hash = ( $hash & 0x7FFFFFFF ) % 1000;
$hash = "$chars[0]$chars[$#chars]$hash" ;

役立つかもしれないもう一つの微調整は、最初と最後以外の文字を使用しています。最初と最後の文字が同じになりがち場合は、ハッシュに何の一意性を追加しません。

また、あなたの希望のサイズに結果を（ダイジェスト:: MD5で利用可能）MD5などのより良いハッシュ関数を使用してトリミングすることがあります。しかし、あなたはすべてのハッシュを使用しているという事実は、あなたが衝突を持っていることの危険性を実行することを意味します。

Answer 2

あなたは256人の以上のユーザーおよび/またはユーザーあたり65536以上のテストケースを持っていますか？ない場合は6つの文字は大丈夫だと思うので、あなたは65535からちょうど0 .. 255からのインデックスユーザーとテストケースとは、16進数の文字列としてエンコードすることができます。

あなたはそれ以上のユーザーまたはテストケースを持っている場合は、

、私は再び、インデックス、その後ユーザーとテストケースとは、人間には実際には4つのバイトを取ると、実装するのは簡単だろう32ビット整数にそれらを組み合わせることが、少し難しいでしょうます。

いずれにせよ、私はあなたのユーザー名とテストケースの情報を与えられていると仮定しています。そのインデックス番号にユーザーとテストケースをマップするために%usersと%cases

：ちょうど2つの縛らハッシュを保ちます。

Answer 3

あなたは多くのユーザーを持っていない場合は、

/このような単純な解決策は十分であるかもしれないテストケース。あなたは制限を追加（そしておそらくそれを格納する際の整数をパック）する必要があると思います。

vinko@parrot:~# more hash.pl
use strict;
use warnings;

my %hash;
my $count = 0;

sub getUniqueId {

        my $_user = shift;
        my $_test = shift;
        my $val;

        my $key = $_user."|".$_test;
        if (defined $hash{$key}) {
                $val = $hash{$key};
        } else {
                $hash{$key} = $count;
                $val = $count;
                $count = $count + 1;
        }
        return $val;
}

my @users = qw{ user1 user2 user3 user4 user5 user3 user5 };
my @testcases = qw{ test1 test2 test3 test1 test1 };

for my $user (@users) {
        for my $test (@testcases) {
                print "$user $test: ".getUniqueId($user,$test)."\n";
        }
}
vinko@parrot:~# perl hash.pl
user1 test1: 0
user1 test2: 1
user1 test3: 2
user1 test1: 0
user1 test1: 0
user2 test1: 3
user2 test2: 4
user2 test3: 5
user2 test1: 3
user2 test1: 3
user3 test1: 6
user3 test2: 7
user3 test3: 8
user3 test1: 6
user3 test1: 6
user4 test1: 9
user4 test2: 10
user4 test3: 11
user4 test1: 9
user4 test1: 9
user5 test1: 12
user5 test2: 13
user5 test3: 14
user5 test1: 12
user5 test1: 12
user3 test1: 6
user3 test2: 7
user3 test3: 8
user3 test1: 6
user3 test1: 6
user5 test1: 12
user5 test2: 13
user5 test3: 14
user5 test1: 12
user5 test1: 12