6個のキー値 Sato, Nakata, Suzuki, Hirano, Egawa, Arai をサイズ9のハッシュ表H[0], H[1],
･･･, H[8] にこの順番で格納する。ハッシュ値は次のとおりとする。
┌─────┬───┬───┬───┬───┬───┬───┐
│ キー値│ Sato │Nakata│Suzuki│Hirano│Egawa │ Arai │
├─────┼───┼───┼───┼───┼───┼───┤
│ハッシュ値│ 1 │ 5 │ 1 │ 8 │ 5 │ 1 │
└─────┴───┴───┴───┴───┴───┴───┘
衝突処理はハッシュ増分2の線形探査法を用いるとする。結果としてH[0] とH[3] にそれぞれ格納されるキー値として適当なものはどれか。
H[0] H[3]
① 空 空
② 空 Egawa
③ Arai Suzuki
④ Hirano Sato
⑤ Nakata Arai
③
「衝突処理はハッシュ増分2の線形探査法を用いるとする。」ということは、同じハッシュ値になった場合は、空きを見つけるまで2を足すということである。また、サイズ (問題の場合は9) まで到達すると、初めに戻って探索する。
Sato = 1
Nakata = 5
Suzuki = 1 → 3
Hirano = 8
Egawa = 5 → 7
Arai = 1 → 3 → 5 → 7 → 0
| Ⅳ－２６ | 目次 | Ⅳ－２８ |