HashTable Implementation with JUNIT testing

Question

I have written a hashtable that implements a set interface. With JUNIT all my test goes through, however I am unsure if they are written correctly based on what their description is. Down here I have The test class, set interface class and HashSet class. Please Look at the two test that is written in the testclass that includes //TESTT and tell me if they are correctly written

import org.junit.Test;
import org.junit.Before;
import static org.junit.Assert.*;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.CoreMatchers.*;
import java.util.Arrays;
/**
 * Test for the HashSet implementation of the Set interface. Runs both the
 * SetTest tests, as well as tests specific to hashing.
 *
 * This test class mostly contains only hash collision tests.
 */
public class HashSetTest extends SetTest {
 private Set<SingleHashUnequal> set;
 private SingleHashUnequal[] uniqueObjsWithEqualHashes;
 /**
 * Returns an implementation of Set that can hold at least 'minCapacity'
 * Integers.
 *
 * @param minCapacity The least amount of elements the Set must be able to
 * hold.
 * @return An implementation of Set.
 */
 @Override
 protected Set<Integer> getIntegerSet(int minCapacity) {
 return new HashSet<Integer>(minCapacity);
 }
 @Override
 @Before
 public void setUp() {
 // We are overriding the setUp method of SetTest, so we need to call
 // it explicitly to not break everything.
 super.setUp();
 int numDummies = 10;
 uniqueObjsWithEqualHashes = new SingleHashUnequal[numDummies];
 set = new HashSet<SingleHashUnequal>(numDummies * 2);
 for (int i = 0; i < numDummies; i++) {
 SingleHashUnequal dummy = new SingleHashUnequal();
 set.add(dummy);
 uniqueObjsWithEqualHashes[i] = dummy;
 }
 }
 @Test
 public void containsIsFalseWhenElementIsNotInSetAndHashCollides() {
 // Test that contains is false when the set contains some other element
 // with the same hash
 // Arrange
 SingleHashUnequal elem = new SingleHashUnequal();
 // Act
 boolean contained = set.contains(elem);
 // Assert
 assertThat(contained, is(false));
 }
 @Test
 public void containsIsTrueForAddedElementsWithEqualHashes() {
 // Arrange
 Arrays
 .stream(uniqueObjsWithEqualHashes)
 // Act
 .map(elem -> set.contains(elem))
 // Assert
 .forEach(contained -> assertThat(contained, is(true)));
 }
 @Test
 public void addIsTrueForUniqueElementsWithEqualHashes() {
 // Arrange
 int capacity = uniqueObjsWithEqualHashes.length;
 Set<SingleHashUnequal> set = new HashSet<SingleHashUnequal>(capacity);
 Arrays
 .stream(uniqueObjsWithEqualHashes)
 // Act
 .map(elem -> set.add(elem))
 // Assert
 .forEach(wasAdded -> assertThat(wasAdded, is(true)));
 }
 @Test
 public void addUniqueElementsWithEqualHashesIncrementsSize() {
 // Arrange
 int capacity = uniqueObjsWithEqualHashes.length;
 Set<SingleHashUnequal> set = new HashSet<SingleHashUnequal>(capacity);
 int expectedSize = 0;
 for (SingleHashUnequal elem : uniqueObjsWithEqualHashes) {
 expectedSize++;
 // Act
 set.add(elem);
 // Assert
 assertThat(set.size(), equalTo(expectedSize));
 }
 }
 @Test
 public void removeUniqueElementsWithEqualHashesDecrementsSize() { //TESTT
 SingleHashUnequal elem = new SingleHashUnequal();
 int expectedSize = set.size();
 // Act
 set.remove(elem);
 // Assert
 assertThat(set.size(), equalTo(expectedSize));
 }
 @Test
 public void removeElementNotInSetWithCollidingHashDoesNotDecreaseSize() { //TESTT
 // Test that removing an element that is not in the set, but has the
 // same hash as some other element in the set, does not decrement size
 SingleHashUnequal elem = new SingleHashUnequal();
 set.remove(elem);
 assertThat(set.size(), equalTo(uniqueObjsWithEqualHashes.length));
 }
 @Test
 public void removeIsFalseWhenElementNotInSetButEqualHashIs() {
 // Test that removing an element that is not in the set, but has the
 // same hash as some other element in the set, returns false
 // Arrange
 SingleHashUnequal elem = new SingleHashUnequal();
 // Act
 boolean removed = set.remove(elem);
 // Assert
 assertThat(removed, is(false));
 }
 /**
 * A helper class for testing hash collisions. Instances equal only
 * themselves, and all instances have the same hashCode.
 */
 private static class SingleHashUnequal {
 private static final int HASH = 0;
 @Override
 public boolean equals(Object o) {
 return this == o;
 }
 @Override
 public int hashCode() {
 return HASH;
 }
 }
}

Hash table:

import java.util.LinkedList;
import java.util.List;
/**
 * A hash table-based implementation of the Set interface.
 *
 */
public class HashSet<T> implements Set<T> {
 private List<T>[] table;
 private int size;
 /**
 * 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);
 }
 @SuppressWarnings("unchecked") // for this declaration only
 List<T>[] t = new LinkedList[capacity];
 table = t;
 size = 0;
 }
 /**
 * Adds the given element to the set.
 * @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) {
 if (elem == null || elem.equals("")){
 return false;
 }
 int hash = Math.abs(elem.hashCode() % table.length);
 if (table[hash]== null){
 table[hash] = new LinkedList<T>();
 table[hash].add(elem);
 size ++;
 return true;
 }
 if (table[hash].contains(elem)){
 return false;
 }else{
 table[hash].add(elem);
 size++;
 return true;
 }
 }
 /**
 * Removes the given element from the dictionary, if it is present.
 * @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) {
 if (elem == null || elem.equals("")){
 return false;
 }
 int hash = Math.abs(elem.hashCode() % table.length);
 if (table[hash] != null && table[hash].contains(elem)){
 table[hash].remove(elem);
 size --;
 return true;
 }else{
 return false;
 }
 }
 /**
 * Check if an element is in the Set.
 * @param elem An element to look for.
 * @return true if the element is in the set, false otherwise.
 */
 @Override
 public boolean contains(T elem) {
 if (elem == null || elem .equals("")){
 return false;
 }
 int hash = Math.abs(elem.hashCode() % table.length);
 if (table[hash] != null && table[hash].contains(elem)){
 return true;
 }else{
 return false;
 }
 }
 /**
 * Returns the number of elements in this set.
 * @return The amount of elements in this set.
 */
 @Override
 public int size() {
 return size;
 }
 }

/**
 * An interface describing a generic set. Duplicates are not allowed.
 */
public interface Set<T> {
 boolean add(T elem);
 boolean remove(T elem);
 
 boolean contains(T elem);
 int size();
}

• pacmaninbw: Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. In this particular instance you should probably add a follow up question with a link back to this question.

Answer 1

Advice 1

public class HashSetTest extends SetTest {
 ...
}

I haven't provide the SetTest, but if you remove the extends SetTest and the two unit test methods annotated with @Override, it compiles, runs and passes the tests.

Advice 2

Once again in the unit test file:

Set<SingleHashUnequal> set = new HashSet<SingleHashUnequal>(capacity);

You can omit the 2nd SingleHashUnequal to get:

Set<SingleHashUnequal> set = new HashSet<>(capacity);

Advice 3

List<T>[] t = new LinkedList[capacity];
table = t;
size = 0;

You can write:

table = new LinkedList[capacity];

since, Java sets int fields to zero by default.

Advice 4

What comes to add(T elem) and remove(T elem) of LinkedList, they return true if the state has changed due to the call to the two methods and false' otherwise. That way, you could spare some calls to contains(T elem)`.

Advice 5

Consider the ArrayList instead of LinkedList, since it will run faster and demand 3-fold times less memory (ArrayList stores only one reference for each element in it; LinkedList stores three references for each element (the actual element, the previous node, the next node).

Advice 6

if (table[hash] != null && table[hash].contains(elem)){
 return true;
}else{
 return false;
}

First, you should have a single space before { and after }. Second, you can write the above more succintly as:

return table[hash] != null && table[hash].contains(elem);

Summa summarum

All in all, I had this in mind:

import java.util.ArrayList;
import java.util.List;
public class HashSet<T> implements Set<T> {
 private List<T>[] table;
 private int size;
 /**
 * 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);
 }
 table = new ArrayList[capacity];
 }
 /**
 * Adds the given element to the set.
 *
 * @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) {
 if (elem == null) {
 return false;
 }
 int hash = Math.abs(elem.hashCode() % table.length);
 if (table[hash] == null) {
 table[hash] = new ArrayList<>();
 table[hash].add(elem);
 size++;
 return true;
 } else if (table[hash].add(elem)) {
 size++;
 return true;
 } else {
 return false;
 }
 }
 /**
 * Removes the given element from the dictionary, if it is present.
 *
 * @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) {
 if (elem == null) {
 return false;
 }
 int hash = Math.abs(elem.hashCode() % table.length);
 if (table[hash] != null) {
 if (table[hash].remove(elem)) {
 size--;
 return true;
 }
 return false;
 } else {
 return false;
 }
 }
 /**
 * Check if an element is in the Set.
 *
 * @param elem An element to look for.
 * @return true if the element is in the set, false otherwise.
 */
 @Override
 public boolean contains(T elem) {
 if (elem == null) {
 return false;
 }
 int hash = Math.abs(elem.hashCode() % table.length);
 return table[hash] != null && table[hash].contains(elem);
 }
 /**
 * Returns the number of elements in this set.
 *
 * @return The amount of elements in this set.
 */
 @Override
 public int size() {
 return size;
 }
}

• ee ss: Thank you! About the test I know that the go through, but are they correctly written, based on their description?
• coderodde: @eess You seem to be a better unit tester. I took a look at the test file, but didn't find anything suspicious.
• ee ss: Thank you! BTW I added the other test class, if you can look at those test too that would be awesome.
• coderodde: @eess SetTest seems fine.