Currency Exchange

Overview

This project implements a custom hash table in C++ designed to store and manage Currency objects—specifically a subclass called Krone. The primary goal is to explore the mechanics of hashing, collision resolution, and performance analysis in a controlled environment using object-oriented programming. The hash table uses a custom hash function based on the values of notes and coins in the Currency object. To handle collisions, it employs quadratic probing, which incrementally checks new indices using a squared offset to reduce clustering.

Features

• Implemented a custom hash table in C++ for storing Currency objects
• Used a custom hash function: (notes * m + coins * n) % size with m = 2 and n = 3
• Handled collisions using quadratic probing: (index + i*i) % size
• Supported insertion by hashing Currency objects and probing until an empty slot is found
• Included search functionality using the same hash and probing logic
• Tracked metrics including number of items, total collisions, and load factor
• Interfaced with a subclass called Krone that extends the Currency class

Demo

Here's a quick demo of heap allocator in action:

Sample Code

void hash(Currency* current) {
  int hash_value = hashValue(current);
  int i = 0;
  while (table[hash_value].isEqual(nullptr)) {
    hash_value = quadraticProbe(hash_value, i);
    i++;
    totalCollision++;
  }
  numberOfItems++;
  //table[hash_value] = new Krone(current);
  table[hash_value].setCoins(current->getCoins());
  table[hash_value].setNotes(current->getNotes());
}
            

Explore the Code

Check out the full project on GitHub, or download it directly.

What I Learned

Through this project, I gained a deeper understanding of how hash tables function at a low level, especially the importance of crafting effective hash functions and handling collisions efficiently. Implementing quadratic probing helped me explore different strategies for resolving collisions and managing clustering. I also learned how to design data structures that interact with custom objects, which improved my grasp of object-oriented programming concepts like inheritance and polymorphism. Additionally, tracking performance metrics like load factor and collision count gave me insight into evaluating the efficiency and scalability of data structures in real-world scenarios.