HashSet

一言で言うと

ハッシュ表ベースの Set 実装。

もう少し詳しく

ハッシュ表を使って要素を管理するコレクション。重複する要素を持たず、要素の順序は保証されない。追加・削除・検索がいずれも平均 O(1) で行える点が特徴。Java の java.util.HashSet が代表例で、equals と hashCode を正しく実装したオブジェクトを格納する必要がある。

追加・検索・削除は平均 O(1) だが、ハッシュ衝突が多い場合は O(n) に劣化することがある。実務では既存ライブラリを使うことが多いですが、内部の仕組みを知っておくと適切な選定とデバッグができるようになります。

実務でどう使うか

関連する章

Ch115 で詳しく学べます。