Taking Hash Tables Off The Shelf - tanakakenji/Rinko GitHub Wiki

[本棚のイラストと共に]

=> 世界中の図書館が本の分類や整理、並び替えをしていなかったらどうなるか想像してみて？

=> あるいは、ISBNナンバーのような突飛な方法で本を並べていたらどうなるか想像してみて？

[下の本棚のイラストと共に]

私たちの本のコレクションをデータセットとして考えることができます。

※もし本を全く整理しなかったら、探しているものを見つけるために全てを検索しなければならないでしょう。

※たとえISBNナンバーで整理したとしても、その一部を探さなければならないでしょう。

図書館をデータ構造として想像してみましょう-

配列やリンクドリストを使って本を探す場合：

棚の最初の本への参照からしか始められないため、全ての本を探索しなければなりません。

→これは空間時間計算量が O(n) となります（nは本の総数）。

ソート済み配列やリンクドリストを使って本を探す場合：

二分探索のテクニックを適用でき、配列/リストをサブ配列に分割していくことができます。

→これは空間時間計算量が O(log n) となります（nは本の総数）。

※これらのどちらも本を見つける最も効率的な方法とは言えません！

ハッシュテーブルとは正確には何でしょうか？

※ハッシュテーブルは基本的に2つの異なる部分で構成されています：

a) 配列：実際のテーブルとしての配列で、データが格納される場所です（そしてデータを見つけるために検索しなければならない場所です）。

b) マッピング関数（またはハッシュ関数）：入力されたデータを受け取り、配列の中の非常に特定のインデックスに割り当てることでマッピングを作成する役割を担います。

[イラストでは、ハッシュ関数が値を配列のインデックス3に割り当てる様子が示されており、0,1,2,4はnullとなっています]

この画像はハッシュテーブルの仕組みを説明しています。

このハッシュテーブルはサイズが12で、本のタイトルを格納する例が示されています：

ハッシュ関数の仕組み：

テーブルサイズは12

ハッシュアルゴリズム：文字列の文字数をテーブルサイズで割った余りを使用

例として：

14文字のタイトル: 14 ÷ 12 = 余り2 → インデックス2に格納

16文字のタイトル: 16 ÷ 12 = 余り4 → インデックス4に格納

18文字のタイトル: 18 ÷ 12 = 余り6 → インデックス6に格納

これは、文字数を使って本のタイトルをハッシュテーブルの特定の位置に効率的に格納・検索する方法を示しています。

このコードはハッシュ関数を実装したJavaScriptのコードです。説明させていただきます：

function bookHashing(bookTitle, hashTableSize) {
    // 本のタイトルから空白を削除
    var strippedBookTitle = bookTitle.replace(/\s/g, '')
    
    // タイトルの長さをハッシュテーブルのサイズで割った余りを返す
    return strippedBookTitle.length % hashTableSize;
}

この関数は：

本のタイトルを受け取り、全ての空白を削除します
空白を除いた文字列の長さを計算します
その長さをハッシュテーブルのサイズで割った余りを返します

例として：

"The Grapes of Wrath" → 4を返す
"The Sound and the Fury" → 6を返す

これは前のイラストで説明されていたハッシュ関数のコード実装バージョンです。シンプルですが、本のタイトルをハッシュテーブルの特定のインデックスにマッピングする方法を示しています。

この画像は「衝突(collision)」という概念について説明しています：

例として別の18文字の本のタイトルを使っており、ハッシュ関数の計算をすると：

18 ÷ 12 = 余り6

しかし、インデックス6にはすでに別の本のタイトルが格納されています。これが「衝突」と呼ばれる現象です。

画像では「これは衝突と呼ばれ、完全に普通の現象です！」と説明されています。

これはハッシュテーブルで起こりうる一般的な問題で、異なる入力値が同じハッシュ値（この場合は同じインデックス）を生成する場合に発生します。このような衝突への対処方法は、ハッシュテーブルの設計において重要な考慮事項となります。

この図は辞書やフォンブックでのハッシュ関数の仕組みを説明しています：

主なポイント：

Zで始まる名前を探すのは簡単です - インデックスキーを使うだけで良いのです。
アルファベット順のハッシュ機能：

例：'A'で始まる全ての名前は同じバケットに格納
フォンブックや辞書では、入力データの最初の文字を使ってインデックスキーを生成

重要な特徴：

アルファベットに基づくハッシュ関数は26個のハッシュバケットを生成します（A-Z）
理想的には、データが全てのハッシュバケットに均等に分散されることが望ましい

このように、単純なアルファベット順のハッシュ関数は理解しやすいですが、データの偏りが生じやすいという特徴があります。

この画像は検索の2つの異なる方法を比較しています：

線形探索（Linear Search）- O(n)

上の図は、タイトルを見つけるために配列の先頭から順番に探していく方法
時間計算量はO(n)で、nはデータの数
全ての要素を確認する必要がある可能性があります

ハッシュ関数を使用（Constant time）- O(1)

下の図は、ハッシュ関数を使って直接インデックス（この例では10）にアクセスする方法
時間計算量はO(1)で、一定時間
ハッシュ関数が計算したインデックスに直接アクセスできる

この比較は、ハッシュテーブルが線形探索よりも効率的に検索を行えることを示しています。