Algorithms & Data Structures — Assignment 3 (AITU)

Overview

Implementations of a hash table with separate chaining and a binary search tree (BST), both generic. Main stress-tests the hash table with 10,000 randomly generated strings and prints bucket distribution statistics, then exercises the BST with 10 random inserts and in-order iteration.

What it implements

• MyHashTable<K, V> — separate-chaining hash table with dynamic resizing.
  • Hash function: (key.hashCode() % M + M) % M where M starts at 11.
  • Resizes to the next prime above 2*M when the load factor exceeds 0.7.
  • Operations: put, get, remove, contains, getKey (reverse lookup), getBucketSizes for distribution analysis.
  • Inner HashNode tracks chain length for diagnostics.
• BST<K extends Comparable<K>, V> — recursive binary search tree.
  • put / get / delete (handles 0, 1, and 2-child cases).
  • iterator() returns key-value pairs via in-order traversal (sorted ascending by key).
  • Inner KeyValuePair exposes getKey() / getValue() for safe external access.
• TestMyHashTable — custom key class with a polynomial rolling hash using two different bases and moduli (double hashing) to reduce collisions, demonstrating hashCode() contract implementation.
• Bucket distribution report — after 10,000 inserts: used buckets, average chain length, above-average buckets, max chain length.

Project structure

src/
├── Main.java                          # Stress test + statistics output
├── hashtable/
│   └── MyHashTable.java               # Separate-chaining hash table
├── test_hashtable/
│   └── TestMyHashTable.java           # Custom key class with double-hash hashCode
└── tree/
    └── BST.java                       # Binary search tree with in-order iterator

How to run

# From the project root (src/ on the classpath)
javac -d out src/hashtable/MyHashTable.java src/test_hashtable/TestMyHashTable.java src/tree/BST.java src/Main.java
java -cp out Main

Expected output: bucket sizes for the hash table, distribution stats, then BST key-value pairs in sorted order.

---

Adil Ormanov — GitHub