{
 "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": {}
  }
 ]
}