SHARE
TWEET

Untitled

a guest Aug 26th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class QuadraticHashTable():
  2.     """Is a child class of OpenAddressHashTable.
  3.     If a collision then uses a quadratic probing function to find a free slot
  4.     >>> hash_table = QuadraticHashTable(11)
  5.     >>> hash_table.store('Dianna')
  6.     >>> hash_table.store('Bobby')
  7.     >>> hash_table.store('Dirk')
  8.     >>> hash_table.store('Darlene')
  9.     >>> hash_table.store('Paul')
  10.     >>> hash_table.store('Paula')
  11.     >>> hash_table.store('David')
  12.     >>> hash_table.store('Harry')
  13.     >>> print(hash_table)
  14.     QuadraticOpenAddressHashTable:
  15.     slot        0 = David
  16.     slot        1 = Darlene
  17.     slot        2 = Paul
  18.     slot        3 = -
  19.     slot        4 = Paula
  20.     slot        5 = Harry
  21.     slot        6 = Dirk
  22.     slot        7 = -
  23.     slot        8 = -
  24.     slot        9 = Dianna
  25.     slot       10 = Bobby
  26.     n_slots = 11
  27.     n_items in table = 8
  28.     Load factor =  0.727
  29.     <BLANKLINE>
  30.     >>> 'Harry' in hash_table
  31.     True
  32.     >>> 'Paul' in hash_table
  33.     True
  34.     >>> 'Paula' in hash_table
  35.     True
  36.     >>> 'David' in hash_table
  37.     True
  38.     >>> 'Bobby' in hash_table
  39.     True
  40.     >>> 'Dianna' in hash_table
  41.     True
  42.     >>> 'Dirk' in hash_table
  43.     True
  44.     >>> 'Darlene' in hash_table
  45.     True
  46.     >>> 'Dingus' in hash_table
  47.     False
  48.  
  49.     """
  50.  
  51.     def __init__(self, slots=11):
  52.         """
  53.         Creates a new hashtable with a number of slots (default: 10).
  54.         Remember we can't have a load factor greater than 1 for an open hash...
  55.         """
  56.         self._data = [None for i in range(slots)]
  57.         self.n_slots = slots
  58.         self.n_items = 0
  59.  
  60.     def _next_free_slot(self, first_hash):
  61.         """
  62.         Keeps incrementing hash index until an empty slot is found.
  63.         Then returns the index of that slot.
  64.         Used by the store method to help deal with a collisions.
  65.         Note: this method isn't useful in __contains__ but you shoul
  66.               follow a similar series of probing there.
  67.         """
  68.         curr_index = first_hash
  69.         try_number = 0
  70.         tried = []
  71.         #print self._data
  72.         while self._data[curr_index] is not None:
  73.             tried.append(curr_index)
  74.             try_number += 1
  75.             if try_number > self.n_slots // 2:
  76.                 #print self._data
  77.                 print('Size = ' + str(self.n_slots))
  78.                 print('Number of items = ' + str(self.n_items))
  79.                 print('Failed to find an empty slot...')
  80.                 print('Try number = ' + str(try_number))
  81.                 print('List of tried slots = ' + str(tried))
  82.                 print('Current table = ' + str(self._data))
  83.                 print('*** Failed to find an empty slot!!!! ')
  84.                 print('*** This can happen with quadratic probing')
  85.                 print('*** if the table is over half full')
  86.                 raise ValueError('Failed to find an empty slot!!!!')
  87.             else:
  88.                 curr_index = (first_hash + try_number**2) % self.n_slots
  89.         return curr_index
  90.  
  91.     def store(self, item):
  92.         """Stores an item in the hashtable."""
  93.         if self.n_slots == self.n_items:
  94.             #Argh - crash, who made the hashtable too small?
  95.             print(self._data)
  96.             print('Size = ' + str(self.n_slots))
  97.             print('Slots used = ' + str(self.n_items))
  98.             print("Hash table is full!!!! You eeediot")
  99.             print("A good Hasher would have resized the hash table by now!")
  100.             raise ValueError("Hash table is full!!!!")
  101.         # **************************************************
  102.         # ---start student section---
  103.         index_initial = self._hash(item)
  104.         index_current = self._hash(item)
  105.         i_counter = 0
  106.         if not self.__contains__(item):
  107.             slot_found = False
  108.             while slot_found == False:
  109.                 if self._data[index_current] == None:
  110.                     self._data[index_current] = item
  111.                     slot_found = True
  112.                 else:
  113.                     index_current = index_initial + i_counter^2
  114.                     i_counter += 1
  115.                     if index_current == self.n_slots:
  116.                         index_current = 1
  117.         # ===end student section===
  118.         self.n_items += 1
  119.  
  120.     def _hash(self, item):
  121.         """Computes the hash of an item."""
  122.         return nice_hash(item) % self.n_slots
  123.  
  124.     def __contains__(self, item):
  125.         """
  126.         Checks to see if an item is stored within the hashtable.
  127.         Returns True if it is, otherwise it returns False.
  128.         Note: The function should give up and return False if
  129.         the try_number reaches the number of slots in the table.
  130.         At this stage we definitely know we are in a never ending
  131.         cycle and will never find the item...
  132.         You can call this method using Python's 'in' keyword:
  133.             ht = HashTable()
  134.             ...
  135.             if 'foo' in ht:
  136.                 ...
  137.         """
  138.         first_hash = self._hash(item)
  139.         i_counter = 0
  140.         try_number = 0
  141.         current_index = first_hash
  142.         # ---start student section---
  143.         first_hash = self._hash(item)
  144.         have_wrapped = False
  145.         if self._data[first_hash] == item:
  146.             return True
  147.         else:
  148.             current_index = first_hash
  149.             while self._data[current_index] is not None:
  150.                 if self._data[current_index] == item:
  151.                     # horay we found it
  152.                     return True
  153.                 if (current_index == first_hash) and have_wrapped:
  154.                     # back to original hash and didn't find item
  155.                     # phew - the hashtable is full!
  156.                     return False
  157.                 if current_index == (self.n_slots -1):
  158.                     # wrap back to start of hash table
  159.                     current_index = 0
  160.                     have_wrapped = True
  161.                 else:
  162.                     current_index = (first_hash + i_counter^2) % self.n_slots      
  163.         # ===end student section===
  164.  
  165.     def __str__(self):
  166.         output = 'QuadraticOpenAddressHashTable:\n'
  167.         for i in range(self.n_slots):
  168.             output += f'slot {i:8} = '
  169.             item = self._data[i]
  170.             if item == None:
  171.                 output = output + '-'
  172.             else:
  173.                 output = output + str(item)
  174.             output += '\n'
  175.         load_factor = float(self.n_items) /self.n_slots
  176.         output += f'n_slots = {self.n_slots}\n'
  177.         output += f'n_items in table = {self.n_items}\n'
  178.         output += f'Load factor = {load_factor:6.3f}\n'
  179.         return output
  180.  
  181.     def __repr__(self):
  182.         return str(self)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top