Quizmaster

Learning objectives

What you will be able to explain

For which type of query is a Hash Index generally superior to a B+ Tree?
What are the primary components of a hash index? (Select all that apply)
What is the ideal behavior of a hash function $h(K)$ ?
State whether each statement is True or False:
Given a hash function $h(K) = K \mod 7$ , calculate the bucket index for the search key $K = 50$ .
What is a major disadvantage of static hashing where the number of buckets is fixed?

Section 01

For which type of query is a Hash Index generally superior to a B+ Tree? to What is the ideal behavior of a hash function $h(K)$ ?

For which type of query is a Hash Index generally superior to a B+ Tree?

Hash indexes are optimized for equality predicates because the hash function maps a key directly to its target bucket. For point lookups this is usually faster than tree traversal, while range and prefix predicates are not hash-friendly.

What are the primary components of a hash index? (Select all that apply)

A hash index needs a search key, a hash function that maps keys to locations, and buckets/slots that store entries. Interior tree nodes are a B+ Tree concept, not a basic hash-index component.

What is the ideal behavior of a hash function $h(K)$ ?

Good hash functions distribute keys as uniformly as possible across buckets to minimize collisions and long probe/overflow chains. Preserving key order is not the goal of hashing.

Section 02

State whether each statement is True or False: to What is a major disadvantage of static hashing where the number of buckets is fixed?

State whether each statement is True or False:

1) False: hashing destroys order, so ranges are inefficient. 2) True: expected lookup is O(1) with good distribution and moderate load. 3) False: hash tables usually win on pure equality lookups. 4) True: no physical key ordering is required.

Given a hash function $h(K) = K \mod 7$ , calculate the bucket index for the search key $K = 50$ .

Using modulo hashing, bucket = K mod 7. For K=50, 50 mod 7 = 1, so the key maps to bucket index 1.

What is a major disadvantage of static hashing where the number of buckets is fixed?

With static hashing, bucket count is fixed. As data grows, collisions increase and overflow chains lengthen, so lookup and update performance degrades unless the table is rebuilt.

Section 03

In secondary storage hashing, what typically corresponds to a "bucket"? to A hash table has 7 slots (0-6) and uses $h(K) = K \mod 7$ . If we insert keys in this order: 10, 20, 30, where will 30 be stored using Linear Probing?

In secondary storage hashing, what typically corresponds to a "bucket"?

In disk-based hashing, a bucket typically corresponds to one page/block (possibly plus overflow pages). Mapping buckets to blocks aligns with the DBMS I/O unit.

Match the collision handling technique to its description:

Chaining handles collisions by linking overflow storage outside the primary slot. Open addressing resolves collisions inside the table itself by probing alternative slots.

A hash table has 7 slots (0-6) and uses $h(K) = K \mod 7$ . If we insert keys in this order: 10, 20, 30, where will 30 be stored using Linear Probing?

Compute each home slot with mod 7: 10->3, 20->6, 30->2. Slot 2 is empty, so linear probing does not continue and 30 is inserted at slot 2.

Section 04

Using the same table ( $h(K) = K \mod 7$ and size 7), we insert: 7, 14, 21. Where is 21 stored? to In Quadratic Probing, if the first hash $h(K)$ results in a collision, the next slot checked is determined by:

Using the same table ( $h(K) = K \mod 7$ and size 7), we insert: 7, 14, 21. Where is 21 stored?

All three keys hash to 0. With linear probing, 7 takes slot 0, 14 moves to slot 1, and 21 advances to the next free slot, which is slot 2.

"Primary Clustering" is a phenomenon primarily associated with which collision handling method?

Primary clustering is characteristic of linear probing because contiguous runs of occupied slots form and grow, increasing probe lengths for later inserts and searches.

In Quadratic Probing, if the first hash $h(K)$ results in a collision, the next slot checked is determined by:

Quadratic probing uses offsets i^2 from the original hash position, so the probe formula is (h(K) + i^2) mod table_size. This spreads probes more than linear probing.

Section 05

Given: - $h_1(K) = K \mod 7$ - $h_2(K) = 5 - (K \mod 5)$ - Table Size = 7 If $K = 8$ , and a collision occurs at the first position, what is the step size for double hashing? to What is the "Load Factor" ( $\alpha$ ) of a hash table?

Given: - $h_1(K) = K \mod 7$ - $h_2(K) = 5 - (K \mod 5)$ - Table Size = 7 If $K = 8$ , and a collision occurs at the first position, what is the step size for double hashing?

In double hashing, the jump length comes from the second hash function. Here h2(8)=5-(8 mod 5)=5-3=2, so the step size is 2.

Why is simply "nulling out" a slot during deletion problematic in Open Addressing?

In open addressing, removing an item by setting the slot to empty can terminate later probe sequences too early. Tombstones preserve the search chain while still marking deletions.

What is the "Load Factor" ( $\alpha$ ) of a hash table?

Load factor alpha measures occupancy pressure: alpha = n/m, where n is stored records and m is total slots. It is a key predictor of collision and probe cost.

Section 06

What is the main goal of Dynamic Hashing (like Extensible or Linear Hashing)? to If an Extensible Hash table has a Global Depth of 4, how many entries are in its directory?

What is the main goal of Dynamic Hashing (like Extensible or Linear Hashing)?

Dynamic hashing aims to adapt capacity incrementally as data changes, instead of expensive full rebuilds. Extensible and linear hashing are both designed for this online growth behavior.

In Extensible Hashing, what does the Global Depth ( $d$ ) represent?

Global depth d is the number of hash bits used to index the directory, so directory size is 2^d. It describes directory addressing granularity, not bucket occupancy.

If an Extensible Hash table has a Global Depth of 4, how many entries are in its directory?

Extensible hashing directories have 2^d entries. With d=4, the directory contains 16 entries.

Section 07

In Extensible Hashing, when a bucket $i$ with Local Depth $d_i$ overflows and $d_i < d$ (Global Depth), what happens? to State True or False:

In Extensible Hashing, when a bucket $i$ with Local Depth $d_i$ overflows and $d_i < d$ (Global Depth), what happens?

If local depth is still below global depth, the overflowing bucket can be split and directory pointers remapped without doubling the directory. Only when local depth reaches global depth is doubling required.

In Extensible Hashing, when does the directory size double?

Directory doubling occurs exactly when an overflowing bucket needs one more hash bit but already has local depth equal to the current global depth. Then the global bit-width must increase.

State True or False:

1) True: several directory entries may alias one physical bucket. 2) True: directory pages are usually smaller than full data storage. 3) True in the standard approach: splits are used instead of maintaining long overflow chains. 4) False: doubling the directory does not force splitting every bucket.

Section 08

Match the scenario to the action: to In Linear Hashing, if we have $N=4$ buckets and the split pointer $s$ is at 0. After bucket 0 is split, where does the split pointer $s$ move?

Match the scenario to the action:

If d_i < d, only the bucket needs splitting and pointer remapping. If d_i = d at overflow, the directory must first double so one more address bit is available.

What distinguishes Linear Hashing from Extensible Hashing?

Extensible hashing grows reactively at the overflowing bucket via directory semantics, while linear hashing advances splits in a deterministic round-robin order using a split pointer. That scheduling difference is the key distinction.

In Linear Hashing, if we have $N=4$ buckets and the split pointer $s$ is at 0. After bucket 0 is split, where does the split pointer $s$ move?

In linear hashing, each split advances the split pointer to the next bucket. Starting at s=0, one split moves it to s=1.

Section 09

Linear Hashing uses a family of hash functions $h_i(K), h_{i+1}(K)$ , etc. If the current level is $i$ and the bucket count is $M$ , what is the typical formula for $h_i(K)$ ? to Can a hash index be created on a non-unique secondary key?

Linear Hashing uses a family of hash functions $h_i(K), h_{i+1}(K)$ , etc. If the current level is $i$ and the bucket count is $M$ , what is the typical formula for $h_i(K)$ ?

Linear hashing uses a family of modulo functions that double the address range by level. A common form is h_i(K)=K mod (M x 2^i), with occasional use of h_{i+1} during transition.

What are the advantages of Linear Hashing? (Select all that apply)

Linear hashing avoids large directory structures, supports simple load-factor-based growth policies, and tolerates temporary overflow chains during transition. It still does not make range queries efficient.

Can a hash index be created on a non-unique secondary key?

Yes. For non-unique secondary keys, each hash bucket entry can reference a list/bucket of matching RIDs, so duplicates are handled through indirection.

Section 10

If the hash value of a key in binary is `...10110` and the Global Depth $d$ is 3, which directory entry (expressed as a decimal) will this key map to? (Assume we use the last $d$ bits). to In Extensible Hashing, if the directory is at Global Depth $d=10$ , how many entries does it have?

If the hash value of a key in binary is `...10110` and the Global Depth $d$ is 3, which directory entry (expressed as a decimal) will this key map to? (Assume we use the last $d$ bits).

With global depth 3, use the last three hash bits. ...10110 ends in 110, which is decimal 6, so it maps to directory entry 6.

Which structure is more robust against skewed data distributions?

B+ Trees remain balanced and order-aware even under skewed key distributions. Hash structures are more sensitive to skew because popular keys create hotspot buckets, collisions, and overflow/probe inflation.

In Extensible Hashing, if the directory is at Global Depth $d=10$ , how many entries does it have?

Extensible hashing directory size is 2^d. For d=10, that is 1,024 entries.

Knowledge check

Turn understanding into recall.

The quiz now follows the same concepts in scored form. You can return to this lesson from the quiz whenever a gap appears.

Start the quiz →Back to course

What you will be able to explain

For which type of query is a Hash Index generally superior to a B+ Tree? to What is the ideal behavior of a hash function h(K)h(K)h(K)?

For which type of query is a Hash Index generally superior to a B+ Tree?

What are the primary components of a hash index? (Select all that apply)

What is the ideal behavior of a hash function h(K)h(K)h(K)?

State whether each statement is True or False: to What is a major disadvantage of static hashing where the number of buckets is fixed?

State whether each statement is True or False:

Given a hash function h(K)=Kmod 7h(K) = K \mod 7h(K)=Kmod7, calculate the bucket index for the search key K=50K = 50K=50.

What is a major disadvantage of static hashing where the number of buckets is fixed?

In secondary storage hashing, what typically corresponds to a "bucket"? to A hash table has 7 slots (0-6) and uses h(K)=Kmod 7h(K) = K \mod 7h(K)=Kmod7. If we insert keys in this order: **10, 20, 30**, where will **30** be stored using **Linear Probing**?

In secondary storage hashing, what typically corresponds to a "bucket"?

Match the collision handling technique to its description:

A hash table has 7 slots (0-6) and uses h(K)=Kmod 7h(K) = K \mod 7h(K)=Kmod7. If we insert keys in this order: **10, 20, 30**, where will **30** be stored using **Linear Probing**?

Using the same table (h(K)=Kmod 7h(K) = K \mod 7h(K)=Kmod7 and size 7), we insert: **7, 14, 21**. Where is **21** stored? to In Quadratic Probing, if the first hash h(K)h(K)h(K) results in a collision, the next slot checked is determined by:

Using the same table (h(K)=Kmod 7h(K) = K \mod 7h(K)=Kmod7 and size 7), we insert: **7, 14, 21**. Where is **21** stored?