3.6. A Hash Table
Can we do better than O(n*log(n))?

If we want to keep the states sorted  no.

If, however, we just want to determine if a given state is present
or not, then the answer is: "usually".
What is a hash?

As far as we are concerned a hash is an array of buckets. The index
of the bucket into which a given state goes is determined according to a
deterministic hash function.

A hash function is highly magical and should make sure similar records
have very distinct hash values, and all hash values are generated
in roughly equal frequency.
Written by Shlomi Fish