Chained Hash Table

Generic hash table implementation in Java using separate chaining (doubly linked lists) for collision resolution, benchmarked with 1,000,000 records and 100,000 queries across varying bucket counts.

Description

This project implements a chained hash table from scratch in Java, using a doubly linked list at each bucket to handle collisions. The implementation is fully generic, supporting any key-value types through a pluggable HashFunction interface. A Python script generates the test datasets: 1,000,000 main records, 100,000 queries with keys known to exist (for successful search benchmarks), and 100,000 queries with keys guaranteed absent (for unsuccessful search benchmarks). Performance is measured for insertion, search, and deletion across three bucket counts.

Features

• Generic ChainTable<K, V> with pluggable hash function via HashFunction<T> interface
• Doubly linked list implementation (DoublyLinkedList<T>) with predicate-based search and delete
• Hash functions for both Integer and String key types
• Java lambda-based element search using Predicate<T>
• Python data generator producing deterministic, reproducible datasets
• Benchmarks for insertion, successful search, unsuccessful search, and deletion
• Three bucket sizes tested: 1,001, 5,003, and 10,007 (all prime)

Topics Covered

• Hash tables
• Separate chaining (collision resolution)
• Doubly linked lists
• Generic programming (Java generics)
• Hash function design
• Load factor analysis
• Benchmarking methodology

Project Structure

Java/DS/
  ChainTable.java                 # Hash table with separate chaining
  DoublyLinkedList.java           # Doubly linked list (Node + list operations)
  Entry.java                      # Key-value pair class
  hash/
    HashFunction.java             # Hash function interface
    IntegerHash.java              # Hash function for Integer keys (modular)
    StringHash.java               # Hash function for String keys (ASCII sum)
  hashBenchmarkResult/
    HashBenchmarkRunner.java      # Benchmark harness (load, query, measure)
    MainDataTester.java           # Benchmark: initial data loading
    Query1Tester.java             # Benchmark: successful search queries
    Query2Tester.java             # Benchmark: unsuccessful search queries
Python/
  generate_data.py                # Dataset generator (1M records + queries)
  main_data.txt                   # Generated main dataset (1M lines)
  query_1.txt                     # 100K queries (keys present in main data)
  query_2.txt                     # 100K queries (keys absent from main data)
AryanGhasemi-Result.xlsx          # Benchmark results

Algorithms

Chaining with Doubly Linked Lists

Each bucket in the hash table points to a doubly linked list. On insertion, if the key already exists, its value is updated in place; otherwise, a new entry is appended to the tail. On search, the list is traversed using a Predicate<T> lambda that matches on the key. On deletion, the matching node is unlinked from the list.

Hash Functions

• IntegerHash: h(k) = |k| mod m — simple modular hashing.
• StringHash: h(k) = (sum of ASCII values) mod m — sums all character codes and takes modulo bucket count. Simple but effective for random string keys.

Load Factor Design

The three bucket counts (1,001 / 5,003 / 10,007) are all prime numbers, which improves distribution uniformity for modular hashing. With 1,000,000 records:

• m = 1,001 → load factor ≈ 999 (very dense chains)
• m = 5,003 → load factor ≈ 200
• m = 10,007 → load factor ≈ 100

Experimental Results

Benchmarks were run on Windows 11, Intel i9-13980HX. All times in milliseconds.

Query 1 — Successful Search (100,000 keys present in main data)

m (buckets)	Insert	Search	Delete
1,001	2,075	2,073	2,044
5,003	2,069	1,841	1,980
10,007	2,004	1,788	1,654

Query 2 — Unsuccessful Search (100,000 keys absent from main data)

m (buckets)	Insert	Search	Delete
1,001	4,933	2,865	4,257
5,003	4,537	2,801	3,681
10,007	3,875	2,751	2,997

Key Observations

• Unsuccessful search and delete are significantly slower with dense chains. At m=1,001 (load factor ~999), the average chain length approaches 1,000 nodes, so each failed search must traverse the entire list. Increasing m to 10,007 reduces this substantially.
• Insertion times for query 2 are high because each insertion first searches for an existing key (to update rather than duplicate), and unsuccessful search must traverse the full chain.
• Successful search is less affected by bucket count because matching keys tend to be found partway through the chain rather than requiring a full traversal.
• Increasing the bucket count from 1,001 to 10,007 cuts deletion time by roughly 30-40% in the unsuccessful query scenario.

Complexity Analysis

Operation	Average Case	Worst Case
Insert	O(1 + α)	O(n)
Search	O(1 + α)	O(n)
Delete	O(1 + α)	O(n)

Where α = n/m is the load factor. With a well-chosen m, operations approach O(1) amortized.

Build Instructions

1. Generate test data

cd Python
python generate_data.py

2. Compile and run benchmarks

# From the project root
javac Java/DS/*.java Java/DS/hash/*.java Java/DS/hashBenchmarkResult/*.java

# Run individual benchmarks
java -cp Java DS.hashBenchmarkResult.MainDataTester
java -cp Java DS.hashBenchmarkResult.Query1Tester
java -cp Java DS.hashBenchmarkResult.Query2Tester

Requires Java 8+ and Python 3.x.

Conclusion

This project demonstrates a complete hash table implementation with separate chaining, from the data structure itself to the hash function design and large-scale performance evaluation. The benchmarks clearly show the impact of load factor on operation times: denser chains lead to longer traversals, particularly for unsuccessful searches. Choosing an appropriate bucket count (keeping α manageable) is critical for practical hash table performance.

License

Educational project created for the Data Structures course at Shahid Beheshti University.