tpl_odhash.H File Reference

Open addressing hash table with double hashing. More...

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

Include dependency graph for tpl_odhash.H:

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

Go to the source code of this file.

Classes
class	Aleph::ODhashTable< Key, Cmp >
	Open addressing hash table with double hashing collision resolution. More...
struct	Aleph::ODhashTable< 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::SetODhash = ODhashTable< Key, Cmp >

Detailed Description

Open addressing hash table with double hashing.

This file implements an open-addressed hash table that uses double hashing for collision resolution. Double hashing provides excellent distribution and avoids primary and secondary clustering.

Double Hashing Strategy

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

h(k, i) = (h1(k) + i * h2(k)) mod m

where h2(k) is a secondary hash function.

Key Features

• No clustering (unlike linear probing)
• Better cache locality than chaining
• 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)

Expected probes: 1/(1-α) for unsuccessful, (1/α)ln(1/(1-α)) for successful where α is the load factor.

Load Factor

The table resizes when load factor exceeds a threshold (default ~0.5). Lower load factors mean faster operations but more memory.

Usage Example

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

Comparison with OLhashTable

Feature	ODhashTable	OLhashTable
Probe	Double hash	Linear
Clustering	None	Primary
Cache	Good	Excellent

See also

tpl_olhash.H Linear probing variant

tpl_lhash.H Chaining with linear expansion

hashDry.H Common open addressing utilities

Author

Leandro Rabindranath León

Definition in file tpl_odhash.H.