If you sort and store partial keys you can search by using binary search, cutting search time from linear to log. For larger number of keys, this becomes much faster than your single bit storage. To reduce space requirements, only store public keys that fit a criteria (like ending with the six lower bits zero) when building. When searching, subtract until you hit the bit criteria, then look up with binary search.