hash_tables_example.C

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
#include <iostream>
#include <string>
#include <chrono>
#include <random>
#include <iomanip>
 
#include <tpl_dynSetHash.H>
#include <tpl_odhash.H>
 
using namespace std;
using namespace Aleph;
 
static void print_usage(const char* prog)
{
  cout << "Usage: " << prog << " [-s <chaining|linear|open|performance|all>] [--help]\n";
  cout << "\nIf no selector is given, all demos are executed.\n";
}
 
// =============================================================================
// Example 1: DynSetLhash - Separate Chaining
// =============================================================================
 
void demo_dynset_lhash()
{
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║      EXAMPLE 1: DynSetLhash (Separate Chaining)                  ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  cout << "DynSetLhash uses linked lists to handle collisions.\n";
  cout << "Each bucket is a list of entries with the same hash.\n\n";
 
  DynSetLhash<int> set;
 
  // Insert values
  vector<int> values = {10, 20, 30, 40, 50, 60, 70, 80};
 
  cout << "Inserting values:\n";
  for (int v : values) {
    set.insert(v);
    cout << "  ✓ " << v << "\n";
  }
 
  cout << "\nSet size: " << set.size() << "\n";
 
  cout << "\n--- Membership testing ---\n\n";
 
  auto test_contains = [&](int key) {
    bool found = set.contains(key);
    cout << "  contains(" << key << "): " << (found ? "YES" : "NO") << "\n";
  };
 
  test_contains(30);
  test_contains(50);
  test_contains(100);
  test_contains(70);
 
  cout << "\n--- Removal ---\n\n";
 
  cout << "Removing 40...\n";
  set.remove(40);
 
  cout << "Removing 70...\n";
  set.remove(70);
 
  test_contains(40);
  test_contains(70);
 
  cout << "\nFinal size: " << set.size() << "\n";
 
  cout << "\n--- Iteration ---\n\n";
  cout << "All elements: ";
  set.for_each([](const int& v) { cout << v << " "; });
  cout << "\n";
}
 
// =============================================================================
// Example 2: DynSetLinHash - Linear Hashing
// =============================================================================
 
void demo_dynset_linhash()
{
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║      EXAMPLE 2: DynSetLinHash (Linear Hashing)                   ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  cout << "Linear hashing grows the table incrementally, one bucket at a time.\n";
  cout << "This avoids expensive full-table rehashing operations.\n\n";
 
  DynSetLinHash<int> set;
 
  cout << "Inserting 100 random integers...\n\n";
 
  mt19937 rng(42);
  uniform_int_distribution<int> dist(1, 10000);
 
  for (int i = 0; i < 100; ++i)
    set.insert(dist(rng));
 
  cout << "Set size: " << set.size() << "\n";
 
  cout << "\n--- Membership testing ---\n\n";
 
  // Reset RNG and check first few values
  rng.seed(42);
  for (int i = 0; i < 5; ++i) {
    int v = dist(rng);
    cout << "  contains(" << v << "): " 
         << (set.contains(v) ? "YES" : "NO") << "\n";
  }
 
  cout << "  contains(99999): " 
       << (set.contains(99999) ? "YES" : "NO") << "\n";
}
 
// =============================================================================
// Example 3: ODhashTable - Open Addressing  
// =============================================================================
 
void demo_odhash()
{
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║      EXAMPLE 3: ODhashTable (Open Addressing)                    ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  cout << "ODhashTable stores all entries in a contiguous array.\n";
  cout << "Collisions are resolved by double hashing + linear probing.\n\n";
 
  // Create hash table with capacity 17 (prime for better distribution)
  ODhashTable<int> table(17);
 
  cout << "Table capacity: 17 (prime number recommended)\n\n";
 
  // Insert values
  vector<int> values = {10, 20, 30, 40, 50, 60, 70, 80};
 
  cout << "Inserting values:\n";
  for (int v : values) {
    int* result = table.insert(v);
    if (result)
      cout << "  ✓ Inserted: " << v << "\n";
    else
      cout << "  ✗ Failed (duplicate?): " << v << "\n";
  }
 
  cout << "\nTable statistics:\n";
  cout << "  Size: " << table.size() << "\n";
  cout << "  Capacity: " << table.capacity() << "\n";
  cout << "  Load factor: " << fixed << setprecision(2)
       << (double)table.size() / table.capacity() << "\n";
 
  cout << "\n--- Search operations ---\n\n";
 
  auto search_test = [&](int key) {
    int* found = table.search(key);
    cout << "  search(" << key << "): "
         << (found ? "FOUND" : "NOT FOUND") << "\n";
  };
 
  search_test(30);
  search_test(50);
  search_test(100);
  search_test(70);
 
  cout << "\n--- Remove operations ---\n\n";
 
  cout << "Removing 40...\n";
  table.remove(40);
 
  search_test(40);
 
  cout << "\nFinal size: " << table.size() << "\n";
}
 
// =============================================================================
// Example 4: Performance Comparison
// =============================================================================
 
void demo_performance()
{
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║      EXAMPLE 4: Performance Comparison                           ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  const int N = 50000;
  cout << "Benchmark: " << N << " insertions + " << N << " lookups\n\n";
 
  mt19937 rng(12345);
  vector<int> values;
  for (int i = 0; i < N; ++i)
    values.push_back(rng());
 
  // DynSetLhash benchmark
  {
    DynSetLhash<int> set;
    auto start = chrono::high_resolution_clock::now();
    
    for (int v : values)
      set.insert(v);
    
    auto mid = chrono::high_resolution_clock::now();
    
    size_t found = 0;
    for (int v : values)
      if (set.contains(v))
        ++found;
    
    auto end = chrono::high_resolution_clock::now();
    
    auto insert_ms = chrono::duration_cast<chrono::milliseconds>(mid - start).count();
    auto search_ms = chrono::duration_cast<chrono::milliseconds>(end - mid).count();
    
    cout << "DynSetLhash (chaining):\n";
    cout << "  Insert: " << insert_ms << " ms\n";
    cout << "  Search: " << search_ms << " ms (found " << found << ")\n";
    cout << "  Size:   " << set.size() << "\n\n";
  }
 
  // DynSetLinHash benchmark
  {
    DynSetLinHash<int> set;
    auto start = chrono::high_resolution_clock::now();
    
    for (int v : values)
      set.insert(v);
    
    auto mid = chrono::high_resolution_clock::now();
    
    size_t found = 0;
    for (int v : values)
      if (set.contains(v))
        ++found;
    
    auto end = chrono::high_resolution_clock::now();
    
    auto insert_ms = chrono::duration_cast<chrono::milliseconds>(mid - start).count();
    auto search_ms = chrono::duration_cast<chrono::milliseconds>(end - mid).count();
    
    cout << "DynSetLinHash (linear hashing):\n";
    cout << "  Insert: " << insert_ms << " ms\n";
    cout << "  Search: " << search_ms << " ms (found " << found << ")\n";
    cout << "  Size:   " << set.size() << "\n\n";
  }
 
  // ODhashTable benchmark
  {
    ODhashTable<int> table(N * 2);
    auto start = chrono::high_resolution_clock::now();
    
    for (int v : values)
      (void) table.insert(v);
    
    auto mid = chrono::high_resolution_clock::now();
    
    size_t found = 0;
    for (int v : values)
      if (table.search(v))
        ++found;
    
    auto end = chrono::high_resolution_clock::now();
    
    auto insert_ms = chrono::duration_cast<chrono::milliseconds>(mid - start).count();
    auto search_ms = chrono::duration_cast<chrono::milliseconds>(end - mid).count();
    
    cout << "ODhashTable (open addressing):\n";
    cout << "  Insert: " << insert_ms << " ms\n";
    cout << "  Search: " << search_ms << " ms (found " << found << ")\n";
    cout << "  Size:   " << table.size() << "\n\n";
  }
}
 
// =============================================================================
// Main
// =============================================================================
 
int main(int argc, char* argv[])
{
  string selector;
  for (int i = 1; i < argc; ++i)
    {
      const string arg = argv[i];
      if (arg == "--help" || arg == "-h")
        {
          print_usage(argv[0]);
          return 0;
        }
      if (arg == "-s")
        {
          if (i + 1 >= argc)
            {
              print_usage(argv[0]);
              return 1;
            }
          selector = argv[++i];
          continue;
        }
 
      cout << "Unknown argument: " << arg << "\n";
      print_usage(argv[0]);
      return 1;
    }
 
  if (selector.empty())
    selector = "all";
 
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║              Hash Tables in Aleph-w Library                      ║\n";
  cout << "║                                                                  ║\n";
  cout << "║     Aleph-w Library - https://github.com/lrleon/Aleph-w          ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n";
 
  const bool run_all = (selector == "all");
  if (run_all || selector == "chaining")
    demo_dynset_lhash();
  if (run_all || selector == "linear")
    demo_dynset_linhash();
  if (run_all || selector == "open")
    demo_odhash();
  if (run_all || selector == "performance")
    demo_performance();
 
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║                     Hash Table Summary                           ║\n";
  cout << "╠══════════════════════════════════════════════════════════════════╣\n";
  cout << "║  DynSetLhash:   Separate chaining, flexible, easy deletion      ║\n";
  cout << "║  DynSetLinHash: Linear hashing, smooth growth, no spikes        ║\n";
  cout << "║  ODhashTable:   Open addressing, cache-friendly, fast           ║\n";
  cout << "║                                                                  ║\n";
  cout << "║  Choose based on your use case:                                  ║\n";
  cout << "║  • DynSetLhash: General purpose, many deletions                 ║\n";
  cout << "║  • DynSetLinHash: Realtime, predictable performance             ║\n";
  cout << "║  • ODhashTable: Known size, maximum speed                       ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  return 0;
}