スパースセット

2本の配列で成り立つ。要素を連続して保持する密（パック済み）配列と、キーで引ける巨大な疎配列で、後者は各要素が密配列のどこにあるかを記録する。所属判定は間接参照1回で済む。削除は、密配列の末尾の要素を空いた穴に移し、2つのインデックスを直すだけで、要素をずらす必要はない。密配列を走査すれば、生きている要素だけを順に辿れる。

ECSライブラリが、コンポーネントの型ごとにエンティティIDをキーとしたスパースセットで保存するのはこのためだ。データ指向のスタイルで、反復は線形かつキャッシュに優しくなる。代償はメモリで、疎配列の大きさは要素数ではなくキーの範囲で決まる。この手法は1993年にブリッグスとトーツォンが記述した。