{
 "metadata": {
  "name": "",
  "signature": "sha256:2ea25d6b8d9f93ae0488601c3ca91103c231ea11e5b2efa6b43dd14ae7e00851"
 },
 "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": [
      " \n",
      "class DataItem:\n",
      "    def __init__(self,ii):\n",
      "        self.iData = ii\n",
      "\n",
      "    def getKey(self):\n",
      "        return self.iData\n",
      "\n",
      "class 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",
      "\n",
      "print 'Enter size of hash table: ',\n",
      "size = int(raw_input())\n",
      "print 'Enter initial number of items: ',\n",
      "n = int(raw_input()) # make table\n",
      "theHashTable = HashTable(size)\n",
      "keysPerCell = 10\n",
      "import random\n",
      "for j in range(n): # insert data\n",
      "    aKey = int(random.random() * keysPerCell * size)\n",
      "    aDataItem = DataItem(aKey)      \n",
      "    theHashTable.insert(aDataItem)\n",
      "\n",
      "while(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"
       ]
      }
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 11.2  Page no: 546"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class DataItem:\n",
      "    def __init__(self,ii):\n",
      "        self.iData = ii\n",
      "\n",
      "    def getKey(self):\n",
      "        return self.iData\n",
      "\n",
      "class 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",
      "\n",
      "print 'Enter size of hash table: ',\n",
      "size = int(raw_input())\n",
      "print 'Enter initial number of items: ',\n",
      "n = int(raw_input()) # make table\n",
      "theHashTable = HashTable(size)\n",
      "import random\n",
      "for j in range(n): # insert data\n",
      "    aKey = int(random.random() * 2 * size)\n",
      "    aDataItem = DataItem(aKey)      \n",
      "    theHashTable.insert(aKey, aDataItem)\n",
      "\n",
      "while(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": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter size of hash table: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " Enter initial number of items: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      }
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 11.3  Page no : 555"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class 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",
      "\n",
      "class 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",
      "\n",
      "class 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",
      "\n",
      "keysPerCell = 100 \n",
      "print 'Enter size of hash table: ',\n",
      "size = int(raw_input())\n",
      "print 'Enter initial number of items: ',\n",
      "n = int(raw_input()) # make table\n",
      "theHashTable = HashTable(size)\n",
      "import random\n",
      "for j in range(n): # insert data\n",
      "    aKey = int(random.random() * 2 * size)\n",
      "    aDataItem = Link(aKey)      \n",
      "    theHashTable.insert(aDataItem)\n",
      "\n",
      "while(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": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}