Recall that the core algorithms have a gap which is searching for a key in a bucket (a bucket is a list of elements).

The Bucket Search Problem


Simple Case
When a bucket contains one element, the search is trivial:

  • We have converted key1 to index 5
  • We get the bucket at index 5
  • The bucket contains one value
  • We return the value
The Gap: Multiple Values
When a bucket multiple values, the search is more complex:

  • We have converted key2 to index 3
  • We get the bucket at index 3
  • The bucket contains multiple values
  • How do we find the value associated with key2?

We have a gap (question) we need to resolve

Solving the Bucket Search Problem


The Problem
We just discovered the problem where a bucket contained multiple values. It is unknown which value corresponds to a given key.
Recall the Collision
Let's recall how the collision occurred.

Two different keys produced the same hash index (3).

The two different values (note: with different keys) are added into the bucket.
The Solution
The solution is to store both the key and value in the table.

Rather than just plopping the value into the bucket we instead add the key and value together (in an Association or KeyValue object).

See more info on Association here...
The Problem Revisited
  • We have converted key2 to index 3
  • We get the bucket at index 3
  • The bucket contains multiple associations
  • Search for the association with a key matching the given key2
  • Return the value from the matching association or null if not found






























Data Structures And Algorithms (DSA) (Chapter 601 - Hash Table Concepts)










Chapter 601 - Hash Table Concepts Associations (For the Bucket Search Problem)

Index Intro Concept Design 1 Algorithms Concept Design 2 Advantages References

Chapter Top Search Site Contents