Question

Instead of using a linked list to resolve collisions, as in separate chaining, use
a binary search tree. That is, create a hash table that is an array of trees. To
display a small tree-based hash table, you could use an inorder traversal of
each tree. The advantage of a tree over a linked list is that it can be searched
in O(logN) instead of O(N) time. This time savings can be a significant
advantage if very high load factors are encountered. Checking 15 items takes
a maximum of 15 comparisons in a list but only 4 in a tree. Duplicates can
present problems in both trees and hash tables, so add some code that
prevents a duplicate key from being inserted in the hash table. (Beware: The
find()method in Tree assumes a non-empty tree.) To shorten the listing for
this program, you can forget about deletion, which for trees requires a lot of code. Write algorithm for the scenario.
#java and with comments

Answer 1

class Node // bst node
{
int key;
int value;

Node left,right;
  
public Node(int key,int value) // constructer
{
this.key = key;
this.value = value;
}
}
  
class Hash // class for hash table
{
private ArrayList<Node> bucket; // chains array
  
private int total;
  
private int size; // current size

public Hash()
{
bucket = new ArrayList<>();
total = 10;
size = 0;
for (int i = 0; i < total; i++)
bucket.add(null);
}
  
public int GetSize()
   {
   return size;
   }
  
private int GetId(int key) // hash function to find id
{
int id = key % total;
return id;
}
  
public Node get(int Key) // get value for a particular key
{
int id = GetId(Key);
Node head = bucket.get(id);
  
while (head != null) // search key
{
if (head.key==(Key))
return head;
if(head.key<Key)head=head.right;
else head=head.left;
}
return null;
}
  
public void add(int key,int value)
{
int id = GetId(key);
Node head = bucket.get(id);

while (head != null) // check if key is already present
{
if (head.key==(key))
{
head.value = value;
return;
}
if(head.key<key)head=head.right;
else head=head.left;
}
  
// Insert key in chain
size++;
head = bucket.get(id);
Node newNode = new Node(key, value);
if(head.key>key)
newNode.right = head;
else newNode.left = head;
bucket.set(id, newNode);
  

if ((1.0*size)/total >= 0.8) // double hash table size
{
ArrayList<Node> temp = bucket;
bucket = new ArrayList<>();
total = 2 * total;
size = 0;
for (int i = 0; i < total; i++)
bucket.add(null);
  
for (Node headNode : temp)
{
if(headNode!=null)
{
Queue<Node> q = new LinkedList<>(); // traverse bst
q.add(headNode) ;
while (q.size() != 0)
{
Node x = q.peek() ;
q.remove() ;
add(x.key, x.value);
if(x.left!=null)q.add(x.left);
if(x.right!=null)q.add(x.right);
}
}
}
}
}
  
public void printHash() // print the haash table
{
ArrayList<Node> temp = bucket;
System.out.println("Key"+" "+ "Value");
for (Node headNode : temp)
{
if(headNode!=null)
{
Queue<Node> q = new LinkedList<>();
q.add(headNode) ;
while (q.size() != 0)
{
Node x = q.peek() ;
q.remove() ;
System.out.println(x.key+" "+ x.value);
if(x.left!=null)q.add(x.left);
if(x.right!=null)q.add(x.right);
}
}
}
}
  
  
}