Hash Tables

hash-table.py

class hashtable_chain(object):
    '''Chain collision implemented hash table'''
    def __init__(self, hash_array_size=11):
        self.size = hash_array_size
        self.key_values_pairs = [[]]*hash_array_size

    def _hash_function(self, x):
        ''' Private hash function.
        Convert x into a string.
        For each letter in string, position * ord(letter)
        which ensures that anagrams don't hash to the same value.
        '''
        string_x = str(x)
        sha = 0
        for i, letter in enumerate(string_x, start=1): # Q: This is O(n) hash?
            sha += i * ord(letter)
        return sha%self.size

    def add(self, key, value):
        '''Add this key value pair'''
        hash_index = self._hash_function(key)
        this_hash_chain = self.key_values_pairs[hash_index]
        already_in_hash = False
        for k_v in this_hash_chain:
            if k_v[0] == key:
                already_in_hash=True
                k_v[1] = value
        if already_in_hash == False:
            key_value_pair = [key, value]
            this_hash_chain.append(key_value_pair)

    def get(self, key):
        '''Get the key-value pair'''
        hash_index = self._hash_function(key)
        in_hash = False
        for k_v_pair in self.key_values_pairs[hash_index]:
            if k_v_pair[0] == key:
                return k_v_pair
        if in_hash == False:
            return None

    def delete(self, key):
        ''' Delete this keyed item'''
        hash_index = self._hash_function(key)
        in_hash = False
        for i, k_v_pair in enumerate(self.key_values_pairs[hash_index]):
            if k_v_pair[0] == key:
                break
        del self.key_values_pairs[hash_index][i]

class hashtable_openaddress(object):
    '''Hash table implementation with open addressing implemented by linear probing + 1 rehash'''
    def __init__(self, table_size=11):
        self.size = table_size
        self.key_value_pairs = [None]*table_size

    def _hash_function(self, key):
        return ord(str(key))%self.size

    def _reshash_function(self, oldhash):
        return oldhash+1%self.size

    def add(self, key, value):
        ''' Q: What do we do if all slots are taken?'''
        hash_index = self._hash_function(key)
        kvpair = self.key_values_pairs[hash_index]
        count = 0
        while kvpair != None:
            if count == self.size:
                break
            count += 1
            if hash_kvpair[0] == key:
                hash_kvpair[1] = value
                return
            hash_index = self._reshash_function(hash_index)
            kvpair = self.key_values_pairs(hash_index)

    def get(self, key):
        hash_index = self._hash_function(key)
        kvpair = self.key_values_pairs[hash_index]
        count = 0
        while kvpair != None:
            if count == self.size:
                break
            count += 1
            if hash_kvpair[0] == key:
                return hash_kvpair
            hash_index = self._reshash_function(hash_index)
            kvpair = self.key_values_pairs(hash_index)
        raise exception("Key Error")

    def delete(self, key):
        hash_index = self._hash_function(key)
        kvpair = self.key_value_pairs[hash_index]
        count = 0
        while kvpair != None:
            if count == self.size:
                break
            count += 1
            if hash_kvpair[0] == key:
                hash_kvpair = None #Q: does this work or do I need to do self.key_value_pairs[hash_index] = None?
            hash_index = self._reshash_function(hash_index)
            kvpair = self.key_values_pairs(hash_index)
        raise exception("Key Error")