What is a Hash Table?
Coddyの「ハッシュテーブル - データ構造シリーズ #4」コースのレッスン 2/14。
ハッシュテーブルは、キーと値のペアを格納するデータ構造で、キーによってエントリを検索する辞書のようなものです。その魔法は速度にあります。適切に構築されたハッシュテーブルは、格納されているエントリの数に関係なく、平均O(1)の時間でエントリの検索、挿入、削除を行います。
その仕組みの鍵はハッシュ関数です。すべてのキーはバケットのインデックスに変換されるため、テーブル全体をスキャンすることなく、どこを探すべきか正確にわかります。2つの異なるキーが同じバケットに割り当てられた場合（衝突）、それらをそのバケットのリストにまとめて保持します。この戦略はチェイニングと呼ばれます。
ハッシュテーブルの主な5つの操作は次のとおりです：
- Put: キーと値のペアを格納するか、キーが既に存在する場合は値を更新します。
- Get: 指定されたキーに対応する値を検索します。
- ContainsKey: キーがテーブルに格納されているかどうかを確認します。
- Remove: キーと値のペアを削除します。
- Size: 現在格納されているペアの数を返します。
HashMapクラスを作成しましょう！
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。