Chain Hash Table: Insert function

Question

I have been trying to write an insert(self, key) method for my MyChainHashTable class.

It is supposed to use separate chaining to handle collision resolution. If the key is not already in the hash table then it should insert the key at the end of the hashkey chained list and return the hashkey. If the key is already in the hash table then it should return -1.

Here is my class:

class MyChainHashTable:

    def __init__(self, capacity):
        self.capacity = capacity
        self.slots = [ ]
        for i in range(self.capacity):
            self.slots.append([])

    def __str__(self):
        info = ""
        for items in self.slots:
            info += str(items)
        return info

    def __len__(self):
        count = 0
        for i in self.slots:
            count += len(i)
        return count

    def hash_function(self, key):
        i = key % self.capacity
        return i

I tried this:

    def insert(self, key):
        self.slots[self.hash_function(key)].append(key)

But I don't know how to resolve collisions or how to return the -1.

The test is:

x = MyChainHashTable(2)
print("Add 3, return:", x.insert(3))
print("Add 3, return:", x.insert(3))
print("Hashtable:", x)

Result should be:

Add 3, return: 1
Add 3, return: -1
Hashtable: [][3]

martineau martineau · Accepted Answer · 2015-02-10T23:14:47

This does what you say you want:

    def insert(self, key):
        slot = self.hash_function(key)
        if key in self.slots[slot]:
            return -1
        else:
            self.slots[slot].append(key)
            return slot

Chain Hash Table: Insert function

1 Answers