educative.io

HashTable Constructor is updated in this section, please mention that

Courses
,
#1

Its a code build up probably, though not mentioned in the text clearly.
HashTable constructor definition is updated here and gives more clarity into bucket concept, however its neither mentioned in text content or highlighted in code section(as maintained for any new code added).

Course: https://www.educative.io/collection/5642554087309312/5646276079124480
Lesson: https://www.educative.io/collection/page/5642554087309312/5646276079124480/5640425327034368

#2

Hi @Chetan_Deshmukh !!

  1. In Hash Tables, “buckets” are essentially individual containers within the table that store key-value pairs. Each bucket corresponds to a specific index in the Hash Table’s underlying array. Buckets play a crucial role in handling collisions, which occur when multiple keys hash to the same index. Instead of overwriting the existing key-value pair, the new pair is stored in the same bucket, creating a linked list-like structure.
    Let’s take a look at how the concept of buckets is implemented in the provided code examples.
  • Insertion in Table:
#include "Hash.h"

int main() {

    HashTable ht(3);    // making three buckets
    ht.insert("London",2);
    ht.insert("London",10);
    ht.insert("New York",15);
    ht.insert("Tokyo",7);
    ht.insert("Bangkok",2);
    ht.insert("Beijing",6);
    ht.insert("Islamabad",9);
    ht.display();
}

In this example, the HashTable constructor takes a parameter that defines the number of initial buckets. As you insert key-value pairs, the Hash Table hashes the key and determines the index (bucket) where the pair should be stored. If multiple pairs hash to the same index, they are stored in the same bucket, creating a chain.

  • Resizing in a Hash Table:
#include "Hash.h"

int main() {

    HashTable ht(4);
    ht.insert("London",2);
    ht.insert("London",10);
    ht.insert("New York",15);
    ht.insert("Tokyo",7);
    ht.insert("Bangkok",2);
    ht.display();
  
    ht.resize();   // increase slots to 8
    ht.insert("Beijing",6);
    ht.insert("Islamabad",9);
    ht.insert("New Delhi",17);
    ht.insert("Moscow",12);
    ht.insert("Amsterdam",5);
    ht.insert("Paris",13);
    ht.display();
}

The resize operation increases the number of buckets, effectively allowing for more efficient handling of collisions. This is important as the number of elements increases, as it helps distribute the key-value pairs more evenly across buckets, reducing the likelihood of long chains and improving search performance.

  • Search in Hash Table:
#include "Hash.h"

int main() {

    HashTable ht(4);
    ht.insert("London",2);
    ht.insert("London",10);
    ht.insert("New York",15);
    ht.insert("Tokyo",7);
    ht.insert("Bangkok",2);
    ht.insert("Beijing",6);
    ht.insert("Islamabad",9);
  
    cout << ht.search("London") << endl;
    cout << ht.search("Moscow") << endl;
    cout << ht.search("Islamabad") << endl;   
}

When searching for a key, the Hash Table hashes the key to find the appropriate bucket and then traverses the chain (if present) within that bucket to locate the desired key-value pair.

  • Deletion in Table:
#include "Hash.h"

int main() {

    HashTable ht(2);
    ht.insert("London",2);
    ht.insert("London",10);
    ht.insert("New York",15);
    ht.insert("Tokyo",7);
    ht.insert("Bangkok",2);
    ht.insert("Beijing",6);
    ht.insert("Islamabad",9);
    
    ht.display();
    ht.Delete("London");
    ht.display();
    ht.Delete("Moscow");
    ht.display();
    ht.Delete("Islamabad");
    ht.display();
  
}

When deleting a key, the Hash Table finds the corresponding bucket and then searches the chain within that bucket to locate and remove the key-value pair.

Remember that the size and distribution of buckets can greatly impact the efficiency of Hash Table operations, and resizing is an important mechanism to maintain performance as the Hash Table grows.

I hope this explanation helps clarify the concept of buckets and how it’s integrated into the code examples. If you have any further questions or need additional clarification, please don’t hesitate to ask.
Happy Learning :blush: