Hash table using linear probing

Question

This code is meant to implement a hash table class which uses linear probing.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

class Hash:
 def __init__(self):
 self.size = 11
 self.vals = [None] * self.size
 self.keys = [None] * self.size
 self.step = 1
 def put(self, key, val):
 ind = self.hash(key)
 if self.keys[ind] == None:
 self.keys[ind] = key
 self.vals[ind] = val
 elif self.keys[ind] == key:
 self.vals[ind] = val
 else:
 ind = self.rehash(ind)
 while (self.keys[ind] != None and 
 self.keys[ind] != key):
 ind = self.rehash(ind)
 if self.keys[ind] == None:
 self.keys[ind] = key
 self.vals[ind] = val
 elif self.keys[ind] == key:
 self.vals[ind] = val
 def get(self, key):
 ind = self.hash(key)
 start_ind = ind
 val = None
 done = False
 while not done:
 if self.keys[ind] == key:
 val = self.vals[ind]
 done = True
 else:
 ind = self.rehash(ind)
 if ind == start_ind:
 done = True
 elif self.keys[ind] == None:
 done = True
 return val
 def hash(self, key):
 return key % self.size
 def rehash(self, oldhash):
 return (oldhash + self.step) % self.size
 def __getitem__(self, key):
 return self.get(key)
 def __setitem__(self, key, val):
 self.put(key, val)

Answer 1

break (or better yet return)

Instead of doing done = False/True. You could just use break and get rid of done altogether. But even better than that, just return.

This:

 if self.keys[ind] == key:
 val = self.vals[ind]
 done = True

Becomes:

 if self.keys[ind] == key:
 return self.vals[ind] # Value found!

This:

 if ind == start_ind:
 done = True
 elif self.keys[ind] == None:
 done = True

Becomes:

 if ind == start_ind: # Not found!
 return
 elif self.keys[ind] == None: # Not found!
 return

(You can return None if you want).

This gets rid of the val variable (and done)

• cycloidistic: Thanks for the suggestions. Does that mean that instead of while not done: I would use while True:?
• Dair: @cycloidistic: Yes.