代码之家 › 专栏 › 技术社区 › piojo

在Perl 6中使用自定义哈希函数设置/哈希

raku hashset overloading

piojo · 技术社区 · 8 年前

我的问题与 user defined function in set operations ,但我认为我可以切入问题的核心:

如何选择特定的哈希函数?例如,如果我想进行基于值的匹配,而不是引用匹配,并且我想查看是否存在某个元组(或者简单地删除它):

my %data := SetHash.new: (1, 2), (3, 4);
%data{$(1, 2)}:delete; # False

在C++或C#中,我可以为构造函数提供一个自定义哈希/比较函数。在C#中,如果我的数据类型是 struct (值类型而非引用类型)。Perl 6在某种程度上对 Pair (如果该对不包含任何容器),但我不知道如何使其适用于任何其他复杂类型。

一方面,我明白了为什么这不是最安全的操作——很容易定义其哈希代码在插入后可以更改的对象。但这并没有停止。NET和C++STL不允许自定义哈希。

API的一种可能用法(受 this ,最初来自Boost)将是:

class MyHasher does Hasher of Array[Int] {
  method get-hash-value(Int @array) {
    reduce
      -> $a, $b {$a +^ ($b + 0x9e3779b97f4a7c16 + ($a +< 6) + ($a +> 2))},
      0,
      |@array;
  }
  method equals(Int @a, Int @b) { @a eqv @b; }
}

my %data := SetHash.new(
  my Int @=[1, 2], my Int @=[3, 4],
  :hasher(MyHasher.new)
);
say %data{$[1, 2]}; # should be True

这将是哈希器角色,如果Perl 6的核心库还不存在,那么它应该由Perl 6的核心库提供:

role Hasher[::T=Any] { method equals(T $a, T $b --> Bool) { ... }; method get-hash-value(T $obj) { ... } }

解决方案: 目前,最合理的解决方案是重写类的 .WHICH 方法,该方法用作哈希值并用于等式测试。我给出了一个模拟值类型的哈希键类的示例 here . 它几乎与每个哈希对象的自定义哈希函数一样通用,因为可以在创建哈希时声明密钥类型。(这不能用于 Set 自从 设置 未参数化。)

1 回复 | 直到 7 年前

Brad Gilbert 7 年前

散列的工作方式是使用键存储值,然后使用完全相同的键检索值。

对于Str和Int等值类型,您可以有多个实例,它们的作用就像它们是完全相同的值一样。所以 42 和 40Â +Â 2 就好像它们是完全相同的实例,即使它们不是。

所以这是可行的:

my %h{Any}; # defaults to Str keys

%h{'abc'} = 42;

my ($a,$b,$c) = 'a', 'b', 'c';

say %h{"$a $b $c"}; # 42

%h{42} = 'The answer';

say %h{"42"}; # (Any)
say %h{42}; # The answer

实际上,没有一种工具可以让几个不同的值仅为一个哈希值假装为相同的值。

'abc' === 'cba'; # False

'abc'.WHICH eq 'cba'.WHICH; # basically how the above works

我认为你要求的是一个不应该添加的功能。

有一个 WHICH 方法,该方法只应用于在整个语言中使两个值在任何地方都相同。

say 42.WHICH.perl;       # ValueObjAt.new("Int|42")
say (40 + 2).WHICH.perl; # ValueObjAt.new("Int|42")
42 === (40 + 2);         # True

say Hash.new.WHICH.perl; # ObjAt.new("Hash|94014087733456")
say Hash.new.WHICH.perl; # ObjAt.new("Hash|94014087735232")

注意,对于 Hash.new 它们不匹配,因为它们是不同的实例,可能会随着时间的推移而改变。

例如,这是一件好事。假设您有两个名为“Bob”的员工。

my $a = Employee.new( name => 'Bob' );
my $b = Employee.new( name => 'Bob' );

my %salary{Employee};

%salary{$a} = 1200; # arbitrary number for an example
%salary{$b} = 2000;

注意,通过重写 其中 可能会意外给出 BobÂ $a 加薪。

基本上,这可能不是一个好主意 .WHICH 除非你确切地知道自己在做什么,而且你有很好的理由这么做。

所以你不能/不应该那样做。至少不是你尝试的方式。

相反,创建一个新的关联类,该类按您想要的方式工作。

role Custom-Str-Hasher {
  method hashed ( --> Str:D ){â¦}
}

class Custom-SetHash is SetHash {
  multi method AT-KEY ( Custom-Str-Hasher:D $key ) is rw {
    self.AT-KEY( $key.hashed() ); # call base class's method
  }
}


class Foo does Custom-Str-Hasher {
  has Str:D $.Str is required;

  # required by the Custom-Str-Hasher role
  method hashed ( --> Str:D ){
    $!Str.comb(/\w/).unique.sort.join;
    # 'b cb a' â 'abc' and 'aaababcccba' â 'abc'
  }
}

my $a = Foo.new(:Str('b cb a'));
my $b = Foo.new(:Str('aaababcccba'));

my %h is Custom-SetHash; # use a different class than the default

%h{$a} = True;
say %h{$b}; # True;

put $a; # b cb a
put $b; # aaababcccba

请注意,以上只是一个简单的例子,对于一个真实的例子,我会改变很多事情。首先, %h{'abc'} 也会回来 True 因为我实现 AT-KEY 方法它还缺少一系列方法,例如 ASSIGN-KEY 和 DELETE-KEY .