class DataItem:
def __init__(self,ii):
self.iData = ii
def getKey(self):
return self.iData
class HashTable:
def __init__(self,size):
self.hashArray = [] # array is the hash table
for i in range(size):
self.hashArray.append(DataItem(0))
self.arraySize = size
self.nonItem = None # for deleted items
def displayTable(self):
print 'Table: ',
for j in range(self.arraySize):
if(self.hashArray[j] != None):
print self.hashArray[j].getKey() ,
else:
print '** ' ,
print ''
def hashFunc(self,key):
return key % self.arraySize
# insert a DataItem
def insert(self,item):
key = item.getKey() # extract key
hashVal = self.hashFunc(key) # hash the key
while(self.hashArray[hashVal] != None and self.hashArray[hashVal].getKey() != -1):
hashVal += 1
hashVal %= self.arraySize # wraparound if necessary
self.hashArray[hashVal] = item # insert item
def delete(self,key): # delete a DataItem
hashVal = hashFunc(key) # hash the key
while(self.hashArray[hashVal] != None): # until empty cell,
# is correct hashVal?
if(self.hashArray[hashVal].getKey() == key):
temp = self.hashArray[hashVal] # save item
self.hashArray[hashVal] = nonItem # delete item
return temp # return item
hashVal += 1
hashVal %= self.arraySize # for wraparound
return None # cant find item
def find(self,key): # find item with key
# (assumes table not full)
hashVal = hashFunc(key) # hash the key
while(self.hashArray[hashVal] != None): # until empty cell,
# is correct hashVal?
if(self.hashArray[hashVal].getKey() == key):
return self.hashArray[hashVal] # yes, return item
hashVal += 1 # add the step
hashVal %= self.arraySize
# for wraparound
return None # cant find item
print 'Enter size of hash table: ',
size = int(raw_input())
print 'Enter initial number of items: ',
n = int(raw_input()) # make table
theHashTable = HashTable(size)
keysPerCell = 10
import random
for j in range(n): # insert data
aKey = int(random.random() * keysPerCell * size)
aDataItem = DataItem(aKey)
theHashTable.insert(aDataItem)
while(True):
print 'Enter first letter of show, '
print 'insert, find, delete, or traverse: ',
choice = raw_input()
if choice == 's':
theHashTable.displayTable()
elif choice == 'i':
print 'Enter value to key to insert: '
value = int(raw_input())
aDataItem = DataItem(aKey)
theHashTable.insert(aDataItem)
elif choice == 'f':
print 'Enter key value to find: ',
value = int(raw_input())
aDataItem = theHashTable.find(aKey)
if(aDataItem != None):
print 'Found ' , aKey
else:
print 'Could not find ' , aKey
elif choice=='d':
print 'Enter key value to delete: ',
value = int(raw_input())
theHashTable.delete(value)
else:
print 'Invalid entry'
class DataItem:
def __init__(self,ii):
self.iData = ii
def getKey(self):
return self.iData
class HashTable:
def __init__(self,size):
self.hashArray = [] # array is the hash table
for i in range(size):
self.hashArray.append(DataItem(0))
self.arraySize = size
self.nonItem = None # for deleted items
def displayTable(self):
print 'Table: ',
for j in range(self.arraySize):
if(self.hashArray[j] != None):
print self.hashArray[j].getKey() ,
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
# insert a DataItem
def insert(self,key,item):
# (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] != None and self.hashArray[hashVal].getKey() != -1):
hashVal += stepSize # add the step
hashVal %= self.arraySize # for wraparound
self.hashArray[hashVal] = item # insert item
def delete(self,key): # delete a DataItem
hashVal = hashFunc1(key) # hash the key
stepSize = hashFunc2(key) # get step size
while(self.hashArray[hashVal] != None): # until empty cell,
# is correct hashVal?
if(self.hashArray[hashVal].getKey() == key):
temp = self.hashArray[hashVal] # save item
self.hashArray[hashVal] = nonItem # delete item
return temp # return item
hashVal += stepSize # add the step
hashVal %= self.arraySize # for wraparound
return None # cant find item
def find(self,key): # find item with key
# (assumes table not full)
hashVal = hashFunc1(key) # hash the key
stepSize = hashFunc2(key) # get step size
while(self.hashArray[hashVal] != None): # until empty cell,
# is correct hashVal?
if(self.hashArray[hashVal].getKey() == key):
return self.hashArray[hashVal] # yes, return item
hashVal += stepSize # add the step
hashVal %= self.arraySize
# for wraparound
return None # cant find item
print 'Enter size of hash table: ',
size = int(raw_input())
print 'Enter initial number of items: ',
n = int(raw_input()) # make table
theHashTable = HashTable(size)
import random
for j in range(n): # insert data
aKey = int(random.random() * 2 * size)
aDataItem = DataItem(aKey)
theHashTable.insert(aKey, aDataItem)
while(True):
print 'Enter first letter of show, '
print 'insert, find, delete, or traverse: ',
choice = raw_input()
if choice == 's':
theHashTable.displayTable()
elif choice == 'i':
print 'Enter value to key to insert: '
value = int(raw_input())
aDataItem = DataItem(aKey)
theHashTable.insert(aKey, aDataItem)
elif choice == 'f':
print 'Enter key value to find: ',
value = int(raw_input())
aDataItem = theHashTable.find(aKey)
if(aDataItem != None):
print 'Found ' , aKey
else:
print 'Could not find ' , aKey
elif choice=='d':
print 'Enter key value to delete: ',
value = int(raw_input())
theHashTable.delete(value)
else:
print 'Invalid entry'
class Link:
def __init__(self,ii):
self.iData = ii
def getKey(self):
return self.iData
def displayLink(self):
print self.iData ,
class SortedList:
def __init__(self):
self.first = None
def insert(self,theLink): # insert link, in order
key = theLink.getKey()
self.previous = None # start at self.first
current = self.first # until end of list,
while( current != None and key > current.getKey() ): # or current > key,
self.previous = current
current = current.next # go to next item
if(self.previous==None): # if beginning of list,
self.first = theLink
else: # not at beginning,
self.previous.next = theLink
theLink.next = current # new link --> current
def delete(self,key): # delete link
# (assumes non-empty list)
self.previous = None # start at self.first
current = self.first # until end of list,
while( current != None and key != current.getKey() ): # or key == current,
self.previous = current
current = current.next # go to next link
if(self.previous==None):
self.first = self.first.next
else:
self.previous.next = current.next
def find(self,key): # find link
current = self.first # start at self.first
# until end of list,
while(current != None and current.getKey() <= key): # or key too small,
if(current.getKey() == key):# is this the link?
return current # found it, return link
current = current.next # go to next item
return None # didnt find it
def displayList(self):
print 'List (self.first-->last): ',
current = self.first # start at beginning of list
while(current != None): # until end of list,
current.displayLink() # print data
current = current.next # move to next link
print ''
class HashTable:
def __init__(self,size):
self.hashArray = [] # array is the hash table
for i in range(size):
self.hashArray.append(SortedList())
self.arraySize = size
self.nonItem = None # for deleted items
def displayTable(self):
print 'Table: ',
for j in range(self.arraySize):
print j,
self.hashArray[j].displayList()
def hashFunc(self,key):
return key % self.arraySize
def insert(self,theLink):
key = theLink.getKey()
hashVal = self.hashFunc(key)
self.hashArray[hashVal].insert(theLink)
def delete(self,key): # delete a DataItem
hashVal = self.hashFunc(key) # hash the key
self.hashArray[hashVal].delete(key) # delete link
def find(self,key): # find link
hashVal = self.hashFunc(key)# hash the key
theLink = self.hashArray[hashVal].find(key) # get link
return theLink # return link
keysPerCell = 100
print 'Enter size of hash table: ',
size = int(raw_input())
print 'Enter initial number of items: ',
n = int(raw_input()) # make table
theHashTable = HashTable(size)
import random
for j in range(n): # insert data
aKey = int(random.random() * 2 * size)
aDataItem = Link(aKey)
theHashTable.insert(aDataItem)
while(True):
print 'Enter self.first letter of show, '
print 'insert, find, delete, or show: ',
choice = raw_input()
if choice == 's':
theHashTable.displayTable()
elif choice == 'i':
print 'Enter value to key to insert: '
value = int(raw_input())
aDataItem = Link(aKey)
theHashTable.insert(aDataItem)
elif choice == 'f':
print 'Enter key value to find: ',
value = int(raw_input())
aDataItem = theHashTable.find(aKey)
if(aDataItem != None):
print 'Found ' , aKey
else:
print 'Could not find ' , aKey
elif choice=='d':
print 'Enter key value to delete: ',
value = int(raw_input())
theHashTable.delete(value)
else:
print 'Invalid entry'