1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
{
"metadata": {
"name": "ch11"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": "Chapter 11 : Hash Tables"
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": "Example 11.1 Page No : 535"
},
{
"cell_type": "code",
"collapsed": false,
"input": "'''\nExample 11.1\ndemonstrates hash table with linear probing\n'''\nclass DataItem:\n def __init__(self,ii):\n self.iData = ii\n\n def getKey(self):\n return self.iData\n\nclass HashTable:\n def __init__(self,size):\n self.hashArray = [] # array is the hash table\n for i in range(size):\n self.hashArray.append(DataItem(0))\n self.arraySize = size\n self.nonItem = None # for deleted items\n\n def displayTable(self):\n print 'Table: ',\n for j in range(self.arraySize):\n if(self.hashArray[j] != None):\n print self.hashArray[j].getKey() ,\n else:\n print '** ' ,\n print ''\n\n\n def hashFunc(self,key):\n return key % self.arraySize\n\n # insert a DataItem\n def insert(self,item):\n key = item.getKey() # extract key\n hashVal = self.hashFunc(key) # hash the key\n while(self.hashArray[hashVal] != None and self.hashArray[hashVal].getKey() != -1):\n hashVal += 1\n hashVal %= self.arraySize # wraparound if necessary\n self.hashArray[hashVal] = item # insert item\n\n def delete(self,key): # delete a DataItem\n hashVal = hashFunc(key) # hash the key\n while(self.hashArray[hashVal] != None): # until empty cell,\n # is correct hashVal?\n if(self.hashArray[hashVal].getKey() == key):\n temp = self.hashArray[hashVal] # save item\n self.hashArray[hashVal] = nonItem # delete item\n return temp # return item\n hashVal += 1\n hashVal %= self.arraySize # for wraparound\n return None # cant find item\n\n def find(self,key): # find item with key\n # (assumes table not full)\n hashVal = hashFunc(key) # hash the key\n while(self.hashArray[hashVal] != None): # until empty cell,\n # is correct hashVal?\n if(self.hashArray[hashVal].getKey() == key):\n return self.hashArray[hashVal] # yes, return item\n hashVal += 1 # add the step\n hashVal %= self.arraySize\n # for wraparound\n return None # cant find item\n\nprint 'Enter size of hash table: ',\nsize = int(raw_input())\nprint 'Enter initial number of items: ',\nn = int(raw_input()) # make table\ntheHashTable = HashTable(size)\nkeysPerCell = 10\nimport random\nfor j in range(n): # insert data\n aKey = int(random.random() * keysPerCell * size)\n aDataItem = DataItem(aKey) \n theHashTable.insert(aDataItem)\n\nwhile(True):\n print 'Enter first letter of show, '\n print 'insert, find, delete, or traverse: ',\n choice = raw_input()\n if choice == 's':\n theHashTable.displayTable()\n elif choice == 'i':\n print 'Enter value to key to insert: '\n value = int(raw_input())\n aDataItem = DataItem(aKey)\n theHashTable.insert(aDataItem)\n elif choice == 'f':\n print 'Enter key value to find: ',\n value = int(raw_input())\n aDataItem = theHashTable.find(aKey)\n if(aDataItem != None):\n print 'Found ' , aKey\n else:\n print 'Could not find ' , aKey\n\n elif choice=='d':\n print 'Enter key value to delete: ',\n value = int(raw_input())\n theHashTable.delete(value)\n else:\n print 'Invalid entry'\n",
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": "Enter size of hash table: "
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": "12\n"
},
{
"output_type": "stream",
"stream": "stdout",
"text": " Enter initial number of items: "
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": "8\n"
}
],
"prompt_number": "*"
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": "Example 11.2 Page no: 546"
},
{
"cell_type": "code",
"collapsed": false,
"input": "'''\nexample 11.2\ndemonstrates hash table with double hashing\n'''\nclass DataItem:\n def __init__(self,ii):\n self.iData = ii\n\n def getKey(self):\n return self.iData\n\nclass HashTable:\n def __init__(self,size):\n self.hashArray = [] # array is the hash table\n for i in range(size):\n self.hashArray.append(DataItem(0))\n self.arraySize = size\n self.nonItem = None # for deleted items\n\n def displayTable(self):\n print 'Table: ',\n for j in range(self.arraySize):\n if(self.hashArray[j] != None):\n print self.hashArray[j].getKey() ,\n else:\n print '** ' ,\n print ''\n\n def hashFunc1(self,key):\n return key % self.arraySize\n\n def hashFunc2(self,key):\n # non-zero, less than array size, different from hF1\n # array size must be relatively prime to 5, 4, 3, and 2\n return 5 - key % 5\n \n # insert a DataItem\n def insert(self,key,item):\n # (assumes table not full)\n hashVal = self.hashFunc1(key) # hash the key\n stepSize = self.hashFunc2(key) # get step size\n # until empty cell or -1\n while(self.hashArray[hashVal] != None and self.hashArray[hashVal].getKey() != -1):\n hashVal += stepSize # add the step\n hashVal %= self.arraySize # for wraparound\n self.hashArray[hashVal] = item # insert item\n\n def delete(self,key): # delete a DataItem\n hashVal = hashFunc1(key) # hash the key\n stepSize = hashFunc2(key) # get step size\n while(self.hashArray[hashVal] != None): # until empty cell,\n # is correct hashVal?\n if(self.hashArray[hashVal].getKey() == key):\n temp = self.hashArray[hashVal] # save item\n self.hashArray[hashVal] = nonItem # delete item\n return temp # return item\n hashVal += stepSize # add the step\n hashVal %= self.arraySize # for wraparound\n return None # cant find item\n\n def find(self,key): # find item with key\n # (assumes table not full)\n hashVal = hashFunc1(key) # hash the key\n stepSize = hashFunc2(key) # get step size\n while(self.hashArray[hashVal] != None): # until empty cell,\n # is correct hashVal?\n if(self.hashArray[hashVal].getKey() == key):\n return self.hashArray[hashVal] # yes, return item\n hashVal += stepSize # add the step\n hashVal %= self.arraySize\n # for wraparound\n return None # cant find item\n\nprint 'Enter size of hash table: ',\nsize = int(raw_input())\nprint 'Enter initial number of items: ',\nn = int(raw_input()) # make table\ntheHashTable = HashTable(size)\nimport random\nfor j in range(n): # insert data\n aKey = int(random.random() * 2 * size)\n aDataItem = DataItem(aKey) \n theHashTable.insert(aKey, aDataItem)\n\nwhile(True):\n print 'Enter first letter of show, '\n print 'insert, find, delete, or traverse: ',\n choice = raw_input()\n if choice == 's':\n theHashTable.displayTable()\n elif choice == 'i':\n print 'Enter value to key to insert: '\n value = int(raw_input())\n aDataItem = DataItem(aKey)\n theHashTable.insert(aKey, aDataItem)\n elif choice == 'f':\n print 'Enter key value to find: ',\n value = int(raw_input())\n aDataItem = theHashTable.find(aKey)\n if(aDataItem != None):\n print 'Found ' , aKey\n else:\n print 'Could not find ' , aKey\n\n elif choice=='d':\n print 'Enter key value to delete: ',\n value = int(raw_input())\n theHashTable.delete(value)\n else:\n print 'Invalid entry'\n",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": "*"
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": "Example 11.3 Page no : 555"
},
{
"cell_type": "code",
"collapsed": false,
"input": "'''\nExample 11.3\ndemonstrates hash table with separate chaining\n'''\n\nclass Link:\n def __init__(self,ii):\n self.iData = ii\n\n def getKey(self):\n return self.iData\n\n def displayLink(self):\n print self.iData ,\n\nclass SortedList:\n def __init__(self):\n self.first = None\n\n def insert(self,theLink): # insert link, in order\n key = theLink.getKey()\n self.previous = None # start at self.first\n current = self.first # until end of list,\n while( current != None and key > current.getKey() ): # or current > key,\n self.previous = current \n current = current.next # go to next item\n if(self.previous==None): # if beginning of list,\n self.first = theLink\n else: # not at beginning,\n self.previous.next = theLink\n theLink.next = current # new link --> current\n\n def delete(self,key): # delete link\n # (assumes non-empty list)\n self.previous = None # start at self.first\n current = self.first # until end of list,\n while( current != None and key != current.getKey() ): # or key == current,\n self.previous = current\n current = current.next # go to next link\n if(self.previous==None):\n self.first = self.first.next\n else:\n self.previous.next = current.next \n\n def find(self,key): # find link\n current = self.first # start at self.first\n # until end of list,\n while(current != None and current.getKey() <= key): # or key too small,\n if(current.getKey() == key):# is this the link?\n return current # found it, return link\n current = current.next # go to next item\n return None # didnt find it\n\n def displayList(self):\n print 'List (self.first-->last): ',\n current = self.first # start at beginning of list\n while(current != None): # until end of list,\n current.displayLink() # print data\n current = current.next # move to next link\n print ''\n\nclass HashTable:\n def __init__(self,size):\n self.hashArray = [] # array is the hash table\n for i in range(size):\n self.hashArray.append(SortedList())\n self.arraySize = size\n self.nonItem = None # for deleted items\n\n def displayTable(self):\n print 'Table: ',\n for j in range(self.arraySize):\n print j, \n self.hashArray[j].displayList()\n\n def hashFunc(self,key):\n return key % self.arraySize\n\n def insert(self,theLink):\n key = theLink.getKey()\n hashVal = self.hashFunc(key)\n self.hashArray[hashVal].insert(theLink)\n\n def delete(self,key): # delete a DataItem\n hashVal = self.hashFunc(key) # hash the key\n self.hashArray[hashVal].delete(key) # delete link\n\n def find(self,key): # find link\n hashVal = self.hashFunc(key)# hash the key\n theLink = self.hashArray[hashVal].find(key) # get link\n return theLink # return link\n\nkeysPerCell = 100 \nprint 'Enter size of hash table: ',\nsize = int(raw_input())\nprint 'Enter initial number of items: ',\nn = int(raw_input()) # make table\ntheHashTable = HashTable(size)\nimport random\nfor j in range(n): # insert data\n aKey = int(random.random() * 2 * size)\n aDataItem = Link(aKey) \n theHashTable.insert(aDataItem)\n\nwhile(True):\n print 'Enter self.first letter of show, '\n print 'insert, find, delete, or show: ',\n choice = raw_input()\n if choice == 's':\n theHashTable.displayTable()\n elif choice == 'i':\n print 'Enter value to key to insert: '\n value = int(raw_input())\n aDataItem = Link(aKey)\n theHashTable.insert(aDataItem)\n elif choice == 'f':\n print 'Enter key value to find: ',\n value = int(raw_input())\n aDataItem = theHashTable.find(aKey)\n if(aDataItem != None):\n print 'Found ' , aKey\n else:\n print 'Could not find ' , aKey\n\n elif choice=='d':\n print 'Enter key value to delete: ',\n value = int(raw_input())\n theHashTable.delete(value)\n else:\n print 'Invalid entry'\n",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": "*"
},
{
"cell_type": "code",
"collapsed": false,
"input": "",
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}
|
