tpl_olhash.H File Reference

Open addressing hash table with linear probing. More...

#include <iostream>
#include <cstddef>
#include <cstdint>
#include <primes.H>
#include <dlink.H>
#include <ahDry.H>
#include <hash-dry.H>
#include <hashDry.H>
#include <hash-fct.H>
#include <ah-errors.H>

Include dependency graph for tpl_olhash.H:

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

Go to the source code of this file.

Classes
class	Aleph::OLhashTable< Key, Cmp >
	Open addressing hash table with linear probing collision resolution. More...
struct	Aleph::OLhashTable< Key, Cmp >::Bucket

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

Typedefs
template<typename Key , class Cmp = Aleph::equal_to<Key>>
using	Aleph::SetOLhash = OLhashTable< Key, Cmp >

Detailed Description

Open addressing hash table with linear probing.

This file implements an open-addressed hash table using linear probing for collision resolution. Linear probing offers excellent cache performance due to sequential memory access patterns.

Linear Probing Strategy

When a collision occurs at position h(k), the probe sequence is:

h(k, i) = (h(k) + i) mod m

Simply checking the next slot until an empty one is found.

Key Features

• Excellent cache locality (sequential access)
• Simple implementation
• Automatic resizing based on load factor
• Supports deletion with tombstones

Complexity

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

Primary Clustering

Linear probing suffers from primary clustering: consecutive occupied slots form clusters that grow over time. Keep load factor < 0.5 to minimize this effect.

Usage Example

OLhashTable<int> table;
 
table.insert(42);
table.insert(17);
 
if (table.search(42) != nullptr)
  std::cout << "Found 42\n";
 
table.remove(42);

When to Use

• Small to medium tables
• Cache performance is critical
• Keys are uniformly distributed

See also

tpl_odhash.H Double hashing (less clustering)

tpl_lhash.H Chaining (no clustering)

hashDry.H Common open addressing utilities

Author

Leandro Rabindranath León

Definition in file tpl_olhash.H.