Removing an entry from hash table

Question

I'm having an issue, where my program is not removing the last given entry from the hash table. My delete function is the following:

def delete(self, key):
        if self.size == 0:
            raise Exception("Hash table is empty")
        index = self.find(key)
        if self.table[index] == key:
            self.table[index] = None
            self.size -= 1

The given input is short the decade first employee billion rather five training friend college wear player of in town toward yes last.
I proceed to remove the following employee of toward in player town toward five rather yes
Expected ouput: short the decade first billion training friend college wear last
Actual output: short the decade first billion training friend college wear yes last
I don't really understand why it removes the other key, but not the last one.

Full code

class HashLinear:

    def __init__(self, M):
        self.M = M
        self.table = [None for i in range(M)]
        self.size = 0

    def hash(self, key):
        sum = 0
        for i in range(len(key)):
            sum += ord(key[i])
        return sum % self.M

    def find(self, key):
        index = self.hash(key)
        while self.table[index] != None and self.table[index] != key:
            index = (index + 1) % self.M
        return index

    def insert(self, key):
        if self.size == self.M:
            raise Exception("Hash table is full")
        index = self.find(key)
        if self.table[index] == None:
            self.table[index] = key
            self.size += 1

    def delete(self, key):
        if self.size == 0:
            raise Exception("Hash table is empty")
        index = self.find(key)
        if self.table[index] == key:
            self.table[index] = None
            self.size -= 1

    def print(self):
        for key in self.table:
            if key != None:
                print(key, end=" ")
        print()


if __name__ == "__main__":
    table = HashLinear(20)
    table.insert("town")
    table.insert("rather")
    table.insert("short")
    table.insert("toward")
    table.insert("employee")
    table.insert("player")
    table.insert("toward")
    table.insert("the")
    table.insert("of")
    table.insert("college")
    table.insert("in")
    table.insert("yes")
    table.insert("billion")
    table.insert("five")
    table.insert("wear")
    table.insert("last")
    table.insert("decade")
    table.insert("first")
    table.insert("training")
    table.insert("friend")

    table.print()

    table.delete("employee")
    table.delete("of")
    table.delete("toward")
    table.delete("in")
    table.delete("player")
    table.delete("town")
    table.delete("toward")
    table.delete("five")
    table.delete("rather")
    table.delete("yes")

    table.print()

Your `delete` breaks collision resolution. – user2357112 Oct 02 '22 at 19:37 — user2357112, Oct 02 '22 at 19:37

score 1 · Answer 1 · answered Oct 02 '22 at 19:51

1

def delete(self, key):
        if self.size == 0:
            raise Exception("Hash table is empty")
        index = self.hash(key)
        if self.table[index] == key:
            self.table[index] = None
            self.size -= 1
        else:
            index = (index + 1) % self.M
            self.table[index] = None
            self.size -= 1

Made the trick for me.

answered Oct 02 '22 at 19:51

Daniel

186
2
14

This is completely wrong. It assumes that if a key wasn't found with `find`, it must be in the next hash table cell. That assumption is invalid; the key could be in any cell. – user2357112 Oct 02 '22 at 23:01
Open addressing hash tables usually leave a special "deleted entry" marker instead of an "unused cell" marker when they delete entries, so the "find" procedure knows it needs to keep looking when it finds a deleted entry. That avoids the issues your deletion procedure causes. – user2357112 Oct 02 '22 at 23:04
Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Oct 06 '22 at 04:21

score -1 · Answer 2 · answered Oct 02 '22 at 19:35

You can simply use the builtin OrderedDict for OrderedSet (as shown here):

keys = "short the decade first employee billion rather five training friend college wear player of in town toward yes last".split()
keys2 = "employee of toward in player town toward five rather yes".split()

from collections import OrderedDict

S = OrderedDict(zip(keys, [None]*len(keys)))
for k in keys2:
    if k in S:
        S.pop(k)

print(" ".join(S) ) 
# short the decade first billion training friend college wear last

Removing an entry from hash table

2 Answers2