The previous two chapters explored indexing and the B+ tree, both of which locate a specific record by comparing the search key against other values and progressively narrowing down the search, one level at a time. Hashing takes a fundamentally different approach. Instead of comparing keys against each other at all, hashing runs the search key through a mathematical function that directly computes exactly where the record should be stored, ideally allowing a record to be located in a single step, without any comparisons or tree traversal whatsoever.
This difference in strategy gives hashing a distinct advantage for one very specific and very common type of query: looking up a record by an exact match on its key, such as finding the customer with a specific customer ID. Where a B+ tree excels at range queries, retrieving every record between two values, hashing excels at direct, exact-match lookups, often completing them faster than even the most efficient tree-based index could manage.
In this tutorial, you will learn how a hash function maps search keys to storage locations called buckets, the difference between static hashing and dynamic hashing, how collisions are handled when two different keys happen to map to the same location, and a complete worked example demonstrating extendible hashing, the most widely used form of dynamic hashing, growing to accommodate new data.
Hashing is a technique for organizing data that uses a hash function to transform a search key directly into an address, called a bucket address, indicating exactly where the corresponding record should be stored or found. A bucket is simply a storage unit, often corresponding to one disk block, capable of holding one or more records.
Hash Function: h(key) = key mod 5 Inserting EmployeeID 23: h(23) = 23 mod 5 = 3 → stored in Bucket 3 Inserting EmployeeID 17: h(17) = 17 mod 5 = 2 → stored in Bucket 2 Inserting EmployeeID 31: h(31) = 31 mod 5 = 1 → stored in Bucket 1
To later retrieve EmployeeID 23, the database simply recomputes h(23) = 3 and looks directly in Bucket 3, without needing to compare 23 against any other keys stored elsewhere, unlike the block-by-block or level-by-level search required by the indexing techniques covered in the previous two chapters.
In static hashing, the total number of buckets is fixed and determined in advance, and this number never changes for as long as the file exists. The hash function is designed specifically around this fixed bucket count, and every key's bucket address is computed using that same fixed count throughout the file's entire lifetime.
Static Hash File with 4 fixed buckets: h(key) = key mod 4 Insert 12 → h(12) = 0 → Bucket 0 Insert 9 → h(9) = 1 → Bucket 1 Insert 14 → h(14) = 2 → Bucket 2 Insert 19 → h(19) = 3 → Bucket 3 Insert 16 → h(16) = 0 → Bucket 0 (shares a bucket with 12)
Static hashing works well as long as the actual number of records stays reasonably close to what the fixed bucket count was originally designed to handle. The problem arises when the file grows significantly larger than expected: with a fixed number of buckets, each bucket must hold more and more records over time, leading to overflow and steadily degrading performance, since what was meant to be a single-step lookup increasingly requires searching through overflow chains as well. Shrinking far below the expected size wastes space just as badly, leaving many buckets sitting mostly empty.
Dynamic hashing solves the rigidity problem of static hashing by allowing the number of buckets to grow and shrink automatically as records are inserted and deleted, without ever needing to rebuild the entire file from scratch. The most widely taught and widely implemented form of dynamic hashing is called extendible hashing, which cleverly uses only a portion of each key's hash value at any given time, growing to use more of it only when necessary.
| Term | Meaning |
|---|---|
| Hash Value | The full binary result produced by applying the hash function to a key, typically much longer than what is actually needed at any given moment. |
| Global Depth | The number of leading bits of the hash value currently being used across the entire directory to distinguish between buckets. |
| Local Depth | The number of leading bits actually being used by one specific bucket; a bucket's local depth is always less than or equal to the global depth. |
| Directory | An array of pointers, indexed by the global depth's worth of bits, where multiple directory entries can point to the very same bucket. |
Suppose the hash function produces binary values, and each bucket can hold at most 2 records. Begin with a global depth of 1, meaning the directory has 2 entries, both pointing initially to the same single bucket.
Initial State: Global Depth: 1 Directory: [0] → Bucket A, [1] → Bucket A Bucket A (local depth 1): empty
0101 begins with bit 0 → Bucket A 1100 begins with bit 1 → Bucket A Bucket A: [0101, 1100] (exactly at capacity, 2 records)
0011 begins with bit 0 → Bucket A, but Bucket A is already full. Bucket A must split. Since Bucket A's local depth (1) equals the global depth (1), the directory itself must also double in size, increasing the global depth to 2. New Directory (global depth 2, 4 entries): [00] → Bucket A [01] → Bucket A [10] → Bucket B [11] → Bucket B Records are redistributed based on their first 2 bits: 0101 → 01 → stays in Bucket A 0011 → 00 → stays in Bucket A 1100 → 11 → moves to Bucket B Bucket A (local depth 2): [0101, 0011] Bucket B (local depth 2): [1100]
1010 begins with bits 10 → Bucket B, which currently has room. Bucket B (local depth 2): [1100, 1010]
1111 begins with bits 11 → Bucket B, but Bucket B is now full. Bucket B's local depth (2) equals the current global depth (2), so once again the entire directory must double, increasing the global depth to 3. Bucket B splits into Bucket B and a new Bucket C, redistributed using 3 bits: 1100 → 110 → Bucket B 1010 → 101 → Bucket C 1111 → 111 → Bucket B Bucket A's records only ever needed 2 bits to distinguish them, so Bucket A's local depth remains 2, and it is now pointed to by two separate directory entries, [000] and [001], even though the global depth has grown to 3.
This last step highlights the elegant efficiency of extendible hashing: only the bucket that actually overflowed needed to split, and only its specific portion of the directory needed the extra bit of distinction, while Bucket A, which never overflowed, was left completely untouched, simply gaining an extra directory pointer rather than being needlessly split itself.
A collision occurs whenever two distinct keys are mapped by the hash function to the exact same bucket address. Collisions are an unavoidable reality of hashing, since a hash function maps a very large space of possible keys down into a much smaller number of buckets, making some overlap mathematically inevitable. Several standard techniques exist for handling collisions once they occur.
Chaining handles a collision by allowing each bucket to maintain a linked list, or chain, of all the records that happen to hash to that same address, simply appending a new record to the appropriate chain whenever a collision occurs.
Bucket 3 (using chaining): [23] → [38] → [43] All three keys hash to Bucket 3, and are simply linked together in a chain within that bucket rather than causing any conflict.
Open addressing handles a collision differently, by searching for the next available slot elsewhere in the structure according to some defined probing sequence, rather than growing a chain within the original bucket.
| Probing Technique | Description |
|---|---|
| Linear Probing | Checks the next slot immediately following the collided slot, continuing sequentially until an empty slot is found. |
| Quadratic Probing | Checks slots at increasing squared distances from the original slot, reducing a clustering problem that linear probing can suffer from. |
| Double Hashing | Uses a second, independent hash function to determine the step size used when searching for the next available slot. |
Hash Function: h(key) = key mod 5 Insert 12 → h(12) = 2 → Slot 2 Insert 17 → h(17) = 2 → Slot 2 is occupied, try Slot 3 → Slot 3 Insert 22 → h(22) = 2 → Slot 2 occupied, Slot 3 occupied, try Slot 4 → Slot 4
Each of these techniques involves its own tradeoffs: chaining handles a heavily skewed distribution of collisions gracefully, at the cost of needing extra memory for the chain pointers, while open addressing keeps everything within the original fixed structure, but can suffer from clustering, where collisions cause long, awkward runs of occupied slots that slow down future searches.
| Aspect | Static Hashing | Dynamic Hashing |
|---|---|---|
| Bucket Count | Fixed at the time the file is created, and never changes afterward. | Grows and shrinks automatically as records are inserted and deleted. |
| Behavior as File Grows | Performance steadily degrades due to increasing overflow chains once the file exceeds its originally planned size. | Performance remains consistently good, since the structure automatically expands to accommodate growth. |
| Complexity | Simple to implement and understand. | More complex, requiring directory management and bucket splitting logic. |
It is worth briefly comparing hashing directly against the B+ tree covered in the previous chapter, since both are commonly used indexing strategies, but they excel at genuinely different tasks. Hashing offers extremely fast, often single-step lookups for exact-match queries, but it provides no useful way to answer range queries, since a hash function deliberately scatters related key values across completely unrelated bucket addresses, with no preserved ordering at all. A B+ tree, by contrast, keeps its leaf nodes linked in sorted order, making it the clearly better choice whenever a query needs to retrieve a range of values rather than a single exact match. Many real database systems offer both indexing strategies, allowing developers to choose whichever fits a particular column's typical query pattern best.
| Mistake | Correct Understanding |
|---|---|
| Assuming hashing can efficiently support range queries. | Hashing deliberately scatters related keys across unrelated buckets, making it unsuitable for range queries, unlike tree-based indexes such as the B+ tree. |
| Confusing global depth with local depth in extendible hashing. | Global depth applies to the entire directory, while local depth applies to one specific bucket and can be less than or equal to the global depth. |
| Believing every bucket split in extendible hashing also doubles the directory. | The directory only doubles when the splitting bucket's local depth already equals the current global depth; otherwise, only that bucket splits. |
| Assuming collisions indicate a poorly designed hash function. | Some collisions are mathematically unavoidable whenever a large key space is mapped into a smaller number of buckets; a good hash function only aims to distribute them evenly. |
Hashing offers a fundamentally different strategy from the tree-based indexing covered in the previous two chapters, computing a record's location directly through a mathematical function rather than progressively narrowing a search through comparisons. Through static hashing's simplicity, extendible hashing's elegant ability to grow one bucket at a time, and the chaining and open addressing techniques used to handle unavoidable collisions, this chapter demonstrated exactly how databases achieve extremely fast exact-match lookups, complementing the range-query strengths of the B+ tree from the previous chapter.
In this tutorial, you learned how a hash function maps keys to bucket addresses, the limitations of static hashing as a file grows, a complete worked example building an extendible hash structure through four insertions including two directory-doubling splits, and how chaining and open addressing handle collisions. This chapter completes the full DBMS series on this site, carrying you from the fundamental purpose of a database management system all the way through relational theory, transaction safety, and the physical storage structures that make real-world database systems fast and reliable.