タイトルのとおりです。以下の論文を読みました。
Storing a Sparse Table with O(1) Worst Case Access Time
[1,m]の自然数の集合に対するサイズnの部分集合があった場合にqが部分集合に含まれるどうかを知りたい、という問題を考えます。この操作をmembership(q)と書きます。
単純に部分集合に含まれる数をソートして並べた場合、データサイズは数を入れる箱（セル）がn個あればよいです。しかしmembership(q)をやるには二分探索が必要なので時間計算量がO(log n)かかります。
これに対して提案手法はデータサイズが高々セル6n個になるかわりにO(1)でmembership(q)ができます。要素数nの部分集合に対して普通の（完全ではない）ハッシュ関数を用意して、衝突した数の集合に対して完全ハッシュを用意する。という仕組みです。
せっかくなのでPythonでどのくらいのサイズになるのか試してみました。
論文の後ろの方で完全ハッシュを指すアドレスを幾つかのベースアドレスとそこからの相対アドレスにわけるという、よくある感じのやつをやってデータサイズを実質セルn + o(n)個にしているのですが、そのへんはCでやらないとめんどいので今回はスルーです。
以下、m=10009からn=300の部分集合をランダムに作って必要なセル数を確認する、を10回繰り返すサンプルです。-hでヘルプが見られます。セル数は3n前後になっているようです。
$$ python sample.py Success. block size: 940 Success. block size: 921 Success. block size: 978 Success. block size: 963 Success. block size: 887 Success. block size: 1021 Success. block size: 970 Success. block size: 940 Success. block size: 943 Success. block size: 953
