Python Hash: Insert Method

Question

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

It is supposed to use linear probing to handle collision resolution. If the key is already in the table then the method returns -2. If the key is not already in the table and there exists empty slots then the key is entered into the empty slot number returned by the hash_function and that slot number is returned. If the key is not in the hash table and there are no empty slots then it returns -1.

Here is my class:

class MyHashTable:

def __init__(self, capacity):
    self.capacity = capacity
    self.slots = [None] * self.capacity

def __str__(self):
    return str(self.slots )

def __len__(self):
    count = 0
    for i in self.slots:
        if i != None:
            count += 1
    return count

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

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

The test is:

x = MyHashTable(2)
print("Add 3, return:", x.insert(3))
print("Hashtable:", x)
print("Add 3, return:", x.insert(3))  #duplicate
print("Hashtable:", x)

Result should be:

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

I tried a few methods but keep getting the error. "Nonetype" is not iterable.

There is no insert method in your code. That's makes it a little hard to diagnose the problem you're having with it :-) — paxdiablo
You won't be getting "NoneType is not iterable" from that added code, pass is not in the habit of iterating random collections :-) I suggest you add one of your attempts. — paxdiablo
When you get an error message it's a really good idea to post the full error message (in a code block), starting from the Traceback line; and to also post the section of code where that error occurs. If you'd done that it would've been immediately obvious to the people answering what was the cause of your problem. — PM 2Ring
FWIW, you got that "Nonetype" is not iterable message because your insert() is attempting to append key to None. Actually, the logic of your insert() appears to treat self.slots as if it were a list of lists. That is a legitimate way to organize a hash table, but it's not consistent with the rest of your class. — PM 2Ring

paxdiablo paxdiablo · Accepted Answer · 2015-02-11T03:45:46

Okay, we'll have to go from first principles here. Here's what insert will need to do for your case:

Get an initial slot number based on the key by calling hash_function. Save this slot position for later, we'll need it to detect if the hash table is full.
Check the current slot to see if it's empty. If it is, insert the key at that point and return success.
If the key is already at that slot, return -2, it's a duplicate.
Otherwise, that slot has some other key in it, so advance the slot to the next one (wrapping around back to slot zero if you go beyond the capacity). If you've cycled around back to the original slot saved in step 1, return -1 as the table is full.
Otherwise go back to step 2 and keep looking for either the key or an empty slot.

That's basically how hashing with linear probing is expected to work.

I urge you to try and implement that yourself, you'll become a better coder with some blood, sweat and tears :-)

Once done, see how it compares to my initial cut:

def insert(self, key):
    slot = self.hash_function(key)
    orig = slot
    while True:
        if self.slots[slot] is None:
            self.slots[slot] = key
            return slot

        if self.slots[slot] == key:
            return -2

        slot = (slot + 1) % self.capacity
        if slot == orig:
            return -1

I reserve the right to have left certain subtle bugs in there in case this is classwork that you should be doing yourself (actually the truth is that I just gave it a cursory test run so it may not be totally bug free, but it matches the algorithm I provided so should be close).

Python Hash: Insert Method

2 Answers