22: Quadratic Probing

Example 1: Page 446

#demonstrates hash table with double hashing
from random import randrange	#for random numbers

class DataItem:	#(could have more items)
	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

	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 hashFunc1(self, key):
		return key % self._arraySize

	def hashFunc2(self, key):
		#non-zero, less than array size, different from hF1
		#array size must be relatively prime to 5, 4, 3, and 2
		return 5 - key % 5

	def insert(self, key, pItem):	#insert a DataItem
		#assumes table not full
		hashVal = self.hashFunc1(key)	#hash the key
		stepSize = self.hashFunc2(key)	#get step size
		#until empty cell or -1
		while self._hashArray[hashVal] and self._hashArray[hashVal].iData != -1:
			hashVal += stepSize#add the step
			hashVal %= self._arraySize	#for wraparound
		self._hashArray[hashVal] = pItem#insert item
	#end insert()

	def remove(self, key):	#delete a DataItem
		hashVal = self.hashFunc1(key)	#hash the key
		stepSize = self.hashFunc2(key)	#get step size
		
		while self._hashArray[hashVal]:	#until empty cell,
			if self._hashArray[hashVal].iData == key:	#is correct hashVal?
				pTemp = self._hashArray[hashVal]	#save item
				self._hashArray[hashVal] = self._pNonItem	#delete item
				return pTemp	#return item
			hashVal += stepSize#add the step
			hashVal %= self._arraySize	#for wraparound
		return None#can't find item
	#end remove()

	def find(self, key):	#find item with key
		hashVal = self.hashFunc1(key)	#hash the key
		stepSize = self.hashFunc2(key)	#get step size

		while self._hashArray[hashVal]:	#until empty cell,
			if self._hashArray[hashVal].iData == key:	#is correct hashVal?
				return self._hashArray[hashVal]	#yes, return item
			hashVal += stepSize#add the step
			hashVal %= self._arraySize	#for wraparound
		return None#can't find item

#end class HashTable

	#get sizes
size = int(raw_input('Enter size of hash table (use prime number): '))
n = int(raw_input('Enter initial number of items: '))
	#make table
theHashTable = HashTable(size)
for j in xrange(n):	#insert data
	aKey = randrange(0, 2*size)
	pDataItem = DataItem(aKey)
	theHashTable.insert(aKey, 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(aKey, 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 True:	#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 (use prime number): 23
Enter initial number of items: 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Enter first letter of show, insert, delete, or find: s
Table: ** 1 24 3 15 5 25 30 31 16 10 11 12 1 37 38 16 36 18 19 20 ** 41