This community-built FAQ covers the “HashMaps vs. Linked Lists Runtime” exercise from the lesson “Asymptotic Notation: Python”.
Paths and Courses
This exercise can be found in the following Codecademy content:
FAQs on the exercise HashMaps vs. Linked Lists Runtime
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!
Which I believe is wrong.
Big O stands for worst case, which would be searching for a key that is not in the HashMap. In which case we end up in infinite while loop with the existing code, because:
possible_return_value != key
Always evaluates False because possible_return_value is a list and key is a string
possible_return_value is None
Always evaluates False because our HashMap is full and we have value for every index
possible_return_value[0] == key
Alwayse evaluates False because our key is not a valid key
in place of the infinite while loop we could use
for i in range(self.array_size - 1)
with this for loop in place our big O should look like this
I haven’t taken this course, but something just occured to me… Does it take the same amount of time to retrieve a item no matter which key we poll in the HashMap? If that is the case, then it would, I believe, be O(1).
HashMaps use collision when assisigning key-value pairs to a list, to avoid writting different keys to same index. When collision occurs the key-value pair is written at the next list index. Without collision we will have O(1) runtime:
1)hash the key
2)compress the hash to an index
3)grab the value at index from the list
With collision we have to iterate the list so it will be O(N):
1)hash the key
2)compress the hash to index
3) if key at index matches our key return value at index
4) else add 1 to collision counter and repeat (1-3)
Hi
Could anyone help me understand why this code doesn’t run successfully for exercise 3 on HashMaps vs. Linked Lists Runtime:
#Get Zachary’s Disease from a Linked List #Write Code here for Checkpoint 3
current = my_linked_list.get_head_node()
if current_value[0] == ‘Zachary’:
linked_list_zachary_disease = current_value[1]
else:
while current.get_next_node != None:
print(current.get_next_node() != None) #this is just here to show myself that this is None on the iteration where the code fails.
if current.get_next_node().get_value()[0] == ‘Zachary’:
linked_list_zachary_disease = current.get_next_node().get_value()[1]
current = current.get_next_node()
I thought the while loop would stop before I get the error:
Traceback (most recent call last):
File “script.py”, line 40, in
if current.get_next_node().get_value()[0] == ‘Zachary’:
AttributeError: ‘NoneType’ object has no attribute ‘get_value’
The HashMap of the module employs separate chaining, so big O for this HashMap’s search would not be infinite, it would be N.
However, a HashMap with O(N) isn’t much of a HashMap. That would be literally identical to employing just a Linked List. For a module comparing the runtime of a HashMap to the runtime of a Linked List, it wouldn’t be very effective if the HashMap’s hashing function boiled down to simply another Linked List.
The hashing function uses the encode() method. This will result in a very effective distribution of hash codes. On average, this will result in nearly always O(1), with some exceptions. Strictly speaking, you are correct that big O is intended to represent the worst case, but again, it’s not very meaningful to equate the runtime of a HashMap to a Linked List when the HashMap virtually never reaches the runtime of a Linked List, let alone come anywhere near it. For this purpose, we used the amortized time complexity instead, because clearly a well-designed HashMap is superior in runtime to a Linked List, and we still use big O notation despite no longer strictly representing the absolute worst case.
However, the course makes no mention of amortized time complexity, and selecting O(N) is both an honest and technically correct answer, despite being an impractical answer.
I originally did part 3 of the exercise by removing nodes in my_linked_list. Before changing that line, I was getting the following error:
Traceback (most recent call last):
File “script.py”, line 39, in
my_linked_list.remove_node(entry)
File “/home/ccuser/workspace/asymptotic-notation-python-hashmaps-linkedlist-runtime/linkedlist.py”, line 25, in remove_node
if current_node.get_value() == node_to_remove:
NameError: name ‘node_to_remove’ is not defined
the hashmap in this exercise does not employ separate chaining. it employs open addressing.
when a collision is found it finds a new index that is empty.
for it to employ separate chaining the hashmap would add the element to a linked list upon finding a collision
this will only be an infinite loop if the value passed into .retrieve() is not a valid key.
the logic “if possible_return_value[0]” relates to the list that is stored in possible return value [“Zachary”, “Sunburn sickness”]
so therefore possible return value[0] is “Zachary”
if the key entered into .retrieve() is “Zachary” the while loop will be exited.
you did find a bug in the code, however the question is asked for the runtime of the function given. which is still believe is O(N) because for the list to be O(1) the hashmap would have to retrieve the key the FIIRST time every time.
which isnt the case due to possible collisons.
if the key we are looking for collides the maximum possible times we would have O(N)
a well made hashmap should never collide the maximum of times however, but i dont believe our hashmap is made in this way
You’re absolutely correct! After reviewing the module again, this definitely employs open addressing. In fact, virtually nothing I said applies here. The hashing function’s encode() method is completely nullified because of the HashMap’s compressor() method. This construction results in a very ineffective distribution of hash codes, translating literally to a O(N), not O(1). Thank you for updating me. I’m not sure how I so thoroughly overlooked all of this.
There is a mistake on LinkedList.remove_node(), not sure if this part of the lesson.
def remove_node(self, value_to_remove):
current_node = self.head_node
if current_node.get_value() == node_to_remove: <------ should be "value_to_remove"
Thanks @code3482255522 for your perseverance and @mdcoulson for your clear explanations. I was also confused as to why the runtime for the hashmap was not N. Makes more sense to me now as they wanted to compare a linked list solution to a hash map solution and although the amortized runtime doesn’t apply fully here I enjoyed reading up about it and understand more now
For inserting, the worst case in a hash map is that every single input after the first produces a collision.
For retrieving, the worst case is that every single input produced a collision, the array is full, and the item you’re retrieving is the last one to be found.
That produces a Big-O (worst case) runtime of O(N), not O(1).
If all entries created the same “hash” value (unlikely, but possibly), then it will have to make N comparisons at worst, until it reaches the correct ‘key’.
) below.
) to up-vote the contribution!