tpl_lhash.H File Reference

Linear hashing with dynamic bucket expansion. More...

#include <iostream>
#include <primes.H>
#include <dlink.H>
#include <htlist.H>
#include <tpl_dynArray.H>
#include <hashDry.H>
#include <hash-fct.H>
#include <hash-dry.H>
#include <ah-errors.H>

Include dependency graph for tpl_lhash.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::GenLhashTable< Key, BucketType, Cmp >
	Generic hash table with collision resolution by separate chaining. More...
class	Aleph::GenLhashTable< Key, BucketType, Cmp >::Iterator
	Iterator over a GenLhashTable hash table. More...
struct	Aleph::LhashBucketVtl< Key >
	Bucket with virtual destructor for a hash table with collision resolution by separate chaining. More...
struct	Aleph::LhashTable< Key, Cmp >
	Generic hash table with collision resolution by separate chaining and buckets without virtual destructor. More...
struct	Aleph::LhashTableVtl< Key, Cmp >
	Generic hash table with collision resolution by separate chaining and buckets with virtual destructor. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Typedefs
template<typename Key >
using	Aleph::LhashBucket = Dnode< Key >
	Bucket without virtual destructor for a hash table with collision resolution by separate chaining.

Detailed Description

Linear hashing with dynamic bucket expansion.

This file implements Linear Hashing, a dynamic hash table technique that grows gracefully without requiring a complete rehash. Buckets are split one at a time as the load factor increases.

Algorithm Overview

Linear hashing uses two hash functions during expansion:

• h0(k) = k mod m (current level)
• h1(k) = k mod 2m (next level)

When a bucket overflows, the next bucket in sequence is split, not necessarily the overflowing one. This ensures predictable growth.

Key Features

• Incremental expansion (no full rehash needed)
• Configurable load factor thresholds
• Automatic contraction when load decreases
• Supports duplicate keys
• Chaining for collision resolution

Complexity

Operation	Average	Worst Case
insert	O(1)	O(n)
search	O(1)	O(n)
remove	O(1)	O(n)
expand	O(1) amortized	O(n)

Load Factor Control

• upper_alpha: When exceeded, triggers bucket split
• lower_alpha: When below, triggers bucket contraction

Usage Example

LhashTable<int> table;
 
table.insert(new Bucket(42));
table.insert(new Bucket(17));
 
auto* found = table.search(42);
if (found)
  std::cout << "Found: " << found->get_key() << "\n";
 
table.remove(found);

Comparison with Other Hash Tables

Feature	LhashTable	ODhashTable	OLhashTable
Collision	Chaining	Double hash	Linear probe
Growth	Linear	Full rehash	Full rehash
Memory	Extra pointers	Compact	Compact

See also

tpl_odhash.H Open addressing with double hashing

tpl_olhash.H Open addressing with linear probing

tpl_dynSetHash.H High-level hash set interface

Author

Leandro Rabindranath León

Definition in file tpl_lhash.H.