今日の着席位置

アルゴリズムとデータ構造 補足資料

14-1

「ハッシュ法」

横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

今日の着席位置

• 自分の氏名を「ローマ字」で書いてください。（大学名簿に登録したもの）

• 次の値に変換し、総和を計算してください。

A→ 65 B→ 66 C→ 67 D→ 68 E→69 F→ 70 G→ 71 H→ 72 I→ 73 J→74 K→ 75 L→ 76 M→ 77 N→ 78 O→79 P→ 80 Q→ 81 R→ 82 S→ 83 T→84 U→ 85 V→ 86 W→ 87 X→ 88 Y→89 Z→ 90

スペース→ 32

※ First NameとFamily Nameの間には一つスペース(32)を入れて

• その値をこの部屋の席数Bで割った余りの番号（1～B）の席に着席してください

–余りがゼロの場合はB番

–もし、すでに席が埋まっていたら、1を足した番号の席に着席してください

• それでもまだ席が埋まっていたら、空き席にあたるまで、1を足してください

• 氏名から、どこに座っているか当てます！

–できれば１発で

静的データと動的データ

•

– データの総量（件数）が変化しない

• 追加や削除がない

– 静的データを扱うデータ構造：配列

•

– データの総量や内容が変化する

• 追加や削除が発生する

– 動的データを扱うデータ構造：線形リスト、木構造

時間計算量と空間計算量

– 時間計算量： 計算の回数や時間 – 空間計算量： 計算に必要な記憶量

– ソートの問題は、主に時間計算量を見ていた。

– 今日のテーマ：動的データを格納する際

• 探索に必要な時間計算量を一定に

– データが増えても検索が超早い

• 記憶量は犠牲に

– メモリにはゆとりが必要

探索アルゴリズム（復習）

• 与えられたキーを持つデータを見つけ出す

– データの件数 n に対し、どのような時間計算量か？

• 静的データに対するデータ探索（第 4 回）

– 線形探索： 先頭から順番に探索→ O(n) – 2 分探索： 現在地より前か後か→ O(log n)

• ただし、あらかじめソートされている必要あり

• 配列のソート

– 単純ソート（第7回）： 単純選択ソートなど → O( n² ) – 高速ソート（第8回）： クイックソートなど → O( n log n )

探索アルゴリズム

•

– データの件数 n に対し、どのような時間計算量か？

•

– 線形リストの探索（第 11 回）

• 順次探索： 先頭から順番に探索 → O(n)

– 探索木（ 2 分木）の探索（第 13 回）

• 現在ノードより右か左か→ O(log n)

– ハッシュ法による探索（第 14 回：今回）

• ハッシュ関数で「散らして」配置 → O(1)

O(n x log n)

1,000 1,000,000

O(n)

10,000 20,000,000

1,000,000,000

30,000,000,000

O(2

)

O(n

)

10 20

O(log n)

1 1

O( 1 )

10^300,000 10300,000,000

1,000 1,000,000 1,000,000,000

データ件数

例題

• 70 人が、 128 個ある席の一つをそれぞれ指 定されて、着席します。

• 氏名を聞くだけで、席番号がわかるようにし たい。

利用者数（ 70 ）＜座席数（ 128 ）＜＜氏名数（ ???? 超沢 山）

氏名を聞けば、座っている場所がわかるようにす る

例題

• 氏名を聞けば、座っている場所がわかるように する

席番号＝ H （氏名）

• H は、氏名を定義域、席番号を値域とする関数

• H が「上手に散らす」性質の関数なら、、、

• 「探索」の必要がなくなる

（すべての席を「探索」しなくても、その人が座っている場 所がわかる）

今日の着席位置

• 自分の氏名を「ローマ字」で書いてください。（大学名簿に登録したもの） key[i]

• 次の値に変換し、総和を計算してください。 SUM(key[i])

A→ 65 B→ 66 C→ 67 D→ 68 E→69 F→ 70 G→ 71 H→ 72 I→ 73 J→74 K→ 75 L→ 76 M→ 77 N→ 78 O→79 P→ 80 Q→ 81 R→ 82 S→ 83 T→84 U→ 85 V→ 86 W→ 87 X→ 88 Y→89 Z→ 90

スペース→ 32

※ First NameとFamily Nameの間には一つスペース(32)を入れて

• その値をこの部屋の席数Bで割った余りの番号（1～B）の席に着席してください

–余りがゼロの場合はB番 SUM(key[i]) % B –もし、すでに席が埋まっていたら、1を足した番号の席に着席してください

• それでもまだ席が埋まっていたら、空き席にあたるまで、1を足してください 衝突→再ハッシュ

• 氏名から、どこに座っているか当てます！

–できれば１発で

–遅刻、早退にも対応可能です　　　　　　　 追加・削除→動的データ

ハッシュ法

• n 件のデータの中から、キーを指定して、同じ値 が登録されている該当データを探し出す

– スペースに十分なゆとりがある

– ハッシュ表に「散らして」上手に格納する

– 探索コスト

• 最良時： O(1) → データの件数 n によらず一定

• 最悪時： O(n)

• 平均： O(1+n/B)

– B は「バケット数」：格納する配列の要素数

– n<<BならO(1) → あらかじめ用意できる配列に十分なゆとり

ハッシュ関数、ハッシュ値

ハッシュ関数：

キー⇒インデックス（索引番号）の変換関数 H(key)

– H(key) ：ハッシュ値； インデックス、索引番号

– ハッシュ関数は一様に「ばらまく」関数がよい H(key) = ORD(key) % B

– 同じハッシュ値をもつキー：衝突（ collision ）

• 衝突時は手順に従って別の関数を適用：再ハッシュ

ハッシュ表に対する基本操作

•

– 探索

• キーを与えると、ハッシュ表の該当位置を返す

– 挿入

• キーを持つデータをハッシュ表に格納する

– 削除

• キーを持つデータをハッシュ表から削除する

衝突処理の違いによる 2 種類のハッシング

• 外部ハッシュ法

– チェイン法、ダイレクトチェイニング法 – バケット個の線形リストを生成

• ハッシュ表には同じハッシュ値をもつ線形リスト（の先頭アドレス）を格納

• 衝突時はリストに追加

• 格納できる要素数に制限がない

– 格納されたデータがハッシュ表の外にある：外部ハッシュ

• 内部ハッシュ法

– オープンアドレス法、オープンアドレッシング法 – バケット個の要素を持つ配列を作成

• ハッシュ値を添え字（アドレス）とする

• 衝突時は再ハッシュ

• バケット数までの要素しか格納できない

– 格納されたデータがハッシュ表の内にある：内部ハッシュ