educative.io

Educative

HashMap design don't need 3 level of list nesting

Hello,

Why is Bucket a List<List> when it can simply be just a List and Entry is just a class with key, and value as members? So the HashMap can simply be List<List> instead of having three level of nesting listing like List<<List<List>>? I believe we only need two level of list nesting. Please clarify.


Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Design HashMap - Grokking Coding Interview Patterns in Java

Hello @Wing_Tang

Thank you for bringing this up. You’re correct in observing that the code uses a nested structure of a List of Buckets, where each Bucket is a List of Entries. This is the correct and expected way to implement a hash map in this case.

Regarding the question about three level of nesting, It seems that there may have been a misunderstanding. In the code provided, there is only two levels of nesting, which is the List of Buckets, where each Bucket is a List of Entries.

Can you please clarify where you see the third level of nesting, so that I can help address any confusion or misunderstandings?

Happy Learning!

You are completely wrong. If you haven’t run the code yet in the final solution provided by the author, you should. The code creates 11 redundant buckets, each containing an entire hash table.

This is very confusing for a learner, except that almost every solution provided in Educative courses contain an error and then the authors usually refuse to acknowledge it. Not sure how you get away with that. You must be a man.

1 Like

Hello @Kate_Portalatin,

Thank you for your feedback on the provided hash map implementation. Upon reviewing the code and your concerns, it appears there’s been a misunderstanding regarding how the hash map and its buckets are initialized and function.

The intention behind the DesignHashMap class is to create a hash map with a specified number of buckets (keySpace) to manage key-value pairs. Each bucket is meant to handle collisions that occur when different keys hash to the same index.

However, after reading your reply, a critical point concerning the initialization of these buckets is found with Collections.nCopies(keySpace, new Bucket()). This approach, mistakenly initializes the ArrayList with references to the same Bucket instance across all indices, not separate instances as required for correct hash map operation. This error would lead to incorrect behavior, but not in the way of creating redundant entire hash tables within each bucket.

We are consistently working on updating this lesson to provide a much better understanding of hash maps. Thank you for letting us know about your concerns. Please feel free to share further suggestions and feedback. We’d be happy to help.