FAQs on the exercise Open Addressing in the Getter
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!
In the exercise “Open Adressing in the Getter” (topic Hash functions), shouldn’t the Getter’s while condition test for the key instead of the whole array element (bold in code)?
I.e. I would replace "while (possible_return_value != key): " for "while (possible_return_value[0] != key): "
Appreciate any help on understading this.
Kind regards
Code as given by solution:
def retrieve(self, key):
array_index = self.compressor(self.hash(key))
possible_return_value = self.array[array_index]
if possible_return_value is None:
return None
if possible_return_value[0] == key:
return possible_return_value[1]
retrieval_collisions = 1
while (**possible_return_value != key**):
new_hash_code = self.hash(key, retrieval_collisions)
retrieving_array_index = self.compressor(new_hash_code)
possible_return_value = self.array[retrieving_array_index]
if possible_return_value is None:
return None
if possible_return_value[0] == key:
return possible_return_value[1]
number_collisions += 1
return
I was also curious about this, I tried running the script with both expressions and they worked…
but I’m still confused as how the method was able to compare the key since there is more than 1 element inside the possible_return_value.
Also if you look at the solution code, when you are supposed to increment retrieval_code += 1 they are actually trying to increase “num_collisions +=1” as in the .assign( ) I already reported it but just in case they dont fix it I will post it in here in case someone doesnt notices it.
I’m doing the hash maps exercises in opn adressing in the getter and i do not understand what does is mean if its none
“”" possible_return_value is None:
After some debugging in Visual Code, I see that the while loop keeps going and incrementing the retrieval_collisions indefinitely, which seems normal given the code and instructions.
We should add a condition where the while loop stops, as it will never have possible_return_value[0] != key evaluate as False so it can end the loop.
In our current setting, I think we can just iterate in a range the size of the array, as our probing method is adding “+1” for every collision.
But I’m thinking there could be more complex probing methods, so the question is:
How many times should we have our method probe until it returns None? It somehow has to be the entire array.
I think in this case we’d only enter the while loop if there is a collision. And if there’s a collision, we’ll either find an empty spot (so the item isn’t in the array and the loop exits with None) or we find the item (and the loop exits and returns with the value). But either way the loop will halt at some point.
I think the solution was written to get a natural learning progression of dealing with the case where the “key” at the index doesn’t match the key we are looking for, and then to think about how to keep searching indexes until we get to the right key. Unfortunately this can result in some fairly ugly repetitive code. If you then refactor to have "DRY"er code some of the tests fail unfortunately. i.e. below fails as retrieval_collisions != 1 at start of test run.
def retrieve(self, key):
retrieval_collisions = 0
found_index = None
while found_index is None:
new_hash_code = self.hash(key, retrieval_collisions)
retrieving_array_index = self.compressor(new_hash_code)
possible_return_value = self.array[retrieving_array_index]
if (possible_return_value == None
or possible_return_value[0] == key):
found_index = retrieving_array_index
else:
retrieval_collisions += 1
retrieved = self.array[found_index]
if retrieved:
return retrieved[1]
else:
return None
Is the code throwing an error, or just failing the SCT? Probably the latter. Without going to the lesson, this isn’t a lot to go on, but I do have an observation regarding the retrieval_collisions variable. What is the point of initializing it, and updating it, but not using it? What’s it’s purpose? It does have one.
Sorry - new to posting on the forum so I should have been clearer. Not a question with how to do the lesson, but just giving some feedback that the way the lesson is taught as introduces some very non DRY code, which is okay as the point of the lesson is still valid - but it would be nice if the tests enabled valid refactored solutions that can pass without failing.
The retrieval_collisions var btw is just part of the lesson - it is used in the code sample as an arg in the self.hash() call to add to the base hash value of the key.
Apologies. When I first read your post, it was on my phone kinda late at night, and I missed where you include retrieval_collisions in your call to the hash method. Just looking at it, your code looks like it should work as expected. In cases like this where the expected solution seems less efficient than what you’d like to do, you can first do what is expected in order to pass the steps, and once you’ve passed everything, go back and refactor your code. At that point the SCT won’t run, and won’t give you messages like you noted above.
) below.
) to up-vote the contribution!