Question
Implement hashtable interfaces set.java Hash tables are built into Java in the form of the classes HashMap, Hashtable (which is almost identical to HashMap) and
Implement hashtable interfaces set.java
Hash tables are built into Java in the form of the classes HashMap, Hashtable (which is almost identical to HashMap) and HashSet, together with the methods equals and hashCode in the Object class. To use these efficiently one has to understand how a hash table works. That's what we'll learn in this assignment.
You will implement a hash table that functions as a set (so, HashSet), that is to say, it can hold only unique values. The interface is described below (and available in Set.java).
This assignment has some unexpected complications because arrays and generics work pretty poorly together in Java. There are two (reasonably good) solutions to this problem, and these are outlined in the next two subsections. Whichever option you pick, the following requirements are placed on your implementation:
- To implement your hash method, use the hashCode method of the stored object. Every object in java has the hashCode method, as it is defined in Object, and every class extends Object.
- Your implementation must handle hash collisions. That is to say it should be possible to store two objects that are not equal, but have the same hash.
- Your implementation does not have to resize dynamically (i.e. the amount of buckets may be constant).
- Work from the code skeleton in src/HashSet.java.
Option 1
Option 1 is to avoid arrays and use an ArrayList instead. Then you can declare and create the hash table in the following way:
ArrayList> table = new ArrayList<>();
Option 2
If you'd rather use arrays, for efficiency-reasons, some more unexpected issues pop up. You can't actually create an array of generic lists in a type-safe fashion in Java. The following, seemingly natural code:
new LinkedList[size];
doesn't work. HashSet.java is a skeleton that shows how you can get around this.
set class:
public interface Set
boolean add(T elem);
boolean remove(T elem);
boolean contains(T elem);
int size(); }
import java.util.LinkedList; | |
import java.util.List; | |
/** | |
* A hash table-based implementation of the Set interface. | |
* | |
* @author YOUR NAME HERE | |
* @version DATE | |
*/ | |
public class HashSet | |
private List | |
/** | |
* 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 | |
// | |
// 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 | |
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. | |
*/ | |
public boolean add(T elem) { | |
throw new UnsupportedOperationException("Not implemented!"); | |
} | |
/** | |
* 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. | |
*/ | |
public boolean remove(T elem) { | |
throw new UnsupportedOperationException("Not implemented!"); | |
} | |
/** | |
* 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. | |
*/ | |
public boolean contains(T elem) { | |
throw new UnsupportedOperationException("Not implemented!"); | |
} | |
/** | |
* Returns the number of elements in this set. | |
* | |
* Complexity: O(1) expected time. | |
* | |
* @return The amount of elements in this set. | |
*/ | |
public int size() { | |
throw new UnsupportedOperationException("Not implemented!"); | |
} | |
} |
please help me with the "not implemented" methods.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started