2
\$\begingroup\$

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();
}

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – pacmaninbw
    Commented Feb 9, 2022 at 16:49

1 Answer 1

1
\$\begingroup\$

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;
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Thank you! About the test I know that the go through, but are they correctly written, based on their description? \$\endgroup\$
    – ee ss
    Commented Feb 9, 2022 at 11:45
  • \$\begingroup\$ @eess You seem to be a better unit tester. I took a look at the test file, but didn't find anything suspicious. \$\endgroup\$
    – coderodde
    Commented Feb 9, 2022 at 11:54
  • \$\begingroup\$ Thank you! BTW I added the other test class, if you can look at those test too that would be awesome. \$\endgroup\$
    – ee ss
    Commented Feb 9, 2022 at 12:01
  • \$\begingroup\$ @eess SetTest seems fine. \$\endgroup\$
    – coderodde
    Commented Feb 9, 2022 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.