Perl―ハッシュの並び方の法則は？

srd 1999/12/22(水) 22:33:06
以下のように実験すると、結果は「dd aa bb cc」となります。キーの文字によって並び方が異なります。

%Hash = (aa => "", bb => "", cc => "", dd => "");
foreach (keys %Hash) { print "$_ "; }

ハッシュに代入した通りの順番で取り出すにはそれなりに工夫しないといけないことは上記の実験や ../199811/98110098.htm を見たりして分かったのですが、一体この並び方にはどんな法則性があるのでしょうか。気になって仕方がありません。どなたか教えてください。

B-Cus 1999/12/22(水) 23:42:32
結局わかってないんだけど、わかったような気になるかもしれないレス。

ハッシュというのは、ある値を入力すると、それに対応する
別の値 (ハッシュ値) を返す仕組みです。ハッシュ値を計算する
関数をハッシュ関数と言います。

@buf=qw(ab 1 cdef 22 ghijk 333);

for ( $i=0 ; $i<@buf ; $i+=2 ){
  $key = $buf[$i];
  $value = $buf[$i+1];
  $hash = &get_hash($key);

  print "hash\{$key\} = $value\n";
  $array[$hash]=$value;
}
print "hash cdef = $array[&get_hash('cdef')]\n";
exit;

sub get_hash { # ハッシュ値を返す
  local($_)=@_;

  print "in get_hash($_) ... ";
  $sum=0;
  @chars = split(//,$_);
  foreach (@chars){
    printf "%d ",ord($_);
    $sum += ord($_);
  }
  printf "合計=%d 合計%100=%d\n",$sum,$sum%100;
  return $sum;
}

実行結果:
  in get_hash(ab) ... 97 98 合計=195 合計%100=95
  hash{ab} = 1
  in get_hash(cdef) ... 99 100 101 102 合計=402 合計%100=2
  hash{cdef} = 22
  in get_hash(ghijk) ... 103 104 105 106 107 合計=525 合計%100=25
  hash{ghijk} = 333
  in get_hash(cdef) ... 99 100 101 102 合計=402 合計%100=2
  hash cdef = 22

これはハッシュを使わず、配列でハッシュもどきを実現したものです。
　ab=>1,cdef=>22,ghijk=>333
のようなデータがあると、キーとなる ab や cdef を get_hash に
渡します。すると get_hash は、各文字の文字コードを合計し、
それを100で割った余りを算出します。それがハッシュ値となります。

そのハッシュ値を使って、$array[ハッシュ値]=$value と、
配列に代入します。値を取り出すときは
  $array[&get_hash('cdef')]
とすれば、一発で cdef に対応する値が得られるわけです。
配列を全部探索する必要はありません。これがハッシュというものの仕組みです。

で、この例では get_hash がハッシュ関数です。ここでの keys の
順番というのは「全文字コードの合計を100で割った余り」というものです。

perl ではどんなアルゴリズムでハッシュを求めているかは
知りませんが、ハッシュの順番というのは、結局ハッシュ値を
求めるアルゴリズムに依存します。本当に知りたいなら、
perl のソースを読むしかないと思います。

なお、この「全文字コードの合計を100で割った余り」というのは
ハッシュ関数としてはひどいものであって、abc も acb も cba も
全て同じハッシュ値になってしまいます。また、ハッシュ値が重なった
ときの対策も全くしていません。

つまり、
  ・高速にハッシュ値を計算できる。
  ・なるべくハッシュ値が重ならない
  ・ハッシュ値が重なっても、それなりに高速に処理できる
というのが優秀なハッシュ関数と言えます。そういうハッシュ関数を
知りたければ、クヌース先生のアルゴリズムの教科書などを読んで下さい。

srd 1999/12/23(木) 10:18:57
[[解決]]
確かに「わかったような気に」はなりました。Perlのソースを読むほど究めたいわけでもありませんので，これでひとまず解決とします。ありがとうございました。

[上に] [前に] [次に]