In this lecture we will be implementing our own Hash Table to complete our understanding of Hash Tables and Hash Functions! Make sure to review the video lecture before this to fully understand this implementation!
Keep in mind that Python already has a built-in dictionary object that serves as a Hash Table, you would never actually need to implement your own hash table in Python.
The idea of a dictionary used as a hash table to get and retrieve items using keys is often referred to as a mapping. In our implementation we will have the following methods:
class HashTable(object): def __init__(self,size): # Set up size and slots and data self.size = size self.slots = [None] * self.size self.data = [None] * self.size def put(self,key,data): #Note, we'll only use integer keys for ease of use with the Hash Function # Get the hash value hashvalue = self.hashfunction(key,len(self.slots)) # If Slot is Empty if self.slots[hashvalue] == None: self.slots[hashvalue] = key self.data[hashvalue] = data else: # If key already exists, replace old value if self.slots[hashvalue] == key: self.data[hashvalue] = data # Otherwise, find the next available slot else: nextslot = self.rehash(hashvalue,len(self.slots)) # Get to the next slot while self.slots[nextslot] != None and self.slots[nextslot] != key: nextslot = self.rehash(nextslot,len(self.slots)) # Set new key, if NONE if self.slots[nextslot] == None: self.slots[nextslot]=key self.data[nextslot]=data # Otherwise replace old value else: self.data[nextslot] = data def hashfunction(self,key,size): # Remainder Method return key%size def rehash(self,oldhash,size): # For finding next possible positions return (oldhash+1)%size def get(self,key): # Getting items given a key # Set up variables for our search startslot = self.hashfunction(key,len(self.slots)) data = None stop = False found = False position = startslot # Until we discern that its not empty or found (and haven't stopped yet) while self.slots[position] != None and not found and not stop: if self.slots[position] == key: found = True data = self.data[position] else: position=self.rehash(position,len(self.slots)) if position == startslot: stop = True return data # Special Methods for use with Python indexing def __getitem__(self,key): return self.get(key) def __setitem__(self,key,data): self.put(key,data)
h = HashTable(5)
# Put our first key in h[1] = 'one' h[2] = 'two' h[3] = 'three'
print(h[1])
‘one’
print(h[4])
None
If you like my post please follow me to read my latest post on programming and technology.
Problem Statement: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example…
Given an integer A. Compute and return the square root of A. If A is…
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where…
A heap is a specialized tree-based data structure that satisfies the heap property. It is…
What is the Lowest Common Ancestor? In a tree, the lowest common ancestor (LCA) of…