Hashing algorithms can be extremely fast, since the entire structure is typically stored in memory and requires a single mathematical calculation, along with perhaps a few memory accesses, to answer the search question. There are many hashing structure variations, but all consist of a hash function, hash buckets, and hash chains.

Hash functions take an input and produce an output within a defined range. The input is called a hash value. Figure 6-6 shows the basic format along with a classic hash function. The x mod 10 function can easily be used to ensure that, regardless of the positive integer hash value input, the result will always reside between 0 (zero) and 9. With a hash value input of 11, the output will be 1. This is commonly spoken as, "Eleven is hashed to one."

Figure 6-6. A hashing function maps the hash value input to a defined range. Part a shows the general hashing algorithm structure; part b shows a classic hashing algorithm. Regardless of the positive integer input, the output will always be between 0 and 9.