#demonstrates hash table with separate chaining
from random import randrange #for random numbers
class Link:
def __init__(self, it): #special method to create objects
#with instances customized to a specific initial state
#(could be other items)
self.iData = it #data item
self.pNext = None #next link in list
def displayLink(self): #display this link
print self.iData,
#end class Link
class SortedList:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._pFirst = None #refer to first list item
def insert(self, pLink): #insert link, in order
key = pLink.iData
pPrevious = None #start at first
pCurrent = self._pFirst
#until end of list,
while pCurrent and key > pCurrent.iData: #or pCurrent > key,
pPrevious = pCurrent
pCurrent = pCurrent.pNext #go to next item
if not pPrevious: #if beginning of list,
self._pFirst = pLink #first --> newlink
else: #not at beginning,
pPrevious.pNext = pLink #prev --> new link
pLink.pNext = pCurrent #new link --> current
#end insert()
def remove(self, key): #delete link
#(assumes non-empty list)
pPrevious = None#start at first
pCurrent = self._pFirst
#until end of list,
while pCurrent and key != pCurrent.iData:
pPrevious = pCurrent #or key == current,
pCurrent = pCurrent.pNext #go to next link
#disconnect link
if not pCurrent: #if item not present in list
print 'Item does not exist'
return
if not pPrevious: #if beginning of list
self._pFirst = self._pFirst.pNext #delete first link
else: #not at beginning
pPrevious.pNext = pCurrent.pNext #delete current link
#end remove()
def find(self, key): #find link
pCurrent = self._pFirst #start at first
#until end of list,
while pCurrent and pCurrent.iData <= key: #or key too small,
if pCurrent.iData == key: #if this the link?
return pCurrent #found it, return link
pCurrent = pCurrent.pNext #go to next item
return None#didn't find it
#end find()
def displayList(self):
print 'List (first-->last):',
pCurrent = self._pFirst #start at beginning of list
while pCurrent: #until end of list,
pCurrent.displayLink() #print data
pCurrent = pCurrent.pNext #move to next link
print
#end class SortedList
class HashTable:
def __init__(self, size): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._hashArray = [] #list of lists
self._arraySize = size
for j in xrange(self._arraySize): #fill list
self._hashArray.append(SortedList()) #with lists
def displayTable(self):
for j, val in enumerate(self._hashArray): #for each cell,
print j, '.', #display cell number
val.displayList() #display list
def hashFunc(self, key): #hash function
return key % self._arraySize
def insert(self, pLink): #insert a link
key = pLink.iData
hashVal = self.hashFunc(key) #hash the key
self._hashArray[hashVal].insert(pLink)#insert at hashVal
#end insert()
def remove(self, key): #delete a Link
hashVal = self.hashFunc(key) #hash the key
self._hashArray[hashVal].remove(key) #delete link
#end remove()
def find(self, key): #find link
hashVal = self.hashFunc(key) #hash the key
pLink = self._hashArray[hashVal].find(key) #get link
return pLink #return link
#end class HashTable
choice = 'b'
#get sizes
size = int(raw_input('Enter size of hash table: '))
n = int(raw_input('Enter initial number of items: '))
keysPerCell = 100
#make table
theHashTable = HashTable(size)
for j in xrange(n): #insert data
aKey = randrange(0, keysPerCell*size)
pDataItem = Link(aKey)
theHashTable.insert(pDataItem)
#as switch is not available in Python, hence using dictionaries and functions instead
def show():
theHashTable.displayTable()
def insert():
aKey = int(raw_input('Enter key value to insert: '))
pDataItem = Link(aKey)
theHashTable.insert(pDataItem)
def delete():
aKey = int(raw_input('Enter key value to delete: '))
theHashTable.remove(aKey)
def find():
aKey = int(raw_input('Enter key value to find: '))
pDataItem = theHashTable.find(aKey)
if pDataItem:
print 'Found', aKey
else:
print 'Coud not find', aKey
case = {'s' : show,
'i' : insert,
'd' : delete,
'f' : find}
#dictionaries and functions set for using
while choice != 'x': #interact with user
print
choice = raw_input('Enter first letter of show, insert, delete, or find: ')
if case.get(choice, None):
case[choice]()
else:
print 'Invalid Entry'
#end while
#end