#demonstrates hash table with linear probing
from random import randrange #for random numbers
class DataItem: #(could have more data)
def __init__(self, ii): #special method to create objects
#with instances customized to a specific initial state
self.iData = ii#data item (key)
#end class DataItem
class HashTable:
#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
_pNonItem = DataItem(-1) #for deleted items #deleted item key is -1
def __init__(self, size): #special method to create objects
#with instances customized to a specific initial state
self._arraySize = size
self._hashArray = [None] * size#list holds hash table#initialize elements
def displayTable(self):
print 'Table:',
for j in xrange(self._arraySize):
if self._hashArray[j]:
print self._hashArray[j].iData,
else:
print '**',
print
def hashFunc(self, key):
return key % self._arraySize #hash function
def insert(self, pItem): #insert a DataItem
#assumes table not full
key = pItem.iData #extract key
hashVal = self.hashFunc(key) #hash the key
#until empty cell or -1,
while self._hashArray[hashVal] and self._hashArray[hashVal].iData != -1:
hashVal += 1#go to next cell
hashVal %= self._arraySize #wraparound if necessary
self._hashArray[hashVal] = pItem#insert item
#end insert()
def remove(self, key): #remove a DataItem
hashVal = self.hashFunc(key) #hash the key
while self._hashArray[hashVal]: #until empty cell,
if self._hashArray[hashVal].iData == key: #found the key?
pTemp = self._hashArray[hashVal] #save item
self._hashArray[hashVal] = self._pNonItem #delete item
return pTemp #return item
hashVal += 1#go to next cell
hashVal %= self._arraySize #wraparound if necessary
return None#can't find item
#end remove()
def find(self, key): #find item with key
hashVal = self.hashFunc(key) #hash the key
while self._hashArray[hashVal]: #until empty cell,
if self._hashArray[hashVal].iData == key: #found the key?
return self._hashArray[hashVal] #yes, return item
hashVal += 1#go to next cell
hashVal %= self._arraySize #wraparound if necessary
return None#can't find item
#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 = 10
#make table
theHashTable = HashTable(size)
for j in xrange(n): #insert data
aKey = randrange(0, keysPerCell*size)
pDataItem = DataItem(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 = DataItem(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