python3 HashTableSolutionmain.pyfrom ChainingHashTable impor.pdf

python3 HashTableSolutionmain.pyfrom ChainingHashTable impor.pdf

• 1.
  python3 HashTable Solution main.py from ChainingHashTableimport ChainingHashTable def TestHashTable(): h_table = ChainingHashTable(5) print("Hash Table:") print(h_table) print("Size:",len(h_table)) h_table[10] = "Mouse" h_table[5] = "Rat" h_table[2] = "Dog" h_table[1] = "Cat" h_table[3] = "Rhino" h_table[9] = "Eagle" h_table[14] = "Condor" h_table[4] = "Hawk" print() print("Hash Table:") print(h_table) print("Size:",len(h_table)) print() for i in range(10): if i in h_table: print(h_table[i],end = " ") print() del h_table[5] del h_table[2] del h_table[9] h_table[4] = "Falcon" print() print("Hash Table:") print(h_table)
• 2.
  print("Size:",len(h_table)) def main(): TestHashTable() main() ChainingHashTable.py from OrderedListimport OrderedList from Node import Node class ChainingHashTable: def __init__(self, size): self.__size = size self.__count = 0 self.__slots = [OrderedList()] * self.__size self.__deleted = "0" def hash_function(self, key, size): return key % size def rehash(self, old_hash,size): return (old_hash + 1) % size def get_data(self): return self.__count def getitem(self, key): start_slot = self.hash_function(key,len(self.__slots)) position = start_slot while self.__slots[position] != None: if self.__slots[position] == key: return self.__data[position] else: position = self.rehash(position, len(self.__slots)) if position == start_slot: return None return None def __getitem__(self, key): return self.get(key)
• 3.
  def put(self, key,value): hash_value = self.hash_function(key,len(self.__slots)) if self.__slots[hash_value] == None or self.__slots[hash_value] == self.__deleted: self.__slots[hash_value] = key self.__data[hash_value] = data elif self.__slots[hash_value] == key: self.__data[hash_value] = data else: next_slot = self.rehash(hash_value, len(self.__slots)) while self.__slots[next_slot] != None and self.__slots[next_slot] != self.__deleted and self.__slots[next_slot] != key: next_slot = self.rehash(next_slot,len(self.__slots)) if next_slot == hash_value: return if self.__slots[next_slot] == None or self.__slots[next_slot] == self.__deleted: self.__slots[next_slot] = key self.__data[next_slot] = data else: self.__data[next_slot] = data def __setitem__(self, key, value): return self.put(key, value) def delete(self, key): start_slot = self.hash_function(key, len(self.__slots)) position = start_slot key_in_slot = self.__slots[position] while key_in_slot != None: if key_in_slot == key: self.__slots[position] = self.deleted self.__data[position] = self.deleted return None else:
• 4.
  position = self.rehash(position,len(self.__slots)) key_in_slot = self.__slots[position] if position == start_slot: return None def __delitem__(self, key): return self.delete(key) def __len__(self): count = 0 for value in self.__slots: if value != None and value != self.__deleted: count += 1 return count def __contains__(self, key): return self.getitem(key) != None def __str__(self): count = 0 for x in self.__slots: print(count) count += 1 return str("str") LinkedListIterator.py class LinkedListIterator: def __init__(self, head): self.__current = head def __next__(self): if self.__current == None: raise StopIteration else: item = self.__current.get_data() self.__current = self.__current.get_next() return item Node.py # class Node which stores an item and a reference to an item of the same type
• 5.
  class Node: def __init__(self,data, key): self.__data = data self.__next = None self.__key = key def get_data(self): return self.__data def get_next(self): return self.__next def set_data(self, new_data): self.__data = new_data def set_next(self, new_next): self.__next = new_next def get_key(self): return self.__key def set_key(self, new_key): self.__key = new_key OrderedList.py from Node import Node from LinkedListIterator import LinkedListIterator class OrderedList: def __init__(self): self.__head = None self.__count = 0 def is_empty(self): return self.__count == 0 def size(self): return self.__count def add(self,item): new_node = Node(item) curr = self.__head prev = None
• 6.
  stop = False whilecurr != None and not stop: if item < curr.get_key(): stop = True else: prev = curr curr = curr.get_next() new_node.set_next(curr) if prev == None: self.__head = new_node else: prev.set_next(new_node) self.__count += 1 def search(self,item): curr = self.__head while curr != None: if curr.get_key() == item: return True elif curr.get_key() > item: return False else: curr = curr.get_next() return False def remove(self,item): curr = self.__head prev = None while curr != None and curr.get_key() != item: prev = curr curr = curr.get_next() if prev == None: self.__head = curr.get_next() else: prev.set_next(curr.get_next()) self.__count -= 1 def __iter__(self):
• 7.
  return LinkedListIterator(self.__head)