ハッシュ法の実装

ハッシュ法

ハッシュ法は、検索アルゴリズムの一つで、各要素の値に応じて格納場所を管理するハッシュテーブルを用いて、データの検索を高速化する。ハッシュテーブルはキーを持つデータの集合に対して、動的な挿入、検索、削除を効率的に行うことができるデータ構造の1つである。

ハッシュテーブル

ハッシュテーブルはm個の要素を格納できる配列Tと、データのキーから配列の添字を決定する関数から構成されている。つまり、各データを挿入すべき位置をそのデータのキーを入力とした関数で求める。

衝突

ハッシュ法で不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成される可能性がある。これをハッシュ値の「衝突 (collision) 」呼ぶ。

use strict;
use warnings;
use utf8;
use Time::HiRes qw(gettimeofday tv_interval);
binmode(STDOUT, ":utf8");
use Data::Dumper;

&hash_algorithm;

sub hash_algorithm {
    my $t0 = [gettimeofday];
    print "命令の数を表す数値nを入力してください。\n";
    my $input_n = <STDIN>;

    print "n件の命令を入力してください。\n";
    my %input_orders_hash;
    my @result_arr;

    while (my $input_n_order = <STDIN>) {
        last if $input_n_order eq "end\n";
        chomp($input_n_order);
        my @tmp = split(/ /, $input_n_order);

        if ($tmp[0] eq 'insert') {
            $input_orders_hash{"$tmp[1]"} = $tmp[1];
        }
        if ($tmp[0] eq 'find') {
            if ($input_orders_hash{"$tmp[1]"}) {
                push (@result_arr, 'yes');
            } else {
                push (@result_arr, 'no');
            }
        }
    }
    $\="\n";
    foreach my $result_value (@result_arr) {
        print $result_value;
    }

    my $timer = tv_interval($t0)."\n";
    print "$timer ms\n";
}

上記のコードは、ハッシュを使っているけれどハッシュテーブルを再現できていないよね。スクリプト言語でも再現できるのだろうか。