Hash Table and Separate Chaining

This blog is intended towards providing Pythonic answers to some programming questions. These answers may not be perfect considering time complexity or space complexity of solution. But it will most definitely give you an idea on how to come up for solution for particular problem.

This is my first post and I would like to address most common programming question of Implementing Hash Table using separate chaining.

We will first require a class called 'hash_entry' that represents 'entry' in the hash table. It will also have some basic methods to be called by hash_entry object.

class hash_entry(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

    def get_key(self):
        return self.key

    def get_value(self):
        return self.value

    def set_key(self, key):
        self.key = key

    def set_value(self, value):
        self.value = value

    def set_next(self, next):
        self.next = next

Once we are done with hash_entry, now let us write methods to create hash table, set key and value and get value. It will look something like this:

class hash_table(object):
    def __init__(self, size_hash_table):
        self.size_of_hash_table = size_hash_table
        self.table = [None for x in range(self.size_of_hash_table)]

    def set(self, key, value):
        """
  set value for given key
        """
        hash = key % 10
        if self.table[hash] is None:
            self.table[hash] = hash_entry(key, value)
        else:
            entry = self.table[hash]
            while entry is not None and entry.get_key() != key:
                previous = entry
                entry = entry.next
            if entry is None:
                new_entry = hash_entry(key, value)
                previous.next = new_entry
            else:
                entry.set_value(value)

    def get(self, key):
 """
 given key, returns value
 """
        hash = key % 10
        if self.table[hash] is None:
            return -1
        else:
            entry = self.table[hash]
            while entry is not None and entry.get_key() != key:
                entry = entry.next
            if entry is None:
                return -1
            else:
                return entry.get_value()

To set value in hash table, the trick is calculating hash and check if that 'hash' index is already occupied in table. If it is, it will check if corresponding key is not the same key and value at that 'hash' index is not 'None'.

while entry is not None and entry.get_key() != key

While loop will continue unless either condition fails. When 'while' loop exists, we have to check which condition actually failed. If entry is none, we just create new hash_entry object and set it as new entry with line 'new_entry = hash_entry(key,value)'.

To 'get' the value, similar logic is implemented. If 'entry' is None, it returns -1 else returns the value.

If you find any mistakes or know any better solution I request you to please comment. This blog is aimed at helping thousands of users like me who want to improve themselves in Python. Good Luck! Continue Python Giri(a habit, an attitude)!