79:T677,class LinearHashTable: def __init__(self, initial_buckets=4): self.N0 = initial_buckets # Initial bucket count self.L = 0 # Current level self.S = 0 # Split pointer self.buckets = [[] for _ in range(initial_buckets)] def _hash(self, key: int) -> int: """Base hash function - typically a good integer hash.""" # Using multiplication method for demonstration A = 0.6180339887 # Golden ratio conjugate return int(len(self.buckets) * ((key * A) % 1)) def _h_level(self, key: int, level: int) -> int: """Hash function for a specific level.""" # h_L(k) = h(k) mod (N0 * 2^L) return hash(key) % (self.N0 * (2 ** level)) def _find_bucket(self, key: int) -> int: """Find the correct bucket for a key.""" # Step 1: Apply current level's hash function bucket = self._h_level(key, self.L) # Step 2: If bucket < S, it has already been split if bucket < self.S: # Step 3: Use next level's hash function bucket = self._h_level(key, self.L + 1) return bucket @property def total_buckets(self) -> int: """Current total number of buckets.""" return self.N0 * (2 ** self.L) + self.S def lookup(self, key: int): """Look up a key in the hash table.""" bucket_idx = self._find_bucket(key) bucket = self.buckets[bucket_idx] for k, v in bucket: if k == key: return v return None # Key not found7a:T5bc,#include #include #include #include #include template class LinearHashTable { private: size_t N0; // Initial bucket count size_t L; // Current level size_t S; // Split pointer std::vector>> buckets; std::hash hasher; // Hash function for a specific level size_t hLevel(const K& key, size_t level) const { size_t h = hasher(key); return h % (N0 * (1ULL << level)); } // Find correct bucket for a key size_t findBucket(const K& key) const { // Step 1: Apply current level's hash function size_t bucket = hLevel(key, L); // Step 2: If bucket < S, it was already split if (bucket < S) { // Step 3: Use next level's hash function bucket = hLevel(key, L + 1); } return bucket; } public: explicit LinearHashTable(size_t initialBuckets = 4) : N0(initialBuckets), L(0), S(0), buckets(initialBuckets) {} size_t totalBuckets() const { return N0 * (1ULL << L) + S; } std::optional lookup(const K& key) const { size_t bucketIdx = findBucket(key); for (const auto& [k, v] : buckets[bucketIdx]) { if (k == key) { return v; } } return std::nullopt; // Key not found } };7b:T419,**Average Chain Length Analysis:** Assuming uniform hashing and a load factor α (records per bucket), the expected chain length at any bucket is: **E[chain length] = α = n / N** Where n is the total number of records and N is the current bucket count. During linear growth, the load factor varies as buckets are added: - Maximum load (before a split cycle): α_max - Minimum load (after sufficient splits): α_min ≈ α_max / 2 The split trigger (discussed in a later page) controls this range. With typical triggers, α stays between 0.5 and 1.0, ensuring O(1) expected lookup time. **Space Overhead Analysis:** Linear hashing eliminates directory overhead entirely. The space overhead consists only of: 1. **State variables**: O(1) — just L, S, and N₀ 2. **Overflow chains**: O(n / bucket_capacity) for chaining 3. **Bucket array**: O(N) bucket pointers Compare this to extendible hashing, which requires O(2^d) directory entries where d is the global depth. Linear hashing's overhead is strictly O(N), never O(2^something_larger).7c:T448,def split(self): """ Perform a split operation on bucket S. Creates a new bucket and redistributes records. """ # Identify the bucket to split and its new sibling old_bucket_idx = self.S new_bucket_idx = self.S + self.N0 * (2 ** self.L) # Create the new bucket self.buckets.append([]) # Adds bucket at index new_bucket_idx # Get all records from the bucket being split old_records = self.buckets[old_bucket_idx] self.buckets[old_bucket_idx] = [] # Clear for redistribution # Redistribute records using h_{L+1} for key, value in old_records: # Use next level's hash function to determine placement new_bucket = self._h_level(key, self.L + 1) self.buckets[new_bucket].append((key, value)) # Advance the split pointer self.S += 1 # Check if we've completed a full round if self.S >= self.N0 * (2 ** self.L): # Move to next level: reset S, increment L self.S = 0 self.L += 1 # Note: No directory to update! This is the beauty of linear hashing.71:{"json":{"id":"seed_8e4b668680e68196d7311f6a52e4f711","slug":"linear-hashing","category":"Database Management Systems","topic":"Hash Indexing","title":"Linear Hashing","description":"Master linear hashing, a dynamic hash indexing technique that enables graceful growth without directory structures. Learn about linear growth, split pointers, split triggers, and performance characteristics that make linear hashing ideal for database systems.","difficulty":"ADVANCED","estimatedMinutes":75,"pages":[{"id":"seed_83188316ac52b638bdf2709ee5aab1e1","title":"Linear Growth","order":0,"content":[{"id":"opening-hook","title":"The Elegance of Incremental Expansion","content":[{"data":{"content":"In the realm of dynamic hashing, **linear hashing** stands as one of the most elegant solutions to the fundamental challenge of growing hash structures. While extendible hashing achieves dynamic growth through directory manipulation, linear hashing takes a remarkably different approach: it expands the hash table **one bucket at a time** in a predetermined, linear sequence.\n\nThis seemingly simple idea—growing incrementally rather than exponentially—yields profound consequences for memory management, I/O efficiency, and system predictability. Linear hashing, first proposed by Witold Litwin in 1980, eliminates the need for directory structures entirely while maintaining O(1) average-case lookup performance."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand linear hashing's growth mechanism from first principles—how buckets are added one at a time, why this approach eliminates directories, and how the mathematical properties of hash function families enable seamless transitions during expansion. You'll grasp both the theoretical foundations and practical implementation considerations.","variant":"info"},"type":"callout"}]},{"id":"problem-exponential-growth","title":"The Problem with Exponential Growth","content":[{"data":{"content":"Before appreciating linear hashing's innovation, we must understand the limitations it addresses. Traditional dynamic hashing schemes, including extendible hashing, suffer from a fundamental characteristic: **exponential growth in bucket count**.\n\nWhen an extendible hash table needs more capacity, it doubles its directory (from 2^d to 2^(d+1) entries). While individual bucket splits are local operations, the directory itself grows exponentially. This creates several problems:"},"type":"text"},{"data":{"items":["**Memory Spikes** — Directory doubling causes sudden, large memory allocations. A directory growing from 1 million to 2 million entries requires instantaneous allocation of significant memory, potentially causing allocation failures or memory pressure.","**Unpredictable Latency** — The doubling operation introduces latency spikes. While individual lookups remain O(1), a lookup that triggers a split followed by directory doubling experiences dramatically higher latency.","**Wasted Capacity** — After doubling, many directory entries point to the same bucket until subsequent splits occur. A freshly doubled directory may have 50% redundant pointers, consuming memory without improving access patterns.","**Concurrency Challenges** — Directory doubling affects the entire structure. All concurrent operations must either wait or use complex protocols to handle the transitional state, creating contention bottlenecks.","**Checkpoint Complexity** — For database systems requiring consistent snapshots, exponential directory growth complicates checkpoint operations since the directory size can change dramatically between checkpoints."],"title":{"icon":"AlertCircle","text":"Exponential Growth Limitations","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"AlertCircle","title":"The Doubling Dilemma","content":"Consider a hash table with 10 million buckets. When the next split requires directory expansion, the directory must grow from 10 million to 20 million entries—allocating 10 million new pointers simultaneously. This 'big bang' growth pattern is fundamentally at odds with gradual, predictable resource consumption.","variant":"warning"},"type":"callout"},{"data":{"content":"**The Linear Hashing Alternative:**\n\nLinear hashing addresses these problems by adopting a fundamentally different growth philosophy. Instead of asking \"how can we double efficiently?\", it asks \"what if we never doubled at all?\"\n\nThe answer lies in **linear growth**: adding exactly one bucket at a time, in a fixed sequence, regardless of where overflow actually occurs. This seemingly counterintuitive approach—splitting buckets that may not be overflowing—unlocks remarkable properties that make linear hashing particularly suitable for database systems."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"linear-growth-principle","title":"The Linear Growth Principle","content":[{"data":{"content":"Linear hashing's core insight is elegantly simple: **grow the hash table one bucket at a time, always in the same predetermined order**. This order is strictly sequential—bucket 0 splits first, then bucket 1, then bucket 2, and so on.\n\nThe key parameters that govern this process are:"},"type":"text"},{"data":{"rows":[["Initial bucket count","N₀","Number of buckets at initialization","Typically a power of 2 (common: 2, 4, 8)"],["Current level","L","Number of complete rounds of expansion","Determines which hash functions are active"],["Split pointer","S","Next bucket to be split (0 ≤ S < N₀ × 2^L)","Tracks expansion progress within current level"],["Current bucket count","N","Total buckets = N₀ × 2^L + S","Grows by exactly 1 with each split"]],"caption":"Linear Hashing State Parameters","headers":["Parameter","Symbol","Description","Role in Growth"]},"type":"table"},{"data":{"content":"**The Expansion Cycle:**\n\nA complete expansion cycle (called a **level** or **round**) works as follows:\n\n1. **Start of Level L**: The table has N₀ × 2^L buckets, and S = 0\n2. **Split Sequence**: Buckets are split in order: 0, 1, 2, ..., up to N₀ × 2^L - 1\n3. **End of Level L**: After N₀ × 2^L splits, S resets to 0, L increments to L+1\n4. **Level L+1 Begins**: The table now has N₀ × 2^(L+1) buckets\n\nWithin each level, the bucket count grows linearly from N₀ × 2^L to N₀ × 2^(L+1). The transition between levels is seamless—just S resetting to 0 and L incrementing."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Understanding the Level Concept","content":"Think of levels as 'generations' of the hash table. Level 0 uses the initial N₀ buckets. Level 1 doubles to 2N₀. Level 2 doubles again to 4N₀. But unlike extendible hashing, these doublings happen gradually—one bucket at a time—across an entire level's worth of splits.","variant":"tip"},"type":"callout"},{"data":{"content":"**Concrete Example:**\n\nLet's trace a linear hash table with N₀ = 4 through its first several splits:"},"type":"text"},{"data":{"rows":[["0","0,1,2,3","Bucket 0 → 0,4","0,1,2,3,4","1","0","5"],["1","0,1,2,3,4","Bucket 1 → 1,5","0,1,2,3,4,5","2","0","6"],["2","0,1,2,3,4,5","Bucket 2 → 2,6","0,1,2,3,4,5,6","3","0","7"],["3","0,1,2,3,4,5,6","Bucket 3 → 3,7","0,1,2,3,4,5,6,7","0","1","8"],["4","0,1,2,3,4,5,6,7","Bucket 0 → 0,8","0,1,...,7,8","1","1","9"]],"headers":["Split #","Before Split","Bucket Split","After Split","S","L","Total Buckets"]},"type":"table"},{"data":{"content":"Notice how the table grows by exactly one bucket per split. After 4 splits (one complete level), the table has doubled from 4 to 8 buckets. But this doubling is spread across 4 operations, not concentrated in one explosive growth event."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"hash-function-families","title":"Hash Function Families for Linear Growth","content":[{"data":{"content":"Linear hashing's ability to grow one bucket at a time depends on a carefully designed **family of hash functions** that work together seamlessly. Unlike static hashing with a single hash function, linear hashing uses a sequence of related functions where each function in the sequence has double the range of its predecessor.\n\nThe hash function family is typically defined as:\n\n**h_L(k) = h(k) mod (N₀ × 2^L)**\n\nWhere:\n- h(k) is a base hash function producing a large integer\n- L is the current level\n- N₀ is the initial bucket count\n- The result maps key k to a bucket in range [0, N₀ × 2^L - 1]"},"type":"text"},{"data":{"icon":"Info","title":"The Nesting Property","content":"The critical property is that h_{L+1}(k) either equals h_L(k) or equals h_L(k) + N₀ × 2^L. When a bucket at position b splits, its records distribute between bucket b (which keeps h_{L+1}(k) = b) and bucket b + N₀ × 2^L (which gets h_{L+1}(k) = b + N₀ × 2^L). This is why splitting works correctly.","variant":"note"},"type":"callout"},{"data":{"content":"**Dual Hash Function Lookup:**\n\nDuring the gradual expansion within a level, some buckets have been split while others have not. This creates a **transitional state** where we must carefully select which hash function to use for each lookup.\n\nThe algorithm for finding the correct bucket is:\n\n```\nfunction findBucket(key k):\n b = h_L(k) // Try current level's hash function\n if b < S:\n b = h_{L+1}(k) // Bucket was already split, use next level\n return b\n```\n\nThis two-step process is the heart of linear hashing's address calculation:"},"type":"text"},{"data":{"items":["**Step 1: Apply h_L** — Compute h(k) mod (N₀ × 2^L). This gives a bucket address in the range [0, N₀ × 2^L - 1], as if no splits had occurred in the current level.","**Step 2: Check against S** — If the computed bucket address b is less than the split pointer S, this bucket has already been split. The record might now be in the new sibling bucket.","**Step 3: Apply h_{L+1} if needed** — If b < S, recompute using h_{L+1}(k) = h(k) mod (N₀ × 2^(L+1)). This correctly places the record in either b or b + N₀ × 2^L.","**Step 4: Access the bucket** — The final bucket address is guaranteed to be valid and to contain the record if it exists."],"title":{"icon":"Zap","text":"Address Calculation Logic","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"fileName":"linear_hashing_address.py","languages":[{"code":"$79","label":"Python","value":"python"},{"code":"$7a","label":"C++","value":"cpp"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"mathematics-linear-growth","title":"The Mathematics of Linear Growth","content":[{"data":{"content":"Understanding the mathematical properties of linear growth helps explain why this approach works and enables precise analysis of performance characteristics.\n\n**Bucket Count at Any State:**\n\nThe total number of buckets at any point is:\n\n**N = N₀ × 2^L + S**\n\nWhere:\n- N₀ × 2^L represents completed levels (buckets from previous doublings)\n- S represents progress in the current level"},"type":"text"},{"data":{"rows":[["0","0 to 3","4 to 7","First level: Growing from 4 to 8 buckets"],["1","0 to 7","8 to 15","Second level: Growing from 8 to 16 buckets"],["2","0 to 15","16 to 31","Third level: Growing from 16 to 32 buckets"],["3","0 to 31","32 to 63","Fourth level: Growing from 32 to 64 buckets"],["L","0 to N₀×2^L - 1","N₀×2^L to N₀×2^(L+1) - 1","General formula for any level"]],"caption":"Bucket Count Evolution (N₀ = 4)","headers":["Level (L)","S Range","Bucket Count Range","Interpretation"]},"type":"table"},{"data":{"content":"**Hash Function Relationship:**\n\nThe family of hash functions satisfies a crucial **halving property**:\n\nh_L(k) = h_{L+1}(k) mod (N₀ × 2^L)\n\nThis means that for any key k:\n- h_{L+1}(k) is either equal to h_L(k), OR\n- h_{L+1}(k) is equal to h_L(k) + N₀ × 2^L\n\n**Proof:**\nLet h = h(k) be the base hash value.\n- h_L(k) = h mod (N₀ × 2^L)\n- h_{L+1}(k) = h mod (N₀ × 2^(L+1)) = h mod (2 × N₀ × 2^L)\n\nSince h mod (2M) equals either (h mod M) or (h mod M) + M:\n- h_{L+1}(k) ∈ {h_L(k), h_L(k) + N₀ × 2^L}"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Why This Property Matters","content":"This halving property ensures that when bucket b splits into buckets b and b + N₀ × 2^L, every record in bucket b has a well-defined destination. A record either stays in bucket b (its h_{L+1} value equals b) or moves to the new bucket (its h_{L+1} value equals b + N₀ × 2^L). No record can end up in any other bucket.","variant":"tip"},"type":"callout"},{"data":{"content":"$7b"},"type":"text"}],"titleType":"number","titleNumber":4},{"id":"split-mechanics-detail","title":"Split Mechanics in Detail","content":[{"data":{"content":"When a split occurs in linear hashing, the mechanics are straightforward but must be executed precisely. The bucket at position S is always the one that splits, regardless of which bucket triggered the split condition.\n\n**The Split Algorithm:**"},"type":"text"},{"data":{"fileName":"linear_hash_split.py","languages":[{"code":"$7c","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"items":["**Fixed Split Order** — Bucket S always splits next, regardless of which bucket overflowed. This is counterintuitive but crucial: it enables directory-free addressing.","**Binary Distribution** — Records from bucket S go to exactly two destinations: bucket S (stays) or bucket S + N₀ × 2^L (moves). No record can go elsewhere.","**Local Operation** — Only the splitting bucket and its new sibling are modified. All other buckets remain untouched, enabling excellent concurrency properties.","**Automatic Level Transition** — When S reaches the end of its range, incrementing L happens implicitly. There's no separate 'level up' operation.","**No Pointer Updates** — Unlike extendible hashing, no existing bucket pointers need modification. The new bucket simply extends the bucket array."],"title":{"icon":"CheckCircle","text":"Key Properties of Linear Hash Splits","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"Info","title":"The Deferred Splitting Insight","content":"A critical insight: when bucket 5 overflows, we split bucket S (say, bucket 2). Bucket 5's overflow is not immediately addressed! However, when S eventually reaches 5, it will split, resolving the overflow. This 'eventual resolution' is acceptable because overflow chains, while suboptimal, still provide O(1) expected access with good load factor management.","variant":"note"},"type":"callout"},{"data":{"content":"**Visualizing a Split Sequence:**\n\nConsider a linear hash table with N₀ = 4 at level L = 0, S = 2:\n\n```\nBefore split (6 buckets total):\n┌─────┬─────┬─────┬─────┬─────┬─────┐\n│ 0' │ 1' │ 2 │ 3 │ 4 │ 5 │\n└─────┴─────┴─────┴─────┴─────┴─────┘\n ↑ ↑ ↑\n | | └── S = 2 (next to split)\n | └── Already split (uses h₁)\n └── Already split (uses h₁)\n\nAfter split (7 buckets total):\n┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐\n│ 0' │ 1' │ 2' │ 3 │ 4 │ 5 │ 6 │\n└─────┴─────┴─────┴─────┴─────┴─────┴─────┘\n ↑ ↑ ↑ ↑ ↑\n | | | └── S = 3 (next to split)\n | | └── Just split into 2 and 6\n | └── Previously split\n └── Previously split\n```\n\nThe prime notation (0', 1', 2') indicates buckets already split in this level—they now use h₁ instead of h₀ for addressing."},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"comparison-extendible","title":"Comparison with Extendible Hashing","content":[{"data":{"content":"Linear hashing and extendible hashing are often compared as the two major dynamic hashing techniques. Understanding their differences illuminates when each is preferable."},"type":"text"},{"data":{"rows":[["Directory","None (O(1) state)","Required (O(2^d) entries)"],["Growth Pattern","One bucket at a time","Bucket + potential directory doubling"],["Split Target","Fixed (bucket S)","Flexible (overflowing bucket)"],["Address Calculation","Two hash computations (worst case)","One directory lookup + one hash"],["Memory Overhead","Minimal (L, S, N₀ only)","Directory can dominate for high depths"],["Latency Spikes","No directory doubling","Directory doubling causes spikes"],["Overflow Handling","Chains may persist longer","Immediate split of overflowing bucket"],["Implementation","Simpler state management","More complex directory management"],["Concurrency","Easier (localized updates)","Harder (directory coordination required)"]],"caption":"Linear Hashing vs. Extendible Hashing","headers":["Aspect","Linear Hashing","Extendible Hashing"]},"type":"table"},{"data":{"left":[{"data":{"items":["Predictable, incremental growth","No directory memory overhead","Simpler concurrent access","No latency spikes from doubling","Better for disk-based systems"],"title":{"icon":"CheckCircle","text":"Linear Hashing Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["May split non-overflowing buckets","Overflow chains can persist","Two hash computations sometimes needed","Load factor varies during expansion","Less immediate overflow resolution"],"title":{"icon":"AlertCircle","text":"Linear Hashing Disadvantages","type":"icon","color":"accent","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Lightbulb","title":"When to Choose Linear Hashing","content":"Linear hashing excels in disk-based database systems where I/O predictability matters more than perfect bucket allocation. It's also preferred in concurrent environments due to simpler synchronization requirements. Extendible hashing may be preferable for in-memory tables where directory overhead is less concerning and immediate overflow resolution is valuable.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"summary","title":"Summary: Linear Growth Fundamentals","content":[{"data":{"content":"We've explored the foundational concept of linear hashing: **linear growth**. This elegant approach to dynamic hash tables eliminates directory structures by growing one bucket at a time in a predetermined sequence."},"type":"text"},{"data":{"type":"ordered","items":["**Linear growth adds one bucket at a time** — The split pointer S advances sequentially through buckets, avoiding explosive directory growth.","**Hash function families enable smooth transitions** — The relationship h_L(k) = h_{L+1}(k) mod (range) ensures correct record distribution during splits.","**Two-step address calculation** — Lookups compute h_L(k), then check if the bucket was already split and apply h_{L+1}(k) if needed.","**Level transitions are implicit** — When S completes a full round, it resets to 0 and L increments, naturally doubling capacity over time.","**No directory overhead** — Only O(1) state variables are needed: L, S, and N₀.","**Predictable resource consumption** — Memory grows linearly, never exponentially in a single operation."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nNow that we understand how linear hashing grows, we'll examine the **split pointer** mechanism in detail. The split pointer is the state machine at the heart of linear hashing—tracking exactly which bucket splits next and managing the transition between levels. Understanding its behavior is essential for implementing linear hashing correctly and analyzing its performance characteristics."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the linear growth mechanism that distinguishes linear hashing from other dynamic hashing schemes. This foundation—growing one bucket at a time without directory structures—enables the predictable, efficient behavior that makes linear hashing valuable for database systems.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_a3139abe16cbd8360eed37018ec5af26","title":"Split Pointer","order":1,"content":null,"isLocked":true},{"id":"seed_a25dc64a1df5cffd8261281e07ca0b96","title":"Split Trigger","order":2,"content":null,"isLocked":true},{"id":"seed_de89b8443b04010bcbae41d785cbf510","title":"No Directory Needed","order":3,"content":null,"isLocked":true},{"id":"seed_dd8f718072792b3ba89e93c756717ad7","title":"Performance Characteristics","order":4,"content":null,"isLocked":true}]}}