I'm attempting to implement a basic hash table in Python using only lists. Any tips would be appreciated (including better hash functions). I intend this to handle collisions with separate chaining.
Are there any features I didn't implement that are standard in hash tables?
Are there any things I handled incorrectly or could have implemented in a better way?
My implementation:
class HashTable(object):
table = [None] * 256
def get_value(self, key):
total = 0
for i in range(len(key)):
total += ord(key[i]) * (7**i)
return (len(key) * total) % 256
def insert(self, key):
val = self.get_value(key)
if self.table[val] == None:
self.table[val] = key
else:
if type(self.table[val]) == list:
self.table[val].append(key)
else:
self.table[val] = [self.table[val], key]
def delete(self, key):
val = self.get_value(key)
if self.table[val] != None:
if type(self.table[val]) == list:
i = self.table[val].index(key)
self.table[val][i] = None
else:
self.table[val] = None
else:
KeyError()
def lookup(self, key):
found = False
val = self.get_value(key)
if type(self.table[val]) == list:
found = key in self.table[val]
else:
found = self.table[val] == key
return found
Note: This works on both Python 2 and should work in Python 3