hash_resize.C File Reference

Example demonstrating hash table with automatic resizing. More...

#include <tclap/CmdLine.h>
#include <tpl_dynMapOhash.H>
#include <iostream>
#include <cassert>

Include dependency graph for hash_resize.C:

Go to the source code of this file.

Classes
struct	Foo

Functions
void	fill (size_t n)
void	verify ()
int	main (int argc, char **argv)

Variables
MapOLhash< int, Foo >	tbl
DynArray< Foo >	backup

Detailed Description

Example demonstrating hash table with automatic resizing.

This example demonstrates how MapOLhash (Open Addressing Hash Table) automatically resizes itself to maintain good performance as elements are inserted. Automatic resizing is crucial for maintaining O(1) average performance in hash tables.

Why Resizing Matters

Load Factor Impact

Hash table performance degrades when the load factor (elements/buckets) becomes too high:

• Low load factor (< 0.5): Many empty buckets, wasted memory
• Optimal load factor (0.7-0.8): Good balance of speed and memory
• High load factor (> 0.9): Many collisions, performance degrades

Performance Degradation

Without resizing:

• Operations degrade: From O(1) average to O(n) worst case
• Collisions increase: More elements compete for same buckets
• Linear probing: Longer probe sequences

Common Thresholds

Hash Table Type	Resize Threshold	Reason
Open addressing	Load factor > 0.7-0.8	Collisions become frequent
Separate chaining	Load factor > 1.0-2.0	Chains become too long

Automatic Resizing Strategy

How MapOLhash Resizes

MapOLhash uses open addressing (linear probing or double hashing):

1. Initial size: Starts with a small number of buckets
2. Load monitoring: Tracks load factor during insertions
3. Threshold check: Checks if load factor exceeds threshold
4. Automatic resize: When threshold exceeded:
   • Allocates larger bucket array (typically 2× size)
   • Rehashes all existing elements (O(n) operation)
   • Updates hash table structure
   • Continues insertion

Resize Operation

Resize(old_size, new_size):
  1. Allocate new bucket array of size new_size
  2. For each element in old array:
     - Compute new hash (using new_size)
     - Insert into new array
  3. Deallocate old array
  4. Update hash table size

Cost: O(n) where n = number of elements Frequency: O(log n) times (each resize doubles size) Amortized cost: O(1) per insertion

What This Example Demonstrates

1. Insertion: Adding many elements to the hash table
2. Automatic resizing: Observing resize operations as load increases
3. Verification: Ensuring all elements are still accessible after resize
4. Performance: Demonstrating O(1) average access maintained
5. Load factor tracking: Monitoring load factor over time

Key Operations

• **insert(key, value)**: Insert key-value pair (may trigger resize)
• **search(key)**: Find value by key (O(1) average)
• **size()**: Get current number of elements
• **capacity()**: Get current number of buckets
• **load_factor()**: Get current load factor

Resize Behavior

When Resize Occurs

• Trigger: Load factor exceeds threshold (typically 0.75)
• Frequency: Logarithmic (each resize doubles size)
• Cost: O(n) per resize, but amortized O(1) per insertion

Resize Size

Common strategies:

• Double: new_size = 2 × old_size (most common)
• Prime: Use next prime number (better for some hash functions)
• Power of 2: new_size = 2^k (fast modulo)

Performance Characteristics

Operation	Before Resize	After Resize	Amortized
Insert	O(1) → O(n)	O(1)	O(1)
Search	O(1) → O(n)	O(1)	O(1)
Delete	O(1) → O(n)	O(1)	O(1)

Usage

# Insert 1000 elements and observe resizing
./hash_resize -n 1000
 
# Insert 10000 elements
./hash_resize -n 10000

Expected Output

The program prints progress during insertion and then verifies that every inserted element is still accessible after all insertions (resizes, if any, are handled internally by MapOLhash).

See also

tpl_dynMapOhash.H Open addressing hash map implementation

hash_tables_example.C Hash table implementations comparison

Author

Leandro Rabindranath León

Definition in file hash_resize.C.

Function Documentation

fill()

void fill

(

size_t

n

)

Definition at line 184 of file hash_resize.C.

References backup, Aleph::maps(), Aleph::HTList::size(), and tbl.

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 218 of file hash_resize.C.

References Aleph::fill(), Aleph::maps(), and verify().

verify()

void verify

(

)

Definition at line 201 of file hash_resize.C.

References backup, Aleph::count(), Aleph::maps(), and tbl.

Referenced by main().

Variable Documentation

backup

DynArray<Foo> backup

Definition at line 182 of file hash_resize.C.

Referenced by fill(), and verify().

tbl

MapOLhash<int, Foo> tbl

Definition at line 181 of file hash_resize.C.

Referenced by count_bucket_states(), count_odhash_bucket_states(), fill(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TYPED_TEST_P(), TYPED_TEST_P(), TYPED_TEST_P(), TYPED_TEST_P(), and verify().