23: Separate Chaining

Example 1: Page 462

In [1]:
#demonstrates hash table with separate chaining
from random import randrange	#for random numbers

class Link:

	def __init__(self, it):	#special method to create objects
	#with instances customized to a specific initial state
		#(could be other items)
		self.iData = it	#data item
		self.pNext = None	#next link in list
		
	def displayLink(self):	#display this link
		print self.iData,
#end class Link

class SortedList:

	def __init__(self):	#special method to create objects
	#with instances customized to a specific initial state

		#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
		self._pFirst = None	#refer to first list item

	def insert(self, pLink):	#insert link, in order
		key = pLink.iData
		pPrevious = None	#start at first
		pCurrent = self._pFirst
		#until end of list,
		while pCurrent and key > pCurrent.iData:	#or pCurrent > key,
			pPrevious = pCurrent
			pCurrent = pCurrent.pNext	#go to next item
		if not pPrevious:	#if beginning of list,
			self._pFirst = pLink	#first --> newlink
		else:	#not at beginning,
			pPrevious.pNext = pLink	#prev --> new link
		pLink.pNext = pCurrent	#new link --> current
	#end insert()

	def remove(self, key):	#delete link
		#(assumes non-empty list)
		pPrevious = None#start at first
		pCurrent = self._pFirst
		#until end of list,
		while pCurrent and key != pCurrent.iData:
			pPrevious = pCurrent	#or key == current,
			pCurrent = pCurrent.pNext	#go to next link
			#disconnect link

		if not pCurrent:	#if item not present in list
			print 'Item does not exist'
			return

		if not pPrevious:	#if beginning of list
			self._pFirst = self._pFirst.pNext	#delete first link
		else:	#not at beginning

			pPrevious.pNext = pCurrent.pNext	#delete current link
	#end remove()

	def find(self, key):	#find link
		pCurrent = self._pFirst	#start at first
		#until end of list,
		while pCurrent and pCurrent.iData <= key:	#or key too small,
			if pCurrent.iData == key:	#if this the link?
				return pCurrent	#found it, return link
			pCurrent = pCurrent.pNext	#go to next item
		return None#didn't find it
	#end find()
		
	def displayList(self):
		print 'List (first-->last):',
		pCurrent = self._pFirst	#start at beginning of list
		while pCurrent:	#until end of list,
			pCurrent.displayLink()	#print data
			pCurrent = pCurrent.pNext	#move to next link
		print
#end class SortedList


class HashTable:
	
	def __init__(self, size):	#special method to create objects
	#with instances customized to a specific initial state

		#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
		self._hashArray = []	#list of lists
		self._arraySize = size
		for j in xrange(self._arraySize):	#fill list
			self._hashArray.append(SortedList())	#with lists

	def displayTable(self):
		for j, val in enumerate(self._hashArray):	#for each cell,
			print j, '.',	#display cell number
			val.displayList()	#display list

	def hashFunc(self, key):	#hash function
		return key % self._arraySize

	def insert(self, pLink):	#insert a link
		key = pLink.iData
		hashVal = self.hashFunc(key)	#hash the key
		self._hashArray[hashVal].insert(pLink)#insert at hashVal
	#end insert()

	def remove(self, key):	#delete a Link
		hashVal = self.hashFunc(key)	#hash the key
		self._hashArray[hashVal].remove(key)	#delete link
	#end remove()

	def find(self, key):	#find link
		hashVal = self.hashFunc(key)	#hash the key
		pLink = self._hashArray[hashVal].find(key)	#get link
		return pLink	#return link

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

	#make table
theHashTable = HashTable(size)

for j in xrange(n):	#insert data
	aKey = randrange(0, keysPerCell*size)
	pDataItem = Link(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 = Link(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: 20
Enter initial number of items: 20

Enter first letter of show, insert, delete, or find: s
0 . List (first-->last): 40 1600
1 . List (first-->last): 101 301
2 . List (first-->last): 802
3 . List (first-->last): 743 1243
4 . List (first-->last):
5 . List (first-->last): 185 1385
6 . List (first-->last):
7 . List (first-->last): 1967
8 . List (first-->last): 568 1088
9 . List (first-->last): 1749
10 . List (first-->last): 750
11 . List (first-->last): 851
12 . List (first-->last): 1092
13 . List (first-->last): 113 1393 1773
14 . List (first-->last):
15 . List (first-->last):
16 . List (first-->last):
17 . List (first-->last):
18 . List (first-->last): 1538
19 . List (first-->last):

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

Example 2: Page 471

In [2]:
def hashFunc1(key):
	hashVal = 0
	pow27 = 1	#1, 27, 27*27, etc

	for j in reversed(xrange(0, len(key))):	#right to left
		letter = ord(key[j]) - 96	#get char code
		hashVal += pow27 * letter	#times power of 27
		pow27 *= 27	#next power of 27
	return hashVal % arraySize
#end hashFunc1()

Example 3: Page 472

In [3]:
def hashFunc2(key):
	hashVal = 0
	for j in xrange(0, len(key)):	#left to right
		letter = ord(key[j]) - 96	#get char code
		hashVal = hashVal * 27 + letter	#multiply and add
	return hashVal % arraySize	#mod
#end hashFunc2()

Example 4: Page 473

In [4]:
def hashFunc3(key):
	hashVal = 0
	for j in xrange(0, len(key)):	#left to right
		letter = ord(key[j]) - 96	#get char code
		hashVal = (hashVal * 27 + letter) % arraySize	#mod
	return hashVal	#no mod
#end hashFunc3()