CODEWITHSUNDEEP
pythonhash
Mike Nedelko
Mike Nedelko

Reputation: 709

__hash__ function in Python

I am trying to understand a piece of code I am currently working through (its pacman).

I have the following 2D array in Python:

self.data = [[initialValue for y in range(height)] for x in range(width)]

The variables initialValue is default to F. Therefore the array is a list of lists containing the value 'F' for each element of the list (like so):

    # F F F F
    # F F F F 
    # F F F F

Now my code does the following - I do understand this part, but thought to include it in case it matters for my question: 

def __getitem__(self, i): 
        return self.data[i]  

def __setitem__(self, key, item):
       self.data[key] = item 

def __str__(self):         
       out = [[str(self.data[x][y])[0] for x in range(self.width)] for y in range(self.height)] 
       out.reverse()                                    #reverses the oder of with the last row of the two dimensional array becoming the first row.
       return '\n'.join([''.join(x) for x in out])      #every line is appended with a space '' followed by a line-break with '\n'

The latter turns the Grid into a chessboard of F's by using the \n demarcator. #F F F #F F F #F F F #F F F 

def __eq__(self, other):                               # The __eq__ method compares other instances of the class with itself
      if other == None: return False
      return self.data == other.data

def __hash__(self): 
      # return hash(str(self))
      base = 1
      h = 0
      for l in self.data:
          for i in l:
              if i:
                  h += base
              base *= 2
      return hash(h)

I happen to understand most of it, *but I get lost when it comes to the _hash_ function.*

I did research hashing and hash tables, but I can't seem to find what the function hash() does to our variable h?

What confuses me is the following:

1. It seems like we are creating some kind of hash table here based on self.data, but it seems like we leave this hash-table empty? Why would we do this?

2. It seems to me like the loop inside the _hash_ function is somehow linked to generating keys.

At this stage I can imagine that h is some form of key. The value of the key itself seems to increase every time it passes through the loop.

What confuses me is what the table would actually look like?

Is it this?

    # 1 - value
    # 2 - value 
    # 3 - value
    # 6 - value
    # 7 - value
    # 8 - value

etc...

3. Can anybody point me to a resource that would provide me with an idea of what hash(h) does to h procedurally?

Thank you very much for reading this and for wanting to help out.

Mike

Upvotes: 1

Views: 1335

Answers (2)

user2357112
user2357112

Reputation: 280181

  1. It seems like we are creating some kind of hash table here based on self.data, but it seems like we leave this hash-table empty? Why would we do this?

The code you've shown does not create a hash table. Rather, if a Grid object is used as a key in a hash table, its __hash__ method will be used to generate a hash code for it.

  1. It seems to me like the loop inside the __hash__ function is somehow linked to generating keys.

Indeed. The key it generates is the object's hash code.

  1. Can anybody point me to a resource that would provide me with an idea of what hash(h) does to h procedurally?

hash(h) returns a hash code for h. Hash codes are numbers associated with objects that are guaranteed to be equal for equal objects and unlikely to be equal for different objects; they're used to locate objects in a hash table. For integers, hash(h) is usually the integer itself.

Upvotes: 2

tom
tom

Reputation: 22939

The __hash__() function just returns an integer. It is called from the built-in function hash().

The key property of the hash function is that if two boards are equivalent, calling __hash__ on them will give the same number. If the boards are different, it is good (but not required) for their hashes to be different.

Hash functions are most commonly used by hashtables, but the hash function itself does not create or use a hashtable. The call to hash(h) simply converts h from a possibly huge number to a 32 bit integer.

Upvotes: 2

Related Questions