3

我正在为不同用户执行的一些测试结果创建一个面向文件的数据库。为此，我需要为数据库中的每个条目生成唯一 ID。id 必须满足以下要求：

  • ID 应该相当小（最多 6 个字符）
  • 对于每个测试用例和用户组合，每次都应生成相同的 id

我尝试的是一个简单的 BKDR 哈希函数，种子值为 31，并使用了 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" ;

这有时会导致各种组合的相同结果，即没有观察到唯一性。他们还有其他方法可以做到这一点吗？改变种子值是否有助于实现独特性。

4

3 回答 3

5

您是否拥有超过 256 个用户和/或每个用户超过 65536 个测试用例？如果没有，您可以从 0 .. 255 索引用户，从 0 .. 65535 开始测试用例，并将其编码为十六进制数字字符串，这样六个字符就可以了。

如果你有更多的用户或测试用例，我会再次索引用户和测试用例，然后将它们组合成一个 32 位整数，这实际上只需要 4 个字节并且实现起来很简单，但对人类来说稍微困难一些。

在任何情况下，我都假设您获得了用户名和测试用例信息。只需保留两个绑定的哈希值：%users并将%cases用户和测试用例映射到他们的索引号。

于 2009-06-30T12:41:19.137 回答
3

您的部分问题可能是您正在使用浮点数学，而 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（在 Digest::MD5 中可用）并将结果修剪为您想要的大小。但是，您完全使用哈希这一事实意味着您冒着发生冲突的风险。

于 2009-06-30T12:55:07.297 回答
1

如果您没有很多用户/测试用例，那么像这样的简单解决方案可能就足够了。您必须添加限制（并且可能在存储整数时打包整数）。

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
于 2009-06-30T12:52:29.177 回答