wiki:GB11926/2013-06-17

期末試験 7/1 3限 3A202 持ち込み不可 クイズの類題から出題

データの探索

表探索 ・線形探索 順序に制約がない キーの探索 順番に調べる O(n) キーの追加 表の最後に追加 O(1) キーの削除

  1. 削除して後ろのキーをシフト
  2. 削除したキーをマーク

データが少ない 追加のほうが圧倒的に多い 新しいキーへの探索が多い

二分探索 よく出てくる

ハッシュ表 サイズ9の表を用意する。 アルファベット順、キーの頭の文字をmod9した番地にたたきこむ SuzukiならSmod9=19mod9=1、1番地に入る 先住者がいる→衝突 なんとかして別の領域に入れる (2番地ずらすとか)

ごみが固まると効率が悪くなる

  • 第1クラスタ (Primary Cluster)

同族でないキーがおる

  • 第2種クラスタ

例: Uedaは1=21mod9=3番地に要るはず 3番地にはSatohがいる→5番地に301→5番地にはNakamuraがおる→7番地に301→Watanabeがおる→0番地に301→Abeがおる→2番地に301→Uedaがいた 探索5回。やばい。

開番地法 (Open Addressing) 衝突が起こると、代わりの番地を探す。ハッシュ関数を0とすると、h0(k)がkを格納する理論上の番地を表す。そこがだめなら代わりのh1(k)を示す。これをデータの格納が完了するまで繰り返す。 h0(k), h1(k), …

探索周期 同じ番地が再び出てくるまでの回数

線形走査法 hi(k)をこうやって求める: hi(k) = [h0(k) + d * i] mod M where d = ハッシュ増分(定数)、M = 表のサイズ

Last modified 11 years ago Last modified on 06/17/2013 01:38:24 PM