# 22: Quadratic Probing¶

## Example 1: Page 446¶

In [*]:
#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


In [ ]: