This community-built FAQ covers the “Separate Chaining” exercise from the lesson “Hash Maps: Conceptual”.
Paths and Courses
This exercise can be found in the following Codecademy content:
Computer Science
Complex Data Structures
FAQs on the exercise Separate Chaining
There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (
) below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
Agree with a comment or answer? Like (
) to up-vote the contribution!
Need broader help or resources? Head here.
Looking for motivation to keep learning? Join our wider discussions.
Learn more about how to use this guide.
Found a bug? Report it!
Have a question about your account or billing? Reach out to our customer support team!
None of the above? Find out where to ask other questions here!
In the lesson, it is asked: “What would the benefits of using a tree at each index?”
Unless I’m mistaken, in the course so far no “tree” has been mentioned. Is this a separate data type or something else? Maybe the lesson should be updated to reflect what a tree is.
10 Likes
Hi @byteninja93187,
Yeah, you’ll learn about trees right after you complete the material on hash maps. Trees are more efficient for performing searches than linked lists.
Following is an illustration from the Codecademy introductory material on trees:
If you’re looking for a number in this tree, say 31, you start at the top (the root node). At each node, compare the number that you’re looking for with the number at the current node. Then:
- If the number you’re looking for is the same as the one at the current node, you found it.
- If the number you’re looking for is smaller than the one at the current node, follow the left branch.
- If the number you’re looking for is greater than the one at the current node, follow the right branch.
- If you’ve performed the comparison, and the branch you want to follow is not there, then the number is not in the tree.
For a hash map, each index (or bucket) would have a tree instead of a linked list. You would be storing keys and values in the tree. The comparisons you make along the way would involve the keys. Note that as you follow a branch in the tree, you are eliminating all the nodes along the branch that was not followed, which imparts efficiency to the search. At indexes where there were only a few nodes stored, the gain in efficiency wouldn’t be very much, but if for some reason lots of keys mapped to the same index, the gain could be significant.
Edited on June 16, 2019 to note that there would be a tree instead of a linked list at each index
6 Likes
It will probably be answered by the forthcoming lessons, but I think this article doesn’t really explain how you are supposed to look for the value corresponding to a certain key in the hash map.
With the provided script, both “lapis” and “lap” map to position “2” in the hash map, so their values are added to the linked list. Like so:
Now, say that I want to retrieve the value for “lap”… The hash function will return “2”, so, that’s where I would go to search for the value, but I find a linked list with two values: How do I know which one is for “lapis” and which one for “lap”?
4 Likes
Yes, nevermind, the next lesson covered it, hehe.
1 Like
Seperate chaining will also accept two keys that are same, which is not a property of a map, as mentioned in previous exercises. How would it tackle this?
