Question

Title: Implementation of chained hashing in Java or Python

Description:

1. Implement a double linked list with a procedure for adding list elements.
2. Implement a hash table using chaining and the linked list discussed above.
   1. Use Array size m = 7
   2. A hash function of: h = k mod 7
3. Insert 100 random key values into the table. Key values should be between 0 and 99.
4. Implement a Search procedure that tells whether a particular key value is in the hash table.
5. Search for key values between 0 to 10 in the hash table, and print out whether they were found.

You might find the following useful in doing this lab:

• Chapter 11 of your textbook
• The Chapter 11 PowerPoint slides in Blackboard
• The pseudocode below

Example pseudocode:

Create HashTable (T)

Do 100 times:

   CHAINED-HASH-INSERT(T, randomKeyValue);

End Do

Do for x between 0 and 10:

If (CHAINED-HASH-SEARCH(T,x))

PRINT(Key value x found in Hash Table);

Else

PRINT(Key value x not found in Hash Table);

end If

End Do

Answer 1

 import random class Node: def __init__(self, next=None, prev=None, key=None): self.next = next # reference to next node in DLL self.prev = prev # reference to previous node in DLL self.key = key class DoublyLinkedList: def __init__(self): self.head = None def insert(self, key): if self.head is None: self.head = Node(key=key) else: node = Node(next = self.head, key=key) self.head = node class HashTable: def __init__(self, size): self.size = size self.table = [DoublyLinkedList() for _ in range(size)] def insert(self, key): hash_val = key%self.size if not self.search(key): self.table[hash_val].insert(key) def search(self, key): hash_val = key%self.size node = self.table[hash_val].head while(node is not None): if key==node.key: return True node = node.next return False table = HashTable(7) for i in range(100): table.insert(random.randint(0, 99)) for i in range(10): print(f"Found {i} in table" if table.search(i) else f"Not Found {i}")

: class Node: definit (self, next=None, prev=None, key=None): self.next = next # reference to next node in DLL self.prev = prev # reference to previous node in DLL self.key = key : class DoublyLinkedList: def init (self): self.head = None def insert(self, key): if self. head is None: self. head = Node (key=key) else: node = Node (next = self.head, key=key) self. head = node : class HashTable: def init__(self, size): self.size = size self.table = [DoublyLinkedList() for in range (size) ] def insert(self, key): hash val = key%self.size if not self.search(key): self. table[hash val].insert(key) def search(self, key): hash val = key%self.size node = self.table[hash val].head while(node is not None): if key==node.key: return True node = node.next return false

table = HashTable(7) for i in range (100): table.insert (random.randint(0, 99)) for i in range (10): print(f"Found {i} in table" if table. search(i) else f"Not Found {i}") Not Found o Not Found 1 Found 2 in table Found 3 in table Found 4 in table Not Found 5 Found 6 in table Found 7 in table Not Found 8 Found 9 in table

Reply in case of any doubts