Put simply, CBCs are used to answer the question, "Is the buffer in the buffer cache, and if so, where does it reside?" This is essentially a search-type question. Many types of searching algorithms can be used to get the answer: binary tree, B+ tree, B* tree, sequential search, hashing algorithm, or some combination. Oracle chose to use a hashing algorithm, followed by a quick (we hope) sequential search.

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."