JL Computer Consultancy

What are Hash Chains.

(Recreated from an original written for the Dizwell Wiki).

June 2006

As a starting point for this page, here’s a short list of questions that I recently received about “cache buffers chains”, and the (quick) answers that I gave.

No, for the cache buffers chains it is a doubly linked list

The terms are two names for the same things - also called hash buckets.

A linked list is a collection of memory chunks where each chunk contains a pointer to the next chunk. If there are two pointers in each chunk (one “forwards” one “backwards”) you have a doubly linked list.

If you arrange items into a doubly-linked list, you can remove an item from the list very easily. You follow the two pointers from the current item to the two adjacent items, and change their “backward” pointers so that they point to each other rather than pointing to the item you are removing.

Draw a picture of about 5 rectangles connected in a chain by pairs of arrows and re-read the above.

Buffers headers are placed on these lists. There are many separate lists of this specific type No buffer header goes on to more than one such list Each list has a known starting point.  Many starting points (typicall 64 – 128) are covered by each cache buffers chains latch

But there are other types of linked list that also run through the collection of buffer headers, such as the LRU (least recently used) chains and the checkpoint chains.

Correct. To check if a block is in memory, the process computes a hash value based (I think) on the block address, type and tablespace - and this tells it which hash chain to traverse

Back to Index of Topics