Question: In class we implemented a hash table for a set, with the buckets consisting of linked chains of nodes. Add the following method to the
In class we implemented a hash table for a set, with the buckets consisting of linked chains of nodes. Add the following method to the file:
boolean remove (T item); Then test your code using HashSets. The output should look like this:
0cQ 1Im 2e 3f
4 CyU 5 zDV 6 EiW 7jF 8bP
Does the set contain 'e'? yes Does the set contain 'a'? no After removing e, c, y, W, and y:
0Q 1Im 2 3f 4CU 5 zDV 6Ei 7jF 8bP
/*
* interface for a set
*
* unordered collection, no duplicates allowed
*/
public interface Set
{
/*
* adds item to set if not already present
*
* returns true if item successfully added, false if not
*
*/
boolean add (T item);
T remove();
boolean remove (T item);
T get();
boolean contains (T item);
int size();
String toString();
}
/*
* implements a hash table using chains of nodes for the buckets
*/
public class HashSet
{
private class Node
{
private T data;
private Node next;
public Node(T item)
{
data = item;
next = null;
}
public String toString()
{
return "" + data;
}
}
public static final int DEFAULT_CAPACITY = 9;
private Node[] hashtable;
private int size;
private int items;
public HashSet ()
{
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public HashSet (int capacity)
{
hashtable = (Node[]) new HashSet.Node[capacity];
size = capacity;
items = 0;
}
public boolean add (T item)
{
checkForNull(item);
int index = getIndex(item);
Node current = hashtable[index];
if (current == null)
{
hashtable[index] = new Node(item);
items++;
return true;
}
while (current.next!= null)
{
if (current.data.equals(item))
{
return false;
}
current = current.next;
}
if (current.data.equals(item))
{
return false;
}
current.next = new Node(item);
items++;
return true;
}
public boolean remove (T item)
{
// to be implemented
return false;
}
public T remove ()
{
return null;
}
public T get()
{
boolean filled = false;
int random = 0;
while (!filled)
{
random = (int)(Math.random() * items);
if (hashtable[random] != null)
{
filled = true;
}
}
return hashtable[random].data;
}
public boolean contains(T item)
{
int index = getIndex(item);
Node current = hashtable[index];
if (current == null)
{
return false;
}
while (current.next != null)
{
if (current.data.equals(item))
{
return true;
}
current = current.next;
}
if (current.data.equals(item))
{
return true;
}
return false;
}
public int size()
{
return size;
}
public String toString()
{
if (size == 0)
{
return "[]";
}
String h = "";
for (int i = 0; i < size; i++)
{
Node current = hashtable[i];
if (current == null) h+= i + "\t" + " " + " ";
else
{
h+= i + "\t" + current + " ";
while (current.next != null)
{
current = current.next;
h+= current + " ";
}
h+= " ";
}
}
return h;
}
private void checkForNull(T item)
{
if (item == null)
{
throw new IllegalArgumentException("null not a possible value!");
}
}
private int getIndex(T item)
{
int index = item.hashCode() % size;
if (index < 0)
{
index += size;
}
return index;
}
}
/*
* driver program for testing LinkedHashSet
*/
public class HashSets
{
public static void main (String [] args)
{
Set
char [] toAdd = {'C', 'b', 'c', 'Q', 'z', 'D', 'E', 'P', 'j', 'F',
'E', 'I', 'y', 'f', 'i', 'U', 'V', 'm', 'e', 'W'};
for (int i = 0; i < toAdd.length; i++)
{
letters.add(toAdd[i]);
}
System.out.println(" " + letters);
System.out.println("Does the set contain 'e'? " +
(letters.contains('e') ? "yes" : "no"));
System.out.println("Does the set contain 'a'? " +
(letters.contains('a') ? "yes" : "no"));
System.out.println("After removing e, c, y, W, and y: ");
letters.remove('e');
letters.remove('c');
letters.remove('y');
letters.remove('W');
letters.remove('y');
System.out.println(letters);
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help