Python Hash Table Implementation

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

I'm pretty sure you implemented the necessary features in a standard hash table. If you want the hash table to populate only unique values then you need to change your insert method by looking up the value before inserting it.

Here are some things you did incorrectly or can do better in my opinion:

table = [None] * 256

table is static right now, which means that any instance of the class will have the same table variable. You need to initiate it in __init__.

def get_value(self, key):

get_value is a method that should not be called by the user of the class. I recommend making is private by changing its name to _get_value.

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]

Why starting with a single value and only after that changing to a list? I recommend starting with a list right from the start. As said by python's module this:


Special cases aren't special enough to break the rules.

That way, you can start with a table of empty lists right from the start, this will simplify your insert and lookup methods.

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

Making the value None can be dangerous - what if the user inserts lot's of values and then removes all of them? the lookup method will then take much more time than required. Although it takes more time, I still think list.remove is the right thing to do here.

...
    else:
        KeyError()

You need to raise the KeyError. Also - it's better to put in the error the right message. something like:
raise KeyError("key {key} can't be found.".format(key=key)

StackExchange Code Review Q#118110, answer score: 7