Skip to content

Instantly share code, notes, and snippets.

@AgungPambudi
Forked from sachinnair90/hashtable.py
Created March 10, 2021 09:59
Show Gist options
  • Save AgungPambudi/8b5967c8268b7988b4615095cec66cf4 to your computer and use it in GitHub Desktop.
Save AgungPambudi/8b5967c8268b7988b4615095cec66cf4 to your computer and use it in GitHub Desktop.
Simple Hash table implementation in Python
class MyHashTable:
def __init__(self):
self.size = 11
self.positions = [None] * self.size
self.values = [None] * self.size
def put(self,key,value):
hashvalue = self.hashfn(key,len(self.positions))
if self.positions[hashvalue] == None:
self.positions[hashvalue] = key
self.values[hashvalue] = value
else:
if self.positions[hashvalue] == key:
self.values[hashvalue] = value #replace
else:
nextposition = self.rehash(hashvalue,len(self.positions))
while self.positions[nextposition] != None and \
self.positions[nextposition] != key:
nextposition = self.rehash(nextposition,len(self.positions))
if self.positions[nextposition] == None:
self.positions[nextposition]=key
self.values[nextposition]=value
else:
self.values[nextposition] = value #replace
def hashfn(self,key,size):
return key%size
def rehash(self,oldhash,size):
return (oldhash+1)%size
def get(self,key):
startposition = self.hashfn(key,len(self.positions))
value = None
stop = False
found = False
position = startposition
while self.positions[position] != None and \
not found and not stop:
if self.positions[position] == key:
found = True
value = self.values[position]
else:
position=self.rehash(position,len(self.positions))
if position == startposition:
stop = True
return value
def __getitem__(self,key):
return self.get(key)
def __setitem__(self,key,value):
self.put(key,value)
H = MyHashTable()
H[31]="cow"
H[44]="goat"
H[54]="cat"
H[17]="tiger"
H[77]="bird"
H[55]="pig"
H[20]="chicken"
H[26]="dog"
H[93]="lion"
print(H.positions)
print(H.values)
print(H[20])
print(H[17])
H[20]='duck'
print(H[20])
print(H[99])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment