找到成員資格的有效方法

Question

我正在使用2^n向量例如N = 3的可能值是：

000，001，010，011，100，101，110，111

我想找個什麼是最有效的方式，給出了一套組合說

000，000，001，100，000，110，000，110

如何找到一個給定的值在可能的集合。

一種方法是通過整個列表（蠻力）。另一種方法是使用任何傳統的搜索方法，例如對於log_2二進制搜索等（N）+1

另一種方法是使用布隆過濾器，雖然這是一個概率方法

我想知道是否有別的在那裏，這給位名單字符串，以有效地測試其成員資格。

Answer 1

任何數據結構都可以使用。無論你的本地字典結構是什麼，我都會接觸它，因爲這很容易做，並且是經過充分測試的代碼。通常這是一個散列，雖然它經常被稱爲別的像字典，HashMap或std :: unordered_map。有時它是一棵二叉樹。哈希（Perl），字典（Python），HashMap。

如果我想爲這個問題推出一個「完美的數據結構」，我可能會想要在trie上使用一些變體。但是，最大的勝利是一個相當小的因素加速，所以除非我知道它是必要的，爲什麼還要打擾呢？

Answer 2

某種基於散列的集合（例如，Java中的HashSet）將以攤銷後的恆定時間進行插入和查找，這是最好的漸進式方式。

如果你真的想把小船推出去，並且這個集合將是密集的（即，可能的比特串有相當比例的預期存在），那麼將它們轉換爲整數並使用一個位域。這也是恆定的時間，但更快的常數。