ハッシュテーブルは、キーをハッシュ関数で計算した番号のバケットに格納するデータ構造です。例えばkey % 5のような計算でバケット番号を求めます。異なるキーが同じバケット番号になることを衝突と呼び、衝突したキーは連結リストでつないで同じバケットに格納します。