ハッシュハッシュ法 アルゴリズム論 第5回講義 2011年10月28日(金） ハッシュ法 ハッシング（ｈａｓｈｉｎｇ）ともいう ｈａｓｈ： 切りきざむ 挿入・探索・削除がＯ（１）でできる つまり、データの個数ｎに依存しない 理想の探索技法！？ 学生番号から氏名などを求めたい 2003年度に入学した学生だけを考えると、 70310001～70310101 でも、一般にキーはこのように順序よく 並んでいない ｄｉｒｅｃｔ ａｃｃｅｓｓ という 配列の0番目から100番目に氏名を格納 → （学生番号下3桁－1）番目の 配列要素を見ればよい 英和辞書 • 5万語の英和辞書の全体をメモリにのせて使 いたい • 各単語のインデクス番号が分かれば，O(1)で ある単語の意味を知ることができる インデクス番号 内容 1 2 3 …. hash:切り刻む 50,000 どうすれば 各単語の インデクス番号が 分かる
