Page Comparison

...

#include <iostream>
#include <vector>

template <typename K, typename V>
class HashTable {
publicprivate:
    int staticcapacity;
 const int TABLE_SIZE = 100 std::vector<int> keys;
    std::vector<std::pair<K, V>> table;vector<int> values;

    int HashTablehash(int key) {
        tablereturn = std::vector<std::pair<K, V>>(TABLE_SIZE)key % capacity;
    }

public:
   int hashFunctionHashTable(Kint keycapacity)
{         std::hash<K> hashFunction;
        int index = hashFunction(key) % TABLE_SIZE;
        return index;
    } capacity(capacity), keys(capacity, -1), values(capacity, -1) {} // Initialize keys and values with -1, indicating empty slots

    void putinsert(Kint key, Vint value) {
        int index = hashFunctionhash(key);
        while (tablekeys[index].first != K()-1 && tablekeys[index].first != key) {
            index = (index + 1) % TABLE_SIZE;
 capacity; // Linear probing step
        }
        tablekeys[index] = std::make_pair(key, value)key;
        values[index] = value;
    }

    Vbool getfind(Kint key, int &value) {
        int index = hashFunctionhash(key);
        while (tablekeys[index].first != K()-1) {
            if (tablekeys[index].first == key) {
                returnvalue = tablevalues[index].second;
                return true;
            }
            index = (index + 1) % TABLE_SIZE;
  capacity; // Linear probing step
     }   }
     throw std::out_of_range("Key not found")   return false;
    }

    boolvoid containsKeyremove(Kint key) {
        int index = hashFunctionhash(key);
        while (tablekeys[index].first != K(-1)) {
            if (tablekeys[index].first == key) {
                keys[index] return= true-1;
            }    values[index] = -1;
      index  = (index + 1) % TABLE_SIZE;   return;
     }       }
 return false;     }     index void= remove(Kindex + key1) {
  % capacity; // Linear probing step
     int index = hashFunction(key);}
    }

  while (table[index].first != K() void print() {
        for (int i = if (table[index].first == key0; i < capacity; i++) {
            std::cout << "[" << i << "]: " table<< keys[indexi].first = K();
     << " -> " << values[i] << "\n";
        }
   return }
};

int main() {
    HashTable hashTable(10);

 }   hashTable.insert(15, 150);
    hashTable.insert(25, 250);
  index = (index + 1) % TABLE_SIZE;hashTable.insert(35, 350);

    hashTable.print();

    int value;
    }
if (hashTable.find(25, value)) {
       throw std::out_of_range(cout << "Key not25 found") with value: " << value << "\n";
    } };else {
 int main() {     HashTable<stdstd::string, int> myHashTablecout << "Key 25 not found\n";
    myHashTable.put("one", 1);}

    hashTable.remove(25);

    myHashTablehashTable.put("two", 2print();

   myHashTable.put("three", 3); if (hashTable.find(25, value)) {
        std::cout << myHashTable.get("two") << std::endl;
    myHashTable.remove("one")"Key 25 found with value: " << value << "\n";
    } else {
        std::cout << myHashTable.containsKey("one") << std::endl;"Key 25 not found\n";
    }

    return 0;
}

Output:

2
0

In this example, we define a HashTable class to represent the hash table, which has a vector of key-value pairs to store its elements. We provide member functions to insert elements into the hash table, to retrieve elements from the hash table, to check if the hash table contains a given key, and to remove elements from the hash table.

In the main function, we create a HashTable object, insert some elements into the hash table, retrieve an element from the hash table, remove an element from the hash table, and check if the hash table contains a keyHere, the linear probing is achieved by incrementing the index by 1 ((index + 1) % capacity) each time a collision is detected until an empty slot or a slot with the same key is found.

This approach makes sure that the table gets filled efficiently, but it can lead to clustering, where groups of adjacent slots are filled, slowing down the search, insert, and delete operations. Various probing sequences and rehashing techniques can mitigate these issues.

Class Definition

Private Members

• capacity: The size of the hash table.

• keys: A vector of integers that stores the keys.

• values: A vector of integers that stores the corresponding values.

• hash(int key): A simple hash function that returns the remainder of the key divided by the capacity.

Public Members

• Constructor: Initializes the capacity and sets all keys and values to -1, indicating empty slots.

• insert(int key, int value): Inserts a key-value pair into the hash table.

  1. It calculates the hash index using the hash function.

  2. It then checks if the slot at the index is occupied (if keys[index] != -1).

  3. If the slot is occupied, it performs linear probing by incrementing the index by one in a loop (index = (index + 1) % capacity) until an empty slot or a slot with the same key is found.

  4. It then inserts the key and value into the slots.

• find(int key, int &value): Searches for a key in the hash table.

  1. It calculates the hash index using the hash function.

  2. It then searches for the key using linear probing, incrementing the index in a loop until the key is found or an empty slot (keys[index] == -1) is reached.

  3. If the key is found, it returns true and sets the corresponding value. If not found, it returns false.

• remove(int key): Removes a key-value pair from the hash table.

  1. It calculates the hash index using the hash function.

  2. It then searches for the key using linear probing, as in the find method.

  3. If the key is found, it sets the key and value at that index to -1, indicating an empty slot.

• print(): Prints the contents of the hash table, showing both keys and values.

main Function

In the main function, a HashTable object is created with a capacity of 10. Three key-value pairs are inserted, and the contents of the hash table are printed.

The code then demonstrates finding a key (25) and prints whether it's found along with its value. Afterward, the code removes the key (25) and prints the updated hash table contents, and again checks for the key.

This code implements a hash table with linear probing in C++. The linear probing resolves collisions by searching linearly in the array for the next empty slot. This implementation uses two parallel vectors to represent the keys and values, respectively, and employs basic operations like insert, find, remove, and print.