21: Hash Tables

Example 1: Page 433

In [1]:
#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
Enter size of hash table: 12
Enter initial number of items: 8

Enter first letter of show, insert, delete, or find: s
Table: 72 73 86 2 28 51 77 115 ** ** ** **

Enter first letter of show, insert, delete, or find: f
Enter key value to find: 86
Found 86

Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 100

Enter first letter of show, insert, delete, or find: s
Table: 72 73 86 2 28 51 77 115 100 ** ** **

Enter first letter of show, insert, delete, or find: d
Enter key value to delete: 100

Enter first letter of show, insert, delete, or find: s
Table: 72 73 86 2 28 51 77 115 -1 ** ** **

Enter first letter of show, insert, delete, or find: x
Invalid Entry