A minimal HashTable implementation

Question

For an assignment, I wrote a minimal HashTable implementation (it only supports additions; no deletions).

To resolve collisions, it uses Linear Probing (required by the assignment).

I'm looking for general feedback regarding style, practice, and these things specifically:

• I've gotten out of the habit of using null to denote an error/lack of result, since the return type of a method returning null doesn't give any hints about whether or not the method can fail. As a substitute, I've started using Optionals, since its use makes it very clear whether or not the method can fail. There are a few cases in this code where a null would otherwise be used, but I opted for using an Optional. Are these cases a correct usage?:

  • The underlying array is an ArrayList of Optionals of Pairs, since any given cell may or may not contain a value.

  • findNextInsertionPointAfter returns an Optional since the table may be full; in which case there is no next cell to add to.

• I decided to make my own pair class (KeyValuePair) to store the key-value-pair. Was this the correct approach to take?

• I figured passing in the hash-function as a lambda to the constructor of HashTable was the most flexible way of setting the function. Is my current set-up optimal?

• HashTables toString method is my standard concoction when I need to display a sequential container. Unfortunately, it's quite bulky. Is there a better way of setting this up that still gives the neat output?

Sample output from the internal main (at the bottom of HashTable.java):

[ -, -, -, -, -, -, -, -, -, -, -, -, - ]
[ -, (1,1), -, -, -, -, -, -, -, -, -, -, - ]
[ -, (1,1), -, -, -, (5,5), -, -, -, -, -, -, - ]
[ -, (1,1), -, -, -, (5,5), -, -, (21,21), -, -, -, - ]
[ (26,26), (1,1), -, -, -, (5,5), -, -, (21,21), -, -, -, - ]
[ (26,26), (1,1), (39,39), -, -, (5,5), -, -, (21,21), -, -, -, - ]
[ (26,26), (1,1), (39,39), (14,14), -, (5,5), -, -, (21,21), -, -, -, - ]
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), -, -, (21,21), -, -, -, - ]
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), (16,16), -, (21,21), -, -, -, - ]
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), (16,16), (17,17), (21,21), -, -, -, - ]
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), (16,16), (17,17), (21,21), (18,18), -, -, - ]
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), (16,16), (17,17), (21,21), (18,18), (19,19), -, - ]
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), (16,16), (17,17), (21,21), (18,18), (19,19), (20,20), - ]
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), (16,16), (17,17), (21,21), (18,18), (19,19), (20,20), (111,111) ]
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), (16,16), (17,17), (21,21), (18,18), (19,19), (20,20), (111,111) ]
Table ran out of space!
[ (26,26), (1,1), (39,39), (14,14), (15,15), (5,5), (16,16), (17,17), (21,21), (18,18), (19,19), (20,20), (111,111) ]

KeyValuePair.java:

package comp272.a2.q4;

//Since Java doesn't have tuples/a standard pair class.
//A "somewhat immutable" K-V-pair. The fields are final, so they can't be
// reassigned, but we aren't defensively copying the values before we return them.
//If the key and value are themselves immutable, so is the pair.
public class KeyValuePair<K,V> {
    private final K key;
    private final V value;

    public KeyValuePair(K k, V v) {
        key = k;
        value = v;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    @Override
    public String toString() {
        return "(" + key + "," + value + ")";
    }

}

HashTable.java:

package comp272.a2.q4;

import java.util.ArrayList;
import java.util.Optional;
import java.util.function.BiFunction;

public class HashTable<K,V> {

    //The underlying array that the Hash Tables builds on.
    private final ArrayList<Optional<KeyValuePair<K, V>>> underArr;

    //The user-supplied hash-function. It should take the key, and the size of
    // the table, and return a hash.
    private final BiFunction<K,Integer,Integer> hashFunc;

    public HashTable(int tableSize, BiFunction<K,Integer,Integer> f) {
        hashFunc = f;

        underArr = new ArrayList<Optional<KeyValuePair<K, V>>>(tableSize);
        initArr(tableSize);
    }

    public int tableSize() {
        return underArr.size();
    }

    public boolean hasSpace() {
        for (Optional<KeyValuePair<K, V>> optPair : underArr) {
            if (!optPair.isPresent()) return true;
        }

        return false;
    }

    //Optionally returns the next available cell if one exists
    //I could also return a negative number to represent a full table,
    // but I thought I'd use Optional for consistency.
    private Optional<Integer> findNextInsertionPointAfter(int startI) {
        for (int currentI = startI + 1; currentI != startI; currentI++) {
            //Wrap back to the start if we go off the right end of the table.
            if (currentI >= tableSize()) currentI = 0;

            if (!underArr.get(currentI).isPresent()) {
                return Optional.of(currentI);
            }
        }

        return Optional.empty();
    }

    //Attempts to insert a pair into the table.
    //Fails and returns false if the table is full, else the element is
    // inserted, and returns true.
    public boolean add(K k, V v) {
        int hash = hashFunc.apply(k, tableSize());

        if (!hashIsWithinTable(hash)) throw new IndexOutOfBoundsException(
            "The computed hash (" + hash + ")"
            + " exceeded the table size (" + tableSize() + ")");

        Optional<KeyValuePair<K, V>> foundCell = underArr.get(hash);
        KeyValuePair<K, V> pair = new KeyValuePair<K,V>(k, v);

        int insertIndex = hash;

        if (foundCell.isPresent()) {
            Optional<Integer> nextIndex = findNextInsertionPointAfter(hash);

            if (nextIndex.isPresent()) {
                insertIndex = nextIndex.get();

            } else {
                return false;
            }
        }

        underArr.set(insertIndex, Optional.of(pair));
        return true;
    }

    @Override
    public String toString() {
        String separator = ", ";
        String blankCell = "-";

        StringBuilder strB = new StringBuilder("[ ");

        for (Optional<KeyValuePair<K, V>> optPair : underArr) {
            if (optPair.isPresent()) {
                strB.append(optPair.get());

            } else {
                strB.append(blankCell);
            }

            strB.append(separator);
        }

        //Delete trailing separator
        if (!underArr.isEmpty())
            strB.delete(strB.length() - separator.length(), strB.length());

        strB.append(" ]");

        return strB.toString();
    }

    //Populate the table with all empty cells
    private void initArr(int tableSize) {
        for (int i = 0; i < tableSize; i++) {
            underArr.add(Optional.empty());
        }
    }

    private boolean hashIsWithinTable(int hash) {
        return hash < tableSize();
    }

    public static void main(String[] args) {
        HashTable<Integer,Integer> hTable =
            new HashTable<Integer, Integer>(13,
                (key, tableSize) -> key % tableSize );

        System.out.println(hTable);

        Integer[] keys = new Integer[] {
                1, 5, 21, 26, 39, 14, 15, 16, 17, 18, 19, 20, 111, 145, 146
        };

        boolean addSucceeded = hTable.hasSpace();
        for(int i = 0; i < keys.length && addSucceeded; i++) {
            addSucceeded = hTable.add(keys[i], keys[i]);
            System.out.println(hTable);
        }

        if (!hTable.hasSpace()) System.out.println(
            "Table ran out of space!");

        System.out.println(hTable);
    }
}

Answer 1

As a substitute, I've started using Optionals, since its use makes it very clear whether or not the method can fail.

It tells you about the same as a Nullable annotation would do, just with some overhead.

There are a few cases in this code where a null would otherwise be used, but I opted for using an Optional. Are these cases a correct usage?

I personally agree with this wonderful rant that any use and the mere existence of Optional is wrong.

The underlying array is an ArrayList of Optionals of Pairs, since any given cell may or may not contain a value.

Too bad. That's not what Optional is for. It was meant to be used for return values only (that's why it's not Serializable).

And you added some 12 bytes per entry.

I decided to make my own pair class (KeyValuePair) to store the key-value-pair. Was this the correct approach to take?

Not exactly as there's already Map.Entry.

I figured passing in the hash-function as a lambda to the constructor of HashTable was the most flexible way of setting the function. Is my current set-up optimal?

It adds some overhead, but may make sense.

KeyValuePair

Nothing to say, except for that usually toString would use "=" rather than ",". Just look at a HashMap in debugger.

An immutable KeyValuePair makes a lot of sense for an immutable map, but less for a mutable one. That's why Map.Entry allows to set the value (but not the key).

HashTable

private final ArrayList<Optional<KeyValuePair<K, V>>> underArr;

By using an ArrayList (which should be declared as List) you're adding additional indirection. The same for Optional. You gain some flexibility, which you can't use.

• with the size fixed, an array does the job
• Optional buys you nothing at all

underArr is a terrible name. table would do.

---

//The user-supplied hash-function. It should take the key, and the size of
// the table, and return a hash.
private final BiFunction<K,Integer,Integer> hashFunc;

That's a pain. Letting the user specify a Function<K, Integer> so that they can choose how to hash their values may make sense. Letting them care about the table size is too bad.

Returning Integer rather than int (see IntFunction) means another efficiency loss.

public HashTable(int tableSize, BiFunction<K,Integer,Integer> f) {
    hashFunc = f;

So f or hashFunc? Both names are non-optimal (with f being terrible for anything but a local variable), using two different names is a sin.

    underArr = new ArrayList<Optional<KeyValuePair<K, V>>>(tableSize);
    initArr(tableSize);

Without Optional you could save yourself initArr (didn't I say, I hate the name?).

---

public boolean hasSpace() {
    for (Optional<KeyValuePair<K, V>> optPair : underArr) {
        if (!optPair.isPresent()) return true;
    }

    return false;
}

Do you really traverse the whole table on each insert? Otherwise, I can't see what this method is good for.

But if you traverse the whole table on each insert, then it's the final blow to any efficiency you could gain by hashing.

...it's getting too long and I'm getting too negative...