# Hash table using linear probing

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)


# 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


(You can return None if you want).
This gets rid of the val variable (and done)
• Thanks for the suggestions. Does that mean that instead of while not done: I would use while True:? – cycloidistic Nov 18 '16 at 8:24