Hash Map with Chaining

A C++ implementation of a hash map that efficiently stores and manages large integers using chaining for collision resolution. The project includes memory optimization techniques and a radix sort implementation for sorting the stored values.

What It Does

• Stores 6-8 digit integers in a hash map with chaining
• Optimizes memory by storing keys and indices instead of full key-value pairs
• Implements radix sort for efficient sorting of stored values
• Provides comprehensive monitoring of hash map performance
• Supports insert, lookup, and delete operations

How It Works

The program reads integers from a file and stores them in a hash map where each key's value is 10 times the key. It uses chaining to handle collisions and implements memory optimization by storing indices instead of full values.

// Example of hash map structure
struct KeyValuePair {
    int key;
    int value;  // 10 * key
};

// Example of hash map node
struct Node {
    int key;
    int index;
    Node* next;
};

// Example of hash map operations
class HashMap {
    Node** buckets;
    int size;
    
    void insert(int key, int index) {
        int hash = key % size;
        Node* newNode = new Node{key, index, buckets[hash]};
        buckets[hash] = newNode;
    }
    
    // ... other operations
};

Technical Bits

• Implemented in C++ for performance
• Uses chaining for collision resolution
• Implements radix sort for efficient sorting
• Memory-optimized storage using indices
• File I/O for input and output operations

Features

1. Display All Pairs: Shows all key-value pairs (10 per line)
2. Sort and Output: Sorts pairs by key and outputs to file
3. Search Functionality: Finds keys and displays their locations
4. Hash Map Visualization: Shows the structure of the hash map
5. Performance Monitoring: Tracks longest chain and occupancy rate

Why I Built It

I wanted to explore efficient ways to store and manage large integers while optimizing memory usage. This project helped me understand hash map implementations, collision resolution strategies, and memory optimization techniques.

Future Ideas

• Implement different hash functions
• Add support for different data types
• Implement dynamic resizing
• Add more sorting algorithms
• Enhance visualization capabilities