Question: I need to implement a hashset in java that can handle collisions with separate chaining. For the hash method i can use the hashCode method
I need to implement a hashset in java that can handle collisions with separate chaining. For the hash method i can use the hashCode method of the stored object. The hashset does not need to resize dynamically. I should use a code skeleton that implements the hashset with arrays.
| 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 implements Set { | |
| private List[] table; | |
| /** | |
| * 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. | |
| */ | |
| 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!"); | |
| } | |
| } |
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
