sequences of arbitrary length may combine. The cellar An important optimization, to reduce the effect of coalescing, is to restrict the address space of the hash function to only a subset of the table. For example, if the table has size M with buckets numbered from 0 to M − 1, we can restrict the address space so that the hash function only assigns addresses to the first N locations in the table. The remaining M − N buckets, called the cellar, are used exclusively for storing items that collide during insertion. No coalescing can occur until the cellar is exhausted. The optimal choice of N relative to M depends upon the load factor (or fullness) of the table. A careful analysis shows that the value N = 0.86 × M yields near-optimum performance for most load factors. Variants Other variants for insertion are also possible that have improved search time. Deletion algorithms have been developed that preserve randomness, and thus the average search time analysis still holds after deletions. Implementation Insertion in C: /* htab is the hash table, N is the size of the address space of the hash function, and M is the size of the entire table including the cellar. Collision buckets are allocated in decreasing order, starting with bucket M-1. */ int insert ( char key[] ) { unsigned h = hash ( key, strlen ( key ) ) % N; if ( htab[h] == NULL ) { /* Make a new chain */ htab[h] = make_node ( key, NULL ); } else { struct node *it; int cursor = M-1; /* Find the first empty bucket */ while ( cursor >= 0 && htab[cursor] != NULL ) --cursor; /* The table is full, terminate unsuccessfully */ if ( cursor == -1 ) return -1; htab[cursor] = make_node ( key, NULL ); /* Find the last node in the chain and point to it */ it = htab[h]; while ( it->next != NULL ) it = it->next; it->next = htab[cursor]; } return 0; } One benefit of this strategy is that the search algorithm for separate chaining can be used without change in a coalesced hash table. Lookup in C: char *find ( char key[] ) { unsigned h = hash ( key, strlen ( key ) ) % N; if ( htab[h] != NULL ) { struct node *it; /* Search the chain at