回答編集履歴
1
キーと値の説明を追加
answer
CHANGED
|
@@ -12,6 +12,7 @@
|
|
|
12
12
|
一つの指定席に二人（以上）の人が座りたいということが起る。衝突をできるだけ回避するために出力を一様分布にしたい。
|
|
13
13
|
|
|
14
14
|
**ハッシュテーブルの実装**
|
|
15
|
+
|
|
15
16
|
衝突を考えると、配列に格納するために工夫が必要になります。
|
|
16
17
|
|
|
17
18
|
- 同じハッシュ値のエントリを隣に置く
|
|
@@ -23,9 +24,20 @@
|
|
|
23
24
|
|
|
24
25
|
|
|
25
26
|
**ハッシュ関数の実装**
|
|
27
|
+
|
|
26
28
|
上の本にはハッシュ関数の実装について書かれていません。以下の本を読んでください。
|
|
27
29
|
『世界標準MIT教科書 アルゴリズムインロダクション第３版 第１巻』近代科学社
|
|
28
30
|
衝突の起きるハッシュ関数だけでなく、衝突の起きない「完全ハッシュ法」も紹介されています。
|
|
29
31
|
|
|
30
32
|
**ハッシュ関数の応用**
|
|
33
|
+
|
|
31
|
-
パスワード、電子署名など様々な分野で使われています。wikipediaを読んでみましょう。
|
|
34
|
+
パスワード、電子署名など様々な分野で使われています。wikipediaを読んでみましょう。
|
|
35
|
+
|
|
36
|
+
### 【追記(2019-04-28)】
|
|
37
|
+
**キーと値**
|
|
38
|
+
|
|
39
|
+
ハッシュ値（配列の添字）が「キー」と思われているようですが間違いです。キーは「リンゴ」「ミカン」になります。英語の辞書に例えると、英単語が「キー」単語の説明が「値」に相当します。質問の例は「キー」と「値」が同じ辞書です。ハッシュテーブルを「辞書」「連想配列」「ハッシュ」と呼ぶことがあります。
|
|
40
|
+
|
|
41
|
+
**ハッシュテーブルのエントリ**
|
|
42
|
+
|
|
43
|
+
通常は(キー、値)のペアになります。理由は、衝突リストに格納されたエントリを識別するのにキーの同値判定が必要だから。
|