educative.io

Bucket concept is not clearly depicted, code has typos

Courses
,
#1

While reading this section, one doubt definitely comes is whether

  • Buckets in HashTable are arrays which hold one KV pair per index(hash value) and then buckets are chained to maintain multiple KV pairs per index !?
  • OR (unlikely) Buckets are logical (horizontal) groupings of KV pairs across arrays, for a given index.

Also Ptr to bucket given here is

HashEntry * bucket;

Which further confuses, its actually as below, as mentioned in next page itself.

HashEntry ** bucket;

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

#2

Hello @Chetan_Deshmukh,
Your doubts are well-placed, as understanding hash tables and their internal structures can be complex. Here’s a breakdown to address your concerns:

  1. Buckets in HashTable:
  • Buckets in a hash table are arrays. Each bucket holds one key-value pair per index (based on the hash value of the key).
  • Chaining is a technique used to handle collisions (when two keys have the same hash value) by allowing multiple key-value pairs to exist within the same bucket. These pairs are organized as a linked list, ensuring efficient storage and retrieval.
  1. Ptr to Bucket:
  • The pointer HashEntry * bucket; indicates that bucket is a pointer to a HashEntry object (or possibly the first element of a linked list) representing a bucket in the hash table.
  • The pointer HashEntry ** bucket; is used when dealing with an array of pointers. Each pointer points to a bucket (possibly containing a linked list of key-value pairs). This pointer-to-pointer setup is useful for dynamic memory allocation and managing the structure.