Chapter 11 : Hash Tables¶

Example 11.1 Page No : 535¶

In [ ]:

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)

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())
elif choice == 'f':
print 'Enter key value to find: ',
value = int(raw_input())
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'

Enter size of hash table: 12
Enter initial number of items: 8


Example 11.2 Page no: 546¶

In [ ]:

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)

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())
elif choice == 'f':
print 'Enter key value to find: ',
value = int(raw_input())
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'

Enter size of hash table: 2
Enter initial number of items: 2


Example 11.3 Page no : 555¶

In [ ]:

def __init__(self,ii):
self.iData = ii

def getKey(self):
return self.iData

print self.iData ,

class SortedList:
def __init__(self):
self.first = None

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,
else: # not at beginning,

# (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

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 = 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

hashVal = self.hashFunc(key)

def delete(self,key): # delete a DataItem
hashVal = self.hashFunc(key) # hash the key

hashVal = self.hashFunc(key)# hash the key

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)

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())
elif choice == 'f':
print 'Enter key value to find: ',
value = int(raw_input())
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'

In [ ]: