# 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