1.2 Hash tables and collision strategies

Once ADTs, pointers, and basic node structures are in place, the next question is how to support dictionary-style operations efficiently. A hash table is one of the standard answers: instead of preserving sorted order, it applies a hash function to jump directly to a bucket.

That jump is powerful, but it is never perfect. The whole chapter exists to explain what the jump can guarantee, where collisions come from, and how the implementation recovers when multiple keys land in the same location.

The ADT viewpoint comes first

The hashtable tutorial starts from operations, not from buckets:

• insert a value under a key,
• look up the value for a key,
• delete an existing key-value entry.

So the logical object is a dictionary or symbol table. The hash table is only one implementation strategy for that ADT.

This definition already implies two different design questions:

• how keys are converted into bucket indices,
• what the implementation does when two keys map to the same index.

What a hash function is supposed to do

The local tutorial material emphasizes four properties of a good hash function:

• it must always return a legal bucket index,
• it should reduce collisions,
• it should distribute keys reasonably evenly,
• it should be quick to compute.

The last point matters because a beautifully distributed hash rule is not very useful if every lookup spends too long computing the bucket index itself.

int Hash(char *s, int nBuckets) {
   int h = 0;
   while (*s != '\0') {
      h += *s;
      s++;
   }
   return h % nBuckets;
}

Collision is unavoidable, not exceptional

The most important conceptual shift is that collisions are not a rare bug. They are a normal consequence of sending a large key space into a fixed set of buckets.

If the bucket count is fixed and the key space is large, collisions are inevitable. So the real implementation question is not “how do we avoid every collision?” but “how do we recover from collisions without breaking dictionary correctness?”

Chaining keeps colliding keys in one bucket list

The lecture material treats chaining as the most direct recovery method.

This design fits the pointer-and-node model from the previous section very naturally.

typedef struct cellT {
   char *key;
   void *value;
   struct cellT *next;
} cellT;

Each bucket head points to the first node in its chain. Lookup therefore has two layers:

1. hash the key to choose a bucket,
2. scan only that bucket’s chain instead of the whole table.

Open addressing uses probing instead of linked chains

The tutorial also introduces open addressing. Instead of storing a linked list in each bucket, the table keeps probing other slots when the preferred one is occupied.

Typical probing styles include:

• linear probing,
• quadratic probing,
• double hashing.

The key difference from chaining is where the extra work lives:

• chaining keeps multiple entries in a bucket-side list,
• open addressing keeps searching for another empty slot in the main table.

This means deletion, clustering, and probe-sequence design become central implementation issues.

That is why the collision policy belongs in the conceptual explanation, not as an implementation afterthought.

Why load factor matters

Even a good hash function degrades if the table is too full.

The load factor is usually written as

As $\alpha$ grows:

• chains become longer under chaining,
• probe sequences become longer under open addressing,
• average-case lookup moves away from the ideal constant-time picture.

So resizing is not just a practical optimization. It is part of protecting the performance model promised by the data structure.

Generic pointers make the ADT reusable

The local hashtable lecture also uses $void *$ values. This is a deliberate ADT decision.

typedef struct hashtableCDT *hashtableADT;

hashtableADT EmptyHashtable();
void Enter(hashtableADT table, char *key, void *value);
void *Lookup(hashtableADT table, char *key);

The table does not need to know the concrete value type. It only stores the association between a key and an opaque pointer to some client-owned data.

That makes the same hashtable ADT usable for many different applications, as long as the client also knows how to interpret the returned pointer correctly.

Common mistakes

Quick checks

Exercises

Reading the implementation more closely

The lecture slides do not present hash tables as a pile of buckets first. They present them as an ADT first and as a storage strategy second. That order matters.

That overwrite behavior is easy to miss, but it is one of the reasons the ADT is a dictionary rather than a multiset.

Why key comparison still matters after hashing

Hashing narrows the search to a bucket, but it does not finish the job. The course examples repeatedly return to this point because it is the first place students often over-generalize.

If two keys hash to the same bucket, the table still has to compare the stored key with the query key. Otherwise it would not know whether the match is exact or only accidental.

Chaining is flexible because it stores collision structure separately

The simplest collision strategy in the source material is chaining. It is easy to reason about because each bucket has its own list of entries.

This gives the implementation a useful freedom: it can add new entries at the front of the list, the back of the list, or in another consistent order. The dictionary contract does not care about that local ordering as long as lookup and overwrite behave correctly.

Open addressing keeps the search inside the table

The tutorial and lecture also show open addressing. Instead of attaching a list to each bucket, open addressing keeps searching for another slot inside the table itself.

The cost of a collision therefore moves into the probing rule.

• linear probing checks the next slot, then the next, and so on;
• quadratic probing jumps by square offsets;
• double hashing uses a second hash function to generate a step size.

The lecture warns that linear probing tends to create long runs of filled buckets. That effect is called primary clustering, and it degrades the performance of the table because future probes are more likely to collide with the same dense region.

Quadratic probing is one response to that problem.

That tradeoff is classic CSCI2520 material: more structure in the rule can buy better distribution, but it also makes the implementation more complicated.

Rehashing is the cost of changing the table shape

When the bucket count changes, the hash function must change too. Every stored entry has to be reinserted under the new rule. That process is called rehashing.

The lecture notes point out that rehashing is rarely necessary for most applications, but it is conceptually important because it explains why a hash table cannot be treated as a fixed pile of memory locations forever.

How to choose between chaining and probing

The source material does not frame one strategy as universally best. It instead makes the tradeoffs visible.

• Chaining is easier to explain and naturally handles collisions with a linked list.
• Linear probing keeps the table compact but can form primary clustering.
• Quadratic probing reduces that clustering but needs stricter load-factor control.
• Double hashing usually distributes probes better, but it is more expensive because it depends on two hash functions.

If you are reading code, the safest question is not “Which strategy is faster in abstract?” The safer question is “Which strategy matches the table size, the expected load, and the update pattern of this program?”

A compact code-reading checklist

When you look at a hashtable implementation in C, check these things in order:

1. What counts as the key, and what counts as the stored value?
2. What does Enter do if the key already exists?
3. Does lookup compare the stored key after hashing?
4. Where do collision results live: in a chain, in a probe sequence, or in both?
5. What happens when the table gets too full?

If those five answers are clear, the rest of the implementation becomes much less mysterious.

More exercises