# Direct address hash table

Note: I do know that Python libraries provide better solutions. This implementation has been done to practice python, data structures and Algorithms.

This is a implementation of Direct-address hash tables. It simply makes a list of size 5000000 and initializes each spot with an empty doubly linked list (for chaining).

Feel free to make any suggestions about syntax, logic, or simply anything that you think i should become aware of.

Note: Max number of elements in each table is 5000000, as direct addressing doesn't do any good when table is too big and sorting will be too crazy (I Think :-))

Methods:

dt_insert(value) - inserts and chains
dt_search(value) - search in table and subsequent chain
dt_delete(value) - delete from table and subsequent chain
hash_to_index(value) - used in other methods, only to find the index of the table that value belongs to, and assign that value as key
dump_table() - see everything inserted in table and the chains


from DoublyLinkedList import DoublyLinkedList

class Node:
def __init__(self, key = None, value = None):
self.key = key
self.value = value

class DirectTable:
def __init__(self):
self.list = [None] * 5000000

# take care of chaining
def dt_insert(self, value):
node = self.hash_to_index(value)
position = self.list[node.key]
# if the index is None create a linked list for chaining
if position is None:
# chain
self.list[node.key] = position

def dt_search(self, value):
node = self.hash_to_index(value)
position = self.list[node.key]
if position is not None:
# search in the chain
result = position.list_search(node.value)
print(result.data)
return result.data
return False

def dt_delete(self, value):
node = self.hash_to_index(value)
position = self.list[node.key]
if position is not None:
# delete in the chain
result = position.list_delete(node.value)
return result
return False

def hash_to_index(self, value):
node = Node()
if str(value).isdigit():

if value < 5000000:
node.value = value
node.key = value
return node
# if its a char
else:
key = ord(value)
if key < 5000000:
node.value = value
node.key = key
return node
# dump the table
def dump_table(self):
for i in self.list:
if i is not None:
temp = i.dump()
for j in temp:
print(j)


main:

from DirectTable import DirectTable

def main():
my_table = DirectTable()
my_list = [1, 'a', 7, 'ab', 8, 20]

for i in my_list:
my_table.dt_insert(i)

my_table.dump_table()
print("---------------")
my_table.dt_search('a')
print("---------------")
print(my_table.dt_delete('a'))
print("---------------")
my_table.dump_table()
print("---------------")
print(my_table.dt_delete(10))

if __name__ == "__main__":
main()


class Node:
def __init__(self, value, key):
self.data = value
self.key = key
self.next = None
self.prev = None

def __init__(self):
self.head = None # no need for tail as always the next pointer of last object will remain as none

def add_node(self, value=None, key=None):
node = Node(value, key)   # make new node
# self.head is either pointing to None or the first object, make the next pointer of the new node point to same
# if head is not null, than there is other items in the list
if self.head is not None:
# make the prev pointer of the node that head is pointing to point to the new node
# make the head point to the new node
# make prev pointer of new node, point to head

def list_search(self, value):
# start from the head
# do it as long as there is no pointer and value not foun
while p is not None:
# make p reference to next node
if p.data is not None:
if p.data == value:
return p
if p.next is not None:
p = p.next
else:
return False

def list_delete(self, value):
# find the node in the linked list
p = self.list_search(value)
# if what back pointer points to is not head
if p is not False:
if p.prev is not None and p != self.head:
# make the next pointer of the node behind, point to the back of the node ahead
p.prev.next = p.next
else:
# if the back node is the head, make it point to the node after
# if there is a node after
if p.next is not None:
# make the the back pointer of the node ahead point to the front pointer of the node behind
p.next.prev = p.prev
return True
else:
return False

def dump(self):