Hashing Activity

Objective

By the end of this activity, students will:

  1. Understand how hashing and linear probing work.
  2. Implement a basic hash table with a bucket size of 5.
  3. Store and retrieve string-to-string mappings in the hash table.

Materials Needed

  1. Laptops with C++ compiler set up.
  2. Access to an IDE or text editor.
  3. Handouts/whiteboard to explain hashing and linear probing concepts.

Step-by-Step Activity

Step 1: Explain the Concepts (10 minutes)

  • Hash Function: A function that maps strings to an integer index in the hash table.
  • Bucket Size: The fixed size of the hash table (e.g., 5 in this activity).
  • Linear Probing: A collision resolution technique where, if a bucket is occupied, the algorithm checks the next available slot.

Illustrate this on the board with examples:

  1. Hash function formula: hash = sum of ASCII values of characters % bucket_size.
  2. Linear probing for collision: Keep moving to the next index until an empty slot is found.

Step 2: Set Up the Hash Table Class Structure (15 minutes)

Ask students to create a class with the following structure:

#include <iostream>
#include <string>
#include <vector>
#include <utility> // For std::pair

class HashTable {
private:
    std::vector<std::pair<std::string, std::string>> table; // Stores key-value pairs
    int bucketSize;

    int hashFunction(const std::string &key) {
        int hash = 0;
        for (char c : key) {
            hash += c; // Sum of ASCII values
        }
        return hash % bucketSize;
    }

public:
    HashTable(int size) : bucketSize(size) {
        table.resize(size, {"", ""}); // Initialize table with empty strings
    }

    void insert(const std::string &key, const std::string &value);
    std::string search(const std::string &key);
    void display();
};

Step 3: Implement the Insert Function (20 minutes)

Guide students to implement the insert function with linear probing:

void HashTable::insert(const std::string &key, const std::string &value) {
    int index = hashFunction(key);
    int originalIndex = index;

    while (!table[index].first.empty() && table[index].first != key) {
        index = (index + 1) % bucketSize; // Linear probing
        if (index == originalIndex) {
            std::cerr << "Hash table is full!" << std::endl;
            return;
        }
    }
    table[index] = {key, value}; // Insert key-value pair
}

Step 4: Implement the Search Function (20 minutes)

Now implement the search function:

std::string HashTable::search(const std::string &key) {
    int index = hashFunction(key);
    int originalIndex = index;

    while (!table[index].first.empty()) {
        if (table[index].first == key) {
            return table[index].second; // Return the value
        }
        index = (index + 1) % bucketSize; // Linear probing
        if (index == originalIndex) {
            break;
        }
    }
    return "Key not found!";
}

Step 5: Implement the Display Function (10 minutes)

Ask students to add a display function for debugging and visualization:

void HashTable::display() {
    for (int i = 0; i < bucketSize; ++i) {
        if (!table[i].first.empty()) {
            std::cout << i << ": " << table[i].first << " -> " << table[i].second << std::endl;
        } else {
            std::cout << i << ": [Empty]" << std::endl;
        }
    }
}

Step 6: Write the Main Program (20 minutes)

Guide students to test their implementation in main:

int main() {
    HashTable hashTable(5);

    hashTable.insert("apple", "fruit");
    hashTable.insert("table", "furniture");
    hashTable.insert("car", "vehicle");
    hashTable.insert("dog", "animal");
    hashTable.insert("cat", "animal");

    hashTable.display();

    std::cout << "Searching for 'dog': " << hashTable.search("dog") << std::endl;
    std::cout << "Searching for 'book': " << hashTable.search("book") << std::endl;

    return 0;
}

Step 7: Run and Debug (15 minutes)

  • Students should compile and run their program.
  • Test various inputs to observe how linear probing resolves collisions.
  • Debug any issues, like infinite loops or incorrect outputs.

Step 8: Discuss and Reflect (10 minutes)

  • How effective is the hash function?
  • What happens when the hash table is full?
  • What are alternative collision resolution techniques?

This step-by-step activity allows students to incrementally build a working hash table while understanding the underlying principles.

Activity Sheet: Implementing a Hash Table with Linear Probing in C++

Objective

By the end of this activity, you will:

  1. Understand how hashing and linear probing work.
  2. Create a hash table with a bucket size of 5.
  3. Implement functions to store and retrieve string-to-string mappings.

Instructions

1. Learn the Basics of Hashing and Linear Probing

  1. Hash Function: A function that converts a string to an integer index in the hash table.
    • Formula: hash = sum of ASCII values of characters % bucket_size
  2. Linear Probing: A method to resolve collisions. If a bucket is occupied, move to the next bucket until an empty slot is found.
    • Example: If bucket 2 is full, check bucket 3, then 4, and so on.

2. Create the Hash Table Class

  1. Open your C++ IDE or text editor and create a new file.
  2. Copy and paste the following starter code:
#include <iostream>
#include <string>
#include <vector>
#include <utility> // For std::pair

class HashTable {
private:
    std::vector<std::pair<std::string, std::string>> table; // Stores key-value pairs
    int bucketSize;

    int hashFunction(const std::string &key) {
        int hash = 0;
        for (char c : key) {
            hash += c; // Sum of ASCII values
        }
        return hash % bucketSize;
    }

public:
    HashTable(int size) : bucketSize(size) {
        table.resize(size, {"", ""}); // Initialize table with empty strings
    }

    void insert(const std::string &key, const std::string &value);
    std::string search(const std::string &key);
    void display();
};

3. Implement the insert Function

  1. Add the following code to the insert method in the HashTable class:
void HashTable::insert(const std::string &key, const std::string &value) {
    int index = hashFunction(key);
    int originalIndex = index;

    while (!table[index].first.empty() && table[index].first != key) {
        index = (index + 1) % bucketSize; // Linear probing
        if (index == originalIndex) {
            std::cerr << "Hash table is full!" << std::endl;
            return;
        }
    }
    table[index] = {key, value}; // Insert key-value pair
}
  1. Save your file and ensure there are no syntax errors.

4. Implement the search Function

  1. Add the following code to the search method:
std::string HashTable::search(const std::string &key) {
    int index = hashFunction(key);
    int originalIndex = index;

    while (!table[index].first.empty()) {
        if (table[index].first == key) {
            return table[index].second; // Return the value
        }
        index = (index + 1) % bucketSize; // Linear probing
        if (index == originalIndex) {
            break;
        }
    }
    return "Key not found!";
}
  1. Save your file.

5. Implement the display Function

  1. Add the following code to the display method:
void HashTable::display() {
    for (int i = 0; i < bucketSize; ++i) {
        if (!table[i].first.empty()) {
            std::cout << i << ": " << table[i].first << " -> " << table[i].second << std::endl;
        } else {
            std::cout << i << ": [Empty]" << std::endl;
        }
    }
}
  1. Save your file.

6. Test the Hash Table

  1. Write the following code in your main function:
int main() {
    HashTable hashTable(5);

    hashTable.insert("apple", "fruit");
    hashTable.insert("table", "furniture");
    hashTable.insert("car", "vehicle");
    hashTable.insert("dog", "animal");
    hashTable.insert("cat", "animal");

    hashTable.display();

    std::cout << "Searching for 'dog': " << hashTable.search("dog") << std::endl;
    std::cout << "Searching for 'book': " << hashTable.search("book") << std::endl;

    return 0;
}
  1. Save and compile the program.
  2. Run the program and observe the output.

7. Answer the Following Questions

  1. What happens when the table is full and you try to insert another key?
  2. How does the hash function affect the distribution of keys in the table?
  3. Why is linear probing used to resolve collisions?
Scroll to Top