hash function in Python

Question

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

Thank you thefourtheye - but I attempted to understand the python documentation and it didn't yield the clarity I was hoping for. Any other sources that explain what the hash() function does procedurally? — Mike Nedelko
– Mike Nedelko, Commented Feb 16, 2014 at 5:10
in cPython, the hash of an integer is itself, so return hash(h) is just equivalent to return h... — roippi
– roippi, Commented Feb 16, 2014 at 5:11

tom · Accepted Answer · 2014-02-16 05:28:32Z

2

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.

answered Feb 16, 2014 at 5:28

tom

23.2k7 gold badges47 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mike Nedelko Over a year ago

I see. So what we are doing here is to tell our class a modus to generate this integer via the loop above? for l in self.data: for i in l: if i: h += base base *= 2

user2357112 · Accepted Answer · 2014-02-16 05:31:25Z

2

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.

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.

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.

answered Feb 16, 2014 at 5:31

user2357112

286k32 gold badges490 silver badges569 bronze badges

1 Comment

Mike Nedelko Over a year ago

Thank you user2357112. That too was really helpful!

Collectives™ on Stack Overflow

hash function in Python

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related