FAQ: Hash Maps: Python - Open Addressing in the Setter


#1

This community-built FAQ covers the “Open Addressing in the Setter” exercise from the lesson “Hash Maps: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Computer Science

Complex Data Structures

FAQs on the exercise Open Addressing in the Setter

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 (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 (reply) below!

Agree with a comment or answer? Like (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!


#2

Working on this lesson: https://www.codecademy.com/paths/computer-science/tracks/complex-data-structures/modules/cspath-hash-maps/lessons/hash-maps-implementation/exercises/open-addressing-setter

I wrote my code below, but got a Codecademy error. I looked at the solution and I was missing returns (which I don’t understand how that changes what the code does) and I used an else statement as well. It has something to do with the else statement and not returning, but I don’t know why. I also can’t figure out what in my code made Codecademy think assign didn’t have a self, key, value parameters?

 def assign(self, key, value):
    array_index = self.compressor(self.hash(key))
    current_array_value = self.array[array_index]

    if current_array_value is None:
      self.array[array_index] = [key, value]
      return

    if current_array_value[0] == key:
      self.array[array_index] = [key, value]
      return

    # current_array_value currently holds different key
    number_collisions = 1
    while current_array_value[0] != key:
      new_hash_code = self.hash(key, number_collisions)
      new_array_index = self.compressor(new_hash_code)
      current_array_value = self.array[new_array_index]
      if current_array_value == None:
        self.array[new_array_index] = [key, value]
      elif current_array_value == key:
        self.array[new_array_index] = [key, value]        
      else:
        number_collisions += 1

Does HashMap.assign() take self , key , and value as parameters?

The part that the solutions has that is different.

    number_collisions = 1
    while current_array_value[0] != key:
      new_hash_code = self.hash(key, number_collisions)
      new_array_index = self.compressor(new_hash_code)
      current_array_value = self.array[new_array_index]
      if current_array_value == None:
        self.array[new_array_index] = [key, value]
        return
      elif current_array_value == key:
        self.array[new_array_index] = [key, value]
        return
      
      number_collisions += 1
      return

#3

That’s a very poor test, I suppose they wanted to test for the parameters, and tested for what goes wrong if they’re not there. They should be testing the parameters directly which are very much accessible.
Obviously the issue is that there may be other reasons for TypeError - the error message only matches a subset of what is actually tested for.

try:
  h = HashMap(5)
except TypeError:
  fail_tests("Does `HashMap`'s constructor take a single argument?")

try:
  h.assign('ab', 'c')
  h.assign('ba', 'd')
except TypeError:
  fail_tests("Does `HashMap.assign()` take `self`, `key`, and `value` as parameters?")

#4

I don’t quiet understand what you are saying. Can you rephrase it? I messed with it, and it has to do with the difference between the very last bit:

What I did:

 else:
        number_collisions += 1

and Solutions did:

number_collisions += 1
      return

#5

I showed you the test code associated with the error message you’re getting.
You can invoke your code the same way as the test does to get the failure to happen (first step to solving a bug is getting the bug to happen, or at least understanding how it happens)

I wouldn’t pay too much attention to what the “solution” is doing, and instead consider what should happen.


#6

So I added many print statements so that I can understand what is happening throughout the run. I think I don’t understand the error it is throwing enough to figure out what is wrong. Can you help me understand the error?

It appears to assign the 2nd key,value just fine, but then something happens afterwards that seems related to the 2nd entry and the while statement?


#7

You wouldn’t copy the whole test code, you would copy the parts that make use of your code. Like the error message points out, you don’t have a fail_tests function, so obviously you can’t call that. That’s the second exception.
What you want to happen here is to let it crash so that you get information about what happened, instead of what codecademy does which is to catch the exception so you can’t see it, and instead providing a herpderp message about parameters.

The first exception is the failure you’re looking for, and it tells you where and how something goes wrong which you can then compare to what you meant to happen.

NoneType is the type of None (None is the only instance, so in this case it also says which the value is)
subscription is the [] operator, for example lookup by index for a list, so an error message complaining that None isn’t subscriptable… well, it speaks for itself, None doesn’t support that.

None[4]  # error

You should have some kind of argument for what and why that value should instead be, so you would check the code that makes that so. (alternatively if it should be None, then this action shouldn’t be taken since it isn’t possible/doesn’t make sense)


#8

I see what is happening. So after the 1st collision it finds another location. current_array_value gets reassigned to None during the first parts of the while loop. If the current_array_value is ever None in this type of object the while loop should end and not return back to the top. At the end of the if statement it returns back to the while loop, but now `current_array_value’ is None so the while loop does it’s thing but like you said:

while None[0] != key :

doesn’t make sense so it throws the error code. Is this why the solutions has the return at the end of each if statement? To end the while loop? I would think you would want a return at the end of the if and elif, but not the else since you want to be in the while loop until you find the key or find an open slot.

OR I could set:

current_array_value = self.array[new_array_index]

after the if or elif statement. This would make the current_array_value = key and also end the while loop. Does this reasoning sound right? Either return or setting current_array_value = key to end the while loop and avoid the NoneType error?


#9

Without understanding what’s supposed to happen in full (I just went ahead and read the instructions of this exercise and the previous one) –

Isn’t that what the loop’s condition is supposed to be testing?
And if exiting early from within the loop, then what is the condition in the loop doing? Nothing at all. I don’t like that at all. See what I mean about not paying too much attention to the solution? They don’t always seem to have had too much thought put into them.
What should happen instead, is that the variable named current_array_value … actually refers to what it says it refers to.
Clearly whoever wrote the “solution” ran into the same problem, and kind of swept the dirt under the rug instead of fixing the actual issue.

I offer up this solution instead:

while self.array[array_index][0] != key:
    new_hash_code = self.hash(key, number_collisions)
    array_index = self.compressor(new_hash_code)
    if self.array[array_index] is None or self.array[array_index][0] == key:
        self.array[array_index] = [key, value]
    number_collisions += 1

With the difference that rather than assigning a variable to the value in the backing memory, I instead track the location so that if memory is updated, I’ll see the new value when looking there, instead of the old value.
Alternatively, update the variable after updating memory.

(I say “memory” but there is no direct access to memory, list does that for us)


#10

Ok, I think I understand. Thanks! :+1: