Versions Compared

Old Version 1

changes.mady.by.user Computer Science Department

Saved on

compared with

New Version 2

changes.mady.by.user Computer Science Department

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

Hash table chaining is a technique used to handle collisions in a hash table. When a hash function maps two or more keys to the same index in the array, a collision occurs. In chaining, each index in the array contains a linked list of nodes, where each node contains a key-value pair. When a new element is inserted into the hash table and a collision occurs, the new node is appended to the linked list at the corresponding index.Here is an example implementation

Sure! Hash table chaining is a technique used to handle collisions in a hash table. When two keys hash to the same index, they are placed into a linked list at that index.

Here's a basic example of a hash table using with chaining in C++. This example demonstrates a very simple hash function, and the chaining is implemented using the Standard Library's linked list (std::list).

Code Block
languagecpp
#include <iostream>
#include <vector><list>

template <typename K, typename V>
class HashNode#include <vector>

class HashTable {
publicprivate:
    Kint keycapacity; // Size of the Vhash value;table
    HashNode* nextstd::vector<std::list<int>> table; // The hash   HashNode(K keytable itself, Vimplemented value)as {a vector of lists

    this->key =int hash(int key;) {
       this->value =return value;key % capacity; // Simple hash function that returns this->nextthe =remainder nullptr;of key divided by the }capacity
};  template <typename K,}
typename
V>
class HashTable {
public:
    static const HashTable(int TABLE_SIZE = 100;
    std::vector<HashNode<K, V>*> table;

    HashTable(capacity) : capacity(capacity) {
        table = std::vector<HashNode<K, V>*>(TABLE_SIZE, nullptr.resize(capacity);
    }

    void ~HashTableinsert(int key) {

       for (int iindex = 0; i < TABLE_SIZE; i++) {
      hash(key);
     HashNode<K, V>* node = table[i];
            while (node) {
                HashNode<K, V>* nextNode = node->next;
          index].push_back(key); // Append the key to the list at the hashed index
    }
delete
node;    void remove(int key) {
        int nodeindex = nextNode;
            }
   hash(key);
        table[i] = nullptr;
        }
    }

    int hashFunction(K key) {
        std::hash<K> hashFunction;
        int index = hashFunction(key) % TABLE_SIZE;
        return index;index].remove(key); // Remove the key from the list at the hashed index
    }

    voidbool putfind(Kint key, V value) {
        int index = hashFunctionhash(key);
        for HashNode<K, V>* node =(const int& element : table[index];
        while (node) {
            if (node->keyelement == key) {
                node->value = valuereturn true; // If the key is found in the list at the hashed index, return true
 return;           }
 }       }
     node = node->next; return false; // If the key is not }found, return false
    }
 HashNode<K,
V>* newNode = new HashNode<K,void V>print(key, value); {
       newNode->next = table[index];
        table[index] = newNode;for (int i = 0; i < capacity; i++) {
       }     std::cout V get(K key) {
  << "[" << i << "]: ";
     int index = hashFunction(key);    for (const int&   HashNode<K, V>* node =key : table[index];
        while (nodei]) {
            if (node->key == key) {
                return node->value std::cout << key << " -> ";
            }
            node = node->nextstd::cout << "NULL\n";
        }
    }
};

 throw std::out_of_range("Key not found");
int main() {
   } 
    bool containsKey(K key) {HashTable hashTable(10);

    hashTable.insert(15);
   int index = hashFunction(key hashTable.insert(25);
        HashNode<K, V>* node = table[index]hashTable.insert(35);

       while (node) {hashTable.print();

           if (node->key == key(hashTable.find(25)) {
        std::cout << "Key      return true;
       25 found\n";
    } else {
        std::cout << node"Key = node->next;
        }
        return false25 not found\n";
    }

    void hashTable.remove(K key25);
{
    hashTable.print();

  int index = hashFunction(key);if (hashTable.find(25)) {
        HashNode<K, V>* node = table[index]std::cout << "Key 25 found\n";
    } else {
 HashNode<K, V>* prevNode = nullptr;   std::cout << "Key 25 not found\n";
while (node) {  }

    return 0;
}

This will create a hash table with a capacity of 10, and all the keys are linked using a std::list at their hashed index. It inserts three keys and then demonstrates finding and removing one of them.

Note: This is a simple and naive implementation for demonstration purposes. In practice, you would probably want to implement more robust hashing and handle other edge cases.

In the provided example, collisions are handled using the chaining technique, which is implemented with std::list. Let's break it down step by step.

  1. Initial Setup:
    The hash table is an array (or std::vector in this case) of fixed size (capacity). Each slot in the array is a linked list (std::list).

    Code Block
    languagecpp
    std::vector<std::list<int>>

...

  1. table;

  2. Hash Function:
    We have a simple hash function that takes an integer key and produces an index in the hash table.

    Code Block
    languagecpp
    int hash(int key) {
    return key % capacity;
}

  3. Insertion:
    To insert a new key:

    • The key is hashed to determine its position in the array.

    • If the slot (index) in the array is empty (no collision), a new key is added to the linked list at that slot.

    • If the slot is not empty (collision), the key is simply appended to the existing linked list at that slot.

    Code Block
    languagecpp
    void

...

  1. insert(int key) {

...

  1. int index = hash(key);
    table[index]

...

  1. .push_back(key);
}

    Notice that even if two or more keys hash to the same index (collision), they can all co-exist in the linked list at that index.

  2. Searching:
    To search for a key:

    • Hash the key to find its potential position.

    • Traverse the linked list at that position to see if the key exists.

    Code Block
    languagecpp
    bool find(int key) {
    int index

...

  1. = hash(key);
    for (const int& element : table[index]) {

...

  1.    if

...

  1. (element == key) {

...

  1.

...

  1. return

...

  1. true;
        }
    }

...

  1.  return false;
}

  2. Deletion:
    To delete a key:

    • Hash the key to find its position.

    • Remove the key from the linked list at that position.

    Code Block
    languagecpp
    void remove(int key) {

...

  1. int index = hash(key);

...

  1. table[index].remove(key);
}

In summary, when a collision happens, the chaining technique uses a linked list to store all the keys that collide at the same slot. This approach ensures that no keys are rejected due to collisions, but it may result in longer search times if one slot accumulates too many keys.