Tracing Hash Tables

COSC 2306: Data Programming - Collision Resolution

Linear Probing
Chaining

Execution Trace

Action: WAITING
Table Size: 11
Select an action and target word, then click "Step" to begin.

Controls

# HashTable visualizer ready.
# Size: 11, Mode: Linear Probing
Python Implementation (Linear Probing) 
class HashTable:
    def __init__(self, hash_size):
        self.size = hash_size
        self.slots = [None] * self.size
        self.data = [None] * self.size

    def stringhash(self, a_string, table_size):
        sum = 0
        for pos in range(len(a_string)):
            sum = sum + ord(a_string[pos])
        return sum % table_size

    def rehash(self, old_hash, size):
        return (old_hash + 1) % size

    def put(self, key, data):
        hash_value = self.stringhash(key, self.size)
        
        if self.slots[hash_value] is None:
            self.slots[hash_value] = key
            self.data[hash_value] = data
        elif self.slots[hash_value] == key:
            self.data[hash_value] = data # replace
        else:
            next_slot = self.rehash(hash_value, self.size)
            while (self.slots[next_slot] is not None and 
                   self.slots[next_slot] != key):
                next_slot = self.rehash(next_slot, self.size)
                
            if self.slots[next_slot] is None:
                self.slots[next_slot] = key
                self.data[next_slot] = data
            else:
                self.data[next_slot] = data