Find the closest string to a fixed set of strings
This is a nearest-neighbor problem, and there are a variety of algorithms for the problem.  The simplest is a k-d tree, and there are more sophisticated data structures as well.  Another approach is to use locality-sensitive hashing.

However, the effectiveness of these methods depends heavily on the dimension (i.e., on the length of the strings).  Practical experience is that for dimension $\le 10$, these are better than the naive linear-time search, but for very high dimension, usually they perform no better than the naive algorithm.  This occurs due to the curse of dimensionality.  In your context, that means that if the strings are short and $n$ is large, these data structures will probably be effective, but if the strings are long, I would not expect too much hope.

In the special case where strings are long and you expect the nearest neighbor to have very low Hamming distance, whereas the distance to most other strings will be very large, then there are techniques you can use.  For instance, you might look into shingling the strings into $n$-grams, storing the $n$-grams in a hashtable, and doing a lookup on each $n$-gram from the query string.  You can view this as a form of locality-sensitive hashing for the Hamming distance.  Another approach is to use bit sampling as a locality-sensitive hash; this should be easy to implement.

I also recommend taking a look at our questions in the nearest-neighbor topic, especially Why Is KD-Tree-based Nearest Neighbor Exponential in K?, Best data structure for high dimensional nearest neighbor search, Why is exact nearest neighbor search hard in high dimensional spaces?,
What is the state of the art for k nearest neighbour search?.

We also have questions here about the harder problem of finding the nearest string, where nearest is measured by Levenshtein edit distance (e.g., Find all pairs of strings in a set with Levenshtein distance &lt; d, How to speed up process of finding duplicates/similar items in a large amount of strings?, How fast can we identifiy almost-duplicates in a list of strings?, Matching strings in one set to strings in another based on Levenshtein distance).