In many hashing situations, the number of possible hash value inputs exceeds the number of buckets. The examples I just gave are just like this, since there are only 10 buckets, yet there are 1,000 hash input values. In regard to Oracle, the number of possible hash value inputs is the number of Oracle database blocks. But at any one time, the number of hash value input values will equal the number of buffers in the buffer cache.

When two hash values hash to the same bucket, it is called a collision. Collisions are common with hashing. They can be minimized by increasing the number of buckets, but can be disastrous for high-performance applications-such as an Oracle system. As an example, suppose a modulus 10 hash function had 1,000 possible hash value inputs. This would ensure collisions. To avoid collisions, a hashing algorithm outputting a perfectly even output distribution would need 1,000 hash buckets. If the hashing algorithm were not perfect, as none are, then to reduce the likelihood of collisions, the number of output buckets could also be increased. To summarize, two ways to decrease collisions are to use a superb hashing algorithm and to have plenty of hash buckets. If the hashing algorithm is not changeable, then you may have the option to increase the number of hash buckets.

Each hash bucket has an associated hash chain. When a searched-for object is hashed to a bucket, the bucket's chain is sequentially searched looking for the object. If the object is not found in the hash chain, we know the object is not anywhere in the entire hashing structure. If the hash chain is short, the sequential search occurs extremely fast. Even better is a zero chain length if the object is not in the cache.