演習問題　第1回　ハッシュ法(2017、2019年度)


■ 実験用データ
　整数集合:　　集合の濃度(要素数): 1,000,000、　キーの型: 整数、　　 ファイル: integer1MS.dat
　文字列集合: 集合の濃度(要素数): 100,000、　　キーの型: 文字列、　ファイル: wordE100KS.dat
　　　(文字列集合: 英単語集合)

■ 計測値出力単位
整数集合　　　U = 100,000　　(要素数の1/10)
英単語集合　 U = 10,000　　　(要素数の1/10)

■ 集合、パラメーター設定
・学籍番号の最下位桁の値によって、集合、パラメーター(除数、線形探査法のハッシュ増分(CONSL)、等)が異なります。
　　　　前半のグループ　　　　後半のグループ
　　　　集合: 整数集合　　　　集合: 文字列集合
番号　　除数　　CONSL　　　除数　　CONSL
　　0: 　999983　　19　　　　　99991　　19
　　1: 　999983　　23　　　　　99989　　23
　　2: 　999979　　29　　　　　99971　　29
　　3: 　999979　　31　　　　　99929　　31
　　4: 　999961　　37　　　　　99929　　37
　　5: 　999961　　41　　　　　99923　　41
　　6: 　999959　　43　　　　　99907　　43
　　7: 　999959　　47　　　　　99901　　47
　　8: 　999953　　53　　　　　99881　　53
　　9: 　999953　　59　　　　　99877　　59

■ 留意事項
・誤った問題番号、誤った設定値でのレポートを提出は受理されません。 但し、以下のように、分析内容を拡張することは認めます。
問題番号1a: 他の除数でも算出する。


1a ハッシュ法における衝突の問題
　ハッシュ法の主要問題である衝突の状況を調査する。ここでいう「衝突」とは、ハッシュ値が一致する現象だけを指す(探査関数で空番地を見つける過程での衝突は含まない)。　ハッシュ表の生成時に、次に挙げる項目を調べる（調査項目については、テキストp.8〜9に具体的に記述されている)。
　　(a) 衝突が生ずる番地の総数
　　(b) 衝突が起きたキーの総数
　　(c) 最大同族数、最小同族数、平均同族数
指定されたファイルを読み込み、開放番地法でハッシュ表を生成(store関数)する過程で上記指標を測定し、9Uレコード読み込んだ毎に出力(print)する。出力書式のイメージは以下のとおり。

　　　　　　衝突番地数　衝突キー総数　最大同族数、最小同族数、平均同族数
　　 1U　　・　・　　　　・　・　　　　　　　　　・　・　　　　　　　・　・　　　　・　・
　　 2U　　・　・　　　　・　・　　　　　　　　　・　・　　　　　　　・　・　　　　・　・
　　　　　　　　・　・　　　　・　・　　　　　　　　・　・　　　　　　　　・　・　　　・　・
　　　　　　　　・　・　　　　・　・　　　　　　　　・　・　　　　　　　・　・　　　　・　・
　　　9U　　・　・　　　・　・　　　　　　　　　　・　・　　　　　　　・　・　　　　・　・
　　 10U　　・　・　　　・　・　　　　　　　　　　・　・　　　　　　　・　・　　　　・　・

　上記の測定結果について、様々な観点から分析せよ。