Probe Complexity During Insertion in Elastic and Open-Addressing Hash Tables

# Probe Complexity Experiment Dataset ## Overview This dataset contains the benchmark results of an experiment investigating the probe complexity of different open-addressing hashing schemes during insertion. The experiment compares the following hashing schemes: * Linear hashing * Quadratic hashing * Double hashing * Elastic hashing For each hashing scheme, the number of probes required to insert keys into the hash table was recorded across a range of load factors. The dataset contains the complete probe-count data produced by the benchmark runs rather than aggregated statistics. This allows the data to be independently aggregated and analyzed. ## Experimental Design The hash table capacity was fixed at $2^{16} = 65{,}536$ for all configurations. The target load factors range from 0.05 to 0.95 in increments of 0.05, with an additional configuration at a load factor of 0.99. For a target load factor ($\alpha$), the number of keys inserted into the table is calculated as $n = \left\lceil \alpha \cdot 2^{16} \right\rceil$ Each hashing-scheme and load-factor configuration was executed 100 times. The keys and hash-function seeds were randomized between repetitions. ### Measured Quantity The experiment measures the probe complexity incurred during insertion. For each inserted key, the number of probes required to place the key in the hash table is recorded. The complete probe-count state resulting from each experiment run is stored in the NPZ dataset. ## Data Files The dataset consists of two files: ```text metadata.json probe_complexity_experiment.npz ``` ### `metadata.json` The JSON file contains metadata describing the experimental configurations and the corresponding data stored in the NPZ file. Each experiment configuration contains a key identifying the corresponding namespace within the NPZ file. The key is not a filesystem path; it is a logical identifier used to access the corresponding arrays in the NPZ file. Each run contains a repetition number identifying the corresponding probe-complexity array in the NPZ file. The metadata also contains information about the hash-table configuration, input parameters, and the status of individual benchmark runs. ### `probe_complexity_experiment.npz` The NPZ file contains the complete probe-count data for all benchmark runs. Data are organized by experiment key and repetition: ```text {experiment-key}/1.npy {experiment-key}/2.npy ... {experiment-key}/100.npy ``` Each array represents the probe-count state of the hash table after one complete insertion run for a particular hashing scheme, capacity, and load-factor configuration. For each occupied table slot, the corresponding value represents the number of probes required to insert the key stored in that slot. Empty table slots are represented by the sentinel value UINT64_MAX where UINT64_MAX is the maximum representable value of an unsigned 64-bit integer. Sentinel values should therefore be excluded when calculating statistics over occupied table slots. Example Data Access ## Example Data Access The metadata and NPZ data can be loaded using Python with NumPy and pandas. The metadata identifies the NPZ keys required to reconstruct the individual experiment runs. For example: ```python import json from pathlib import Path import numpy as np import pandas as pd def get_probing_experiment_dataframe(metadata_json: Path, data_npz: Path) -> pd.DataFrame: with open(metadata_json) as f: meta_data = json.load(f) data = np.load(data_npz) rows = [] for experiment in meta_data["experiments"]: key = experiment["key"] for run in experiment["repetitions"]: probe_complexity_suffix = Path(run["array"]).stem _hashtable = experiment.get("hashtable", {}) _input = experiment.get("input", {}) rows.append( { "hashtable_type" : as_str(_hashtable.get("type")), "capacity" : as_int(_hashtable.get("capacity")), "load_factor" : as_float(_input.get("load_factor")), "error_occurred" : as_bool(run.get("error_occurred")), "skipped" : as_bool(run.get("skipped")), "probe_complexity" : as_np_array(data[f"{key}/{probe_complexity_suffix}"]), } ) return pd.DataFrame(rows) ``` The resulting DataFrame contains one row per benchmark run. The `probe_complexity` and columns contain NumPy arrays representing the corresponding data for that run. ## Data Interpretation The main experimental factors are: | Factor | Values | | -------------- | ---------------------------------- | | Hashing scheme | Linear, Quadratic, Double, Elastic | | Capacity | ($2^{16} = 65{,}536$) | | Load factor | $0.05, 0.10, ..., 0.95, 0.99$ | | Repetitions | 100 per configuration | | Number of keys | ($\lceil\alpha \cdot 2^{16}\rceil$) | The probe-count arrays preserve the individual observations produced during each run. No averaging, median aggregation, or other statistical reduction has been applied to the stored probe-count data. ## Reproducibility The accompanying metadata contains additional information about the benchmark execution environment and the experimental configuration. ## Source Code The source code used to generate and analyze the benchmark data is available in the accompanying [Open Addressing Hashing Benchmark repository](https://gitlab.uni-trier.de/s4plsimo/open-addressing-hashing-benchmark). ## License This dataset is released under the **Creative Commons Attribution 4.0 International (CC BY 4.0)** license. See the accompanying `LICENSE` file for the license terms.