Changes between Initial Version and Version 1 of GB11926/2013-06-17


Ignore:
Timestamp:
06/17/2013 01:38:24 PM (9 years ago)
Author:
chris
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • GB11926/2013-06-17

    v1 v1  
     1期末試験
     27/1 3限
     33A202
     4持ち込み不可
     5クイズの類題から出題
     6
     7データの探索
     8
     9表探索
     10・線形探索
     11順序に制約がない
     12キーの探索
     13順番に調べる O(n)
     14キーの追加 表の最後に追加 O(1)
     15キーの削除
     161. 削除して後ろのキーをシフト
     172. 削除したキーをマーク
     18データが少ない
     19追加のほうが圧倒的に多い
     20新しいキーへの探索が多い
     21
     22二分探索
     23よく出てくる
     24
     25ハッシュ表
     26サイズ9の表を用意する。
     27アルファベット順、キーの頭の文字をmod9した番地にたたきこむ
     28SuzukiならSmod9=19mod9=1、1番地に入る
     29先住者がいる→衝突 なんとかして別の領域に入れる (2番地ずらすとか)
     30
     31ごみが固まると効率が悪くなる
     32* 第1クラスタ (Primary Cluster)
     33同族でないキーがおる
     34* 第2種クラスタ
     35
     36例: Uedaは1=21mod9=3番地に要るはず
     373番地にはSatohがいる→5番地に301→5番地にはNakamuraがおる→7番地に301→Watanabeがおる→0番地に301→Abeがおる→2番地に301→Uedaがいた 探索5回。やばい。
     38
     39開番地法 (Open Addressing)
     40衝突が起こると、代わりの番地を探す。ハッシュ関数を0とすると、h,,0,,(k)がkを格納する理論上の番地を表す。そこがだめなら代わりのh,,1,,(k)を示す。これをデータの格納が完了するまで繰り返す。
     41h,,0,,(k), h,,1,,(k), ...
     42
     43探索周期
     44同じ番地が再び出てくるまでの回数
     45
     46線形走査法
     47h,,i,,(k)をこうやって求める:
     48h,,i,,(k) = [h,,0,,(k) + d * i] mod M
     49where d = ハッシュ増分(定数)、M = 表のサイズ
     50