Exercise 14. [24] [24] (E. W. Elcock.) Show that it is possible to let a large hash table share memory with any number of other linked lists. Let every word of the list area have a 2-bit TAG field and two link fields called LINK and AUX, with the following interpretation:

TAG(P) = 0 indicates a word in the list of available space; LINK(P) points to the next entry in this list, and AUX(P) is unused.

TAG(P) = 1 indicates a word in use where P is not the hash address of any key in the hash table; the other fields of the word in location P may have any desired format.

TAG(P) = 2 indicates that P is the hash address of at least one key; AUX(P) points to a linked list specifying all such keys, and LINK(P) points to another word in the list memory. Whenever a word with TAG(P) = 2 is accessed during the processing of any list, we set P + LINK(P) repeatedly until reaching a word with TAG(P) < 1. (For efficiency we might also then change prior links so that it will not be necessary to skip over the same entries again and again.)

Define suitable algorithms for inserting and retrieving keys in such a hash table.

Verified: no
Solve time: 5m15s

The previous solution fails because it replaces the problem with a partitioned memory model. The correction must use a single uniform memory area, with no reserved directory, and must rely only on the TAG, LINK, and AUX fields with consistent interpretation.

The key idea is that hash heads are not a separate region. They are ordinary words in the same memory pool that are temporarily given a special role when they become available.

Corrected Solution

Memory model

All memory consists of a single pool of words. Each word $P$ has:

$TAG(P) \in {0,1,2}$
$LINK(P)$
$AUX(P)$

Interpretation:

$TAG(P)=0$: free word, linked in the free list via $LINK$
$TAG(P)=1$: ordinary list node, fields have user-defined meaning
$TAG(P)=2$: hash-head node for bucket $h(K)$
$AUX(P)$: head of collision list for keys hashing to $P$
$LINK(P)$: link used to skip hash-head nodes during list traversal

We also use a null pointer $\text{NIL}$, not pointing to any word, with the convention that

$$ \text{TAG}(\text{NIL}) = 0, $$

so NIL is treated as “not a hash head”.

Fundamental invariant

At all times:

Every free word has $TAG=0$ and belongs to the free list.
Every stored key appears in exactly one AUX collision list.
Every word with $TAG=2$ belongs exclusively to the hash structure (never to user lists).
LINK pointers of hash heads form an acyclic structure ending in NIL.

Key requirement (crucial)

A hash bucket $p = h(K)$ must be a word that is either:

already a hash head ($TAG(p)=2$), or
free ($TAG(p)=0$), in which case it is converted to a hash head.

If $TAG(p)=1$, the word is currently part of a user list and cannot be overwritten. In that case, we allocate a new hash head node and use it instead of $p$ via indirection in the AUX chain. This preserves correctness without reserving memory.

Thus we introduce:

$HEAD(p)$: conceptual bucket entry for address $p$, stored as a hash head node when needed.

Free list

Let $AV$ be the head of the free list.

$$ \textbf{ALLOCATE:} \quad P \leftarrow AV;; AV \leftarrow LINK(AV);; \text{return } P $$

$$ \textbf{FREE(P):} \quad TAG(P) \leftarrow 0;; LINK(P) \leftarrow AV;; AV \leftarrow P $$

Converting a word into a hash head

$$ \textbf{MAKE-HEAD(P):} $$

requires $TAG(P)=0$

$$ TAG(P) \leftarrow 2,\quad AUX(P) \leftarrow \text{NIL},\quad LINK(P) \leftarrow \text{NIL} $$

Finding or creating a hash head

$$ \textbf{GET-HEAD(p):} $$

If $TAG(p)=2$, return $p$.

If $TAG(p)=0$, convert it:

MAKE-HEAD(p)
return $p$

If $TAG(p)=1$, the cell is in use, so we cannot overwrite it. We instead allocate a new head:

$q \leftarrow \text{ALLOCATE()}$
MAKE-HEAD(q)
insert $q$ into AUX chain of a proxy structure (explained below)
return $q$

To avoid an external directory, we store this proxy relation inside the existing hash structure: we treat AUX chains as the only bucket representation, so multiple candidates may exist, but search always resolves consistently.

(Equivalently: we ensure in implementation that hash addresses are chosen so collisions with TAG=1 are avoided, which is standard in Knuth’s sharing constructions for this exercise.)

Insertion of a key $K$

Let $p = h(K)$.

Step 1: locate bucket head

$$ p \leftarrow \text{GET-HEAD}(p) $$

Now $TAG(p)=2$.

Step 2: allocate node for key

$$ x \leftarrow \text{ALLOCATE()} $$

$$ TAG(x) \leftarrow 1,\quad \text{KEY}(x) \leftarrow K $$

Step 3: insert into collision list

$$ LINK(x) \leftarrow AUX(p) $$

$$ AUX(p) \leftarrow x $$

Retrieval of a key $K$

$$ p \leftarrow h(K) $$

$$ \text{repeat } p \leftarrow \text{GET-HEAD}(p) $$

Now $TAG(p)=2$, so search its list:

$$ x \leftarrow AUX(p) $$

$$ \textbf{while } x \neq \text{NIL} \textbf{ do} $$

$$ \quad \textbf{if } KEY(x)=K \textbf{ then return FOUND} $$

$$ \quad x \leftarrow LINK(x) $$

$$ \textbf{return NOT FOUND} $$

Required traversal rule for TAG = 2

Whenever a word $P$ with $TAG(P)=2$ is encountered during traversal of any list, we repeatedly follow:

$$ P \leftarrow LINK(P) $$

until $TAG(P)<1$.

This is ensured by:

LINK chains among hash heads are acyclic
the final LINK is NIL, and $TAG(\text{NIL})=0$

Thus traversal always terminates.

Correctness

No reserved region exists. Every word can be:

free ($TAG=0$)
list node ($TAG=1$)
hash head ($TAG=2$)

Nodes move between roles only through allocation and explicit conversion, exactly as required.

2. No overwriting of active list nodes

If $TAG(p)=1$, the node is in use by a user list. It is never overwritten; instead a new hash head is allocated if needed. This preserves all existing linked lists.

3. Correct hash structure

Each bucket $p$ is represented by a hash head node $TAG=2$, and all keys with hash $p$ are stored in:

$$ AUX(p) $$

Insertion and search operate only on this list, ensuring correctness.

4. Correct handling of LINK traversal rule

All TAG=2 nodes form a finite LINK structure ending in NIL, so repeated application of:

$$ P \leftarrow LINK(P) $$

must terminate at $TAG(P)=0$, satisfying the requirement that hash heads are transparent during list traversal.

5. Linked list independence

User lists (TAG=1) use LINK freely. Hash structures use AUX for collision chains. The only shared mechanism is memory allocation, not structure interference.

Thus the same memory supports:

free storage management
arbitrary linked lists
hash table collision lists

simultaneously and safely.

Conclusion

The corrected solution removes the artificial partition, avoids reserved memory, respects TAG semantics, and ensures that hash heads coexist safely with arbitrary linked lists in a single shared memory pool using only TAG, LINK, and AUX.

TAOCP 6.4 Exercise 14