How to implement hashset. I need help understanding how i should implement the test //TODO in the Hashset class. NO new methods should be added in Hashset
Set.java
/**
* An interface describing a generic set. Duplicates are not allowed.
*
*/
public interface Set {
/**
* Adds the given element to the set.
*
* Complexity: O(1) expected time.
*
* @param elem An element to add to the set.
* @return true if the set did not contain the element, otherwise false.
*/
boolean add(T elem);
/**
* Removes the given element from the dictionary, if it is present.
*
* Complexity: O(1) expected time.
*
* @param elem An element to remove from the set.
* @return true if the set contained the element, false otherwise.
*/
boolean remove(T elem);
/**
* Check if an element is in the Set.
*
* Complexity: O(1) expected time.
*
* @param elem An element to look for.
* @return true if the element is in the set, false otherwise.
*/
boolean contains(T elem);
/**
* Returns the number of elements in this set.
*
* Complexity: O(1) expected time.
*
* @return The amount of elements in this set.
*/
int size();
}
HashSet.java
import java.util.LinkedList;
import java.util.List;
/**
* A hash table-based implementation of the Set interface.
*
*/
public class HashSet implements Set {
private List[] table;
private int capacity;
private int size;
private int index;
private class Node {
private T data;
private Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
/**
* Creates a hash table with the given capacity (amount of buckets).
*
* @throws IllegalArgumentException if capacity <= 0.
*/
public HashSet(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException(
"capacity must be a positive, non-zero value! Provided: " + capacity);
}
// We want to do the following:
//
// table = new LinkedList[capacity];
//
// However, that won't compile ("generic array creation")
// since Java generics and arrays don't get along very well.
// Instead we need to do the following:
//
// table = new LinkedList[capacity];
//
// The above will compile, but with a warning. The proper
// approach is to document why the warning can be safely
// ignored and then suppress the warning. Thus:
/*
* This array will contain only LinkedList
* instances, all created in the add method. This
* is sufficient to ensure type safety.
*/
@SuppressWarnings("unchecked") // for this declaration only
List[] t = new LinkedList[capacity];
table = t;
}
/**
* Adds the given element to the set.
*
* Complexity: O(1) expected time.
*
* @param elem An element to add to the set.
* @return true if the set did not contain the element, otherwise false.
*/
@Override
public boolean add(T elem) {
//TODO
}
/**
* Removes the given element from the dictionary, if it is present.
*
* Complexity: O(1) expected time.
*
* @param elem An element to remove from the set.
* @return true if the set contained the element, false otherwise.
*/
@Override
public boolean remove(T elem) {
//TODO
}
/**
* Removes the given element from the dictionary, if it is present.
*
* Complexity: O(1) expected time.
*
* @param elem An element to remove from the set.
* @return true if the set contained the element, false otherwise.
*/
@Override
public boolean remove(T elem) {
//TODO
}
/**
* Check if an element is in the Set.
*
* Complexity: O(1) expected time.
*
* @param elem An element to look for.
* @return true if the element is in the set, false otherwise.
*/
@Override
public boolean contains(T elem) {
//TODO
}
/**
* Returns the number of elements in this set.
*
* Complexity: O(1) expected time.
*
* @return The amount of elements in this set.
*/
@Override
public int size() {
return size;
}
}
