タグ

関連タグで絞り込む (0)

  • 関連タグはありません

タグの絞り込みを解除

programmingとProgrammingとhashに関するwebmarksjpのブックマーク (2)

  • perl - 配列をハッシュキーとして扱う : 404 Blog Not Found

    2007年10月24日20:00 カテゴリLightweight Languages perl - 配列をハッシュキーとして扱う コメント欄にも「教科書解」がなかったので。 Perl勉強中 - YoshioriのBlog #!/usr/bin/perl use strict; use warnings; my @array = qw/1 2 3/; my @array2 = qw/1 2 3/; my %hash; $hash{@array} = 'foo'; # ちょっと変更 print $hash{ @array2 }; # foo みたいなこと出来ないのかな? 教科書解は、こちら。 $hash{ join($;, @array) } = 'foo'; これは、 $hash{1,2,3} = 'foo'; $hash{qw/1 2 3/} = 'foo'; という、配列リテラルをキーに

    perl - 配列をハッシュキーとして扱う : 404 Blog Not Found
  • Cuckoo Hashing - Radium Software

    ハッシュテーブルからエントリーを検索する処理は,一般に定数時間で済むとされている。つまり,どんなにエントリーが増えても検索の速さは変わらない,ということ。データ構造の教科書には必ず載っていることだね。 でも実際には,ハッシュの衝突が起こった場合に,速度の低下が発生する可能性がある。例えば,一般的なチェイン法(オープンハッシュ)だと,衝突したエントリーに関して線形検索を行うことになるから,衝突が多ければ多いほど,定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing (カッコウ・ハッシング)は仕組みが面白い。こいつは,エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では,2つのハッシュ関数と,2つのテーブルを用いる。ここでは,2つのハッシュ関数をそれぞれ h1, h2 として,2つのテー

    Cuckoo Hashing - Radium Software
  • 1