Hash table implementation in Java

Question

For class, I was asked to write a (linear probing) hash table in Java. (I was also asked to write a linear-chaining hash table, which is why I named this one HashtableB as opposed to just Hashtable.) I'm think my code is correct, but please tell me if I've messed up.

Primarily, though, my questions are:

• Is my style (e.g. naming conventions, whitespace, line length, etc.) correct?
• Do I have too few comments? Too many?
• I've heard about Javadocs. Should I be using that? What would that look like?
• Is my code clear and concise?
• Is correctly object-oriented (e.g., should I have getters and setters for Pair)?
• Am I using generics correctly?
• Should I only be importing the specific parts of the standard libraries, or is importing java.utils.* okay?

The ST<K, V> interface is because I've written other symbol table implementations and wanted to be able to use/test them interchangeably.

HashtableB.java

import java.util.*;
import java.lang.reflect.Array;

// A linear-probing hash table implementation
public class HashtableB<K, V> implements ST<K, V> {
    private static final int MIN_CAP = 11; // The minimum size of the array; when smaller than this, no down-sizing will occur.

    private Pair[] arr; // The array holding all the key/value pairs
    private int size; // The current number of elements.
    private int cap; // Current capacity of the array.

    private double max; // determines how full the array can get before resizing occurs; default 1/2
    private double min; // determines how empty the array can get before resizing occurs; default 3/4
    private double set; // determines how full the array should be made when resizing; default 1/4

    // Primary constructor.
    // Set determines how full the array should be made when resizing
    // Maximum determines how full the array can get before resizing occurs
    // Minimum determines how empty the array can get before resizing occurs
    public HashtableB(double maximum, double minimum, double set){
        assert set < maximum && maximum < 1;
        assert 0 < minimum && minimum < set;
        size = 0;
        cap = MIN_CAP;
        max = maximum;
        min = minimum;
        this.set = set;

        arr = (Pair[]) Array.newInstance(Pair.class, cap); // Make the new array;
    }

    // Default the set-size ratio to 1/2
    public HashtableB(double maximum, double minimum){
        this(maximum, minimum, 0.5);
    }

    // Default the max-size ratio to 3/4 and the min-size ratio to 1/4.
    public HashtableB(){
        this(0.75, 0.25);
    }

    // Get the given key.
    public V get(K key){
        assert key != null;

        // Find the key.
        int i = hash(key) % cap;
        while(!key.equals(arr[i].k)){
            i = (i+1) % cap;
        }
        return arr[i]==null? null : arr[i].v; // If there's nothing there, return null. Otherwise, return the value.
    }

    // Sets the given key to the given value.
    public void put(K key, V val){
        assert key != null;
        int i = hash(key) % cap;
        while (arr[i]!=null && !key.equals(arr[i].k)) {
            i = (i+1) % cap;
        }
        if(arr[i] == null) // If we are putting a new key in, increase the size.
            size++;
        arr[i] = new Pair(key, val);

        resize(); // If we need to resize, do so.
    }

    // A hash of the key. I used the absolute value of the key's hashcode so that I didn't get weird negative indices.
    private int hash(K key){
        return Math.abs(key.hashCode());
    }

    // Resize the array if necessary.
    private void resize(){
        if(!((size<cap*min && cap>MIN_CAP) || size>cap*max)){
            return;
        }
        int newcap = (int) (size/set); // The size of the new array

        @SuppressWarnings("unchecked")
        Pair[] a = (Pair[]) Array.newInstance(Pair.class, newcap); // Make the new array

        for(int j=0; j<cap; j++){
            Pair q = arr[j];
            if(q==null)
                continue;

            int i = hash(q.k) % newcap;
            while (a[i]!=null && !q.k.equals(a[i].k)) {
                i = (i+1) % newcap; // get next index
            }
            a[i] = q;
        }
        this.arr = a;
        this.cap = newcap;
    }

    // In here for development purposes only.
    public boolean checkSize(){
        int x = 0;
        for(int i=0; i<cap; i++){
            if(arr[i] != null)
                x++;
        }
        return x == size;
    }

    // Return the number of elements currently contained in this hashtable.
    public int size(){
        return size;
    }

    // Return a list of all the keys currently contained in this hashtable.
    public Set<K> getAll(){
        Set<K> set = new HashSet<K>(size);
        for(Pair p : arr)
            if(p != null)
                set.add(p.k);
        return set;
    }

    // Remove the given key from the hashtable.   
    public void delete(K key){
        assert key != null;
        List<Pair> pairs = new ArrayList<Pair>();

        // Find our key.
        int i = hash(key) % cap;
        while(arr[i]!=null && !key.equals(arr[i].k)){
            i = (i+1) % cap;
            if(arr[i] == null)
                System.out.printf("Delete could not find key %s %n", key.toString());
        }

        // Remove all the keys that could have been "forced over" by this key.
        while(arr[i] != null){
            pairs.add(arr[i]);
            arr[i] = null;
            size--;
            i = (i+1) % cap;
        }

        pairs.remove(0); // Remove the key we're deleting.

        for(Pair p : pairs)
            this.put(p.k, p.v); // Put the rest back in the hashtable.
    }

    public String toString(){
        return String.format("Hashtable(%.2f, %.2f, %.2f)", max, min, set);
    }

    // A key-value pair.
    class Pair{
        K k;
        V v;

        public Pair(K key, V val){
            k = key;
            v = val;
        }
    }
}

ST.java

import java.util.*;

// Symbol table matching keys (of type K) with values (of type V).
public interface ST<K, V> {
    V get(K key); // Get the value associated with the given key.
    void put(K key, V value); // Set the value associated with the given key. The key can be in the dictionary already or not.
    void delete(K key); // Remove the value associated with the given key (this should decrement the size).
    Set<K> getAll(); // Get all the keys in this symbol table.
    int size(); // Get the number of elements currently in the symbol table.
    boolean checkSize(); // For development only. Checks that the stored size and actual size match.
}

Answer 1

I highly recommend Clean Code: A Handbook of Agile Software Craftsmanship by Robert C. Martin. It's an excellent source of great advice precisely aimed at your questions. The earlier you start, the fewer bad habits you'll need to unlearn later on.

Formatting

Your line length and whitespace seem okay, though you a little off from Sun's (now Oracle's) Java Style Guide. I always put whitespace around keywords (if, while) and between closing parentheses and opening braces.

Naming

Ignoring HashtableB and ST which you've already explained, I would get in the habit of using fully-spelled-out variable names now. They are clearer and help you practice your typing skills. There are a few abbreviations that everyone will understand such as max and min, but they don't make good names by themselves.

• arr: Are you a pirate?
  Instead of naming the variable based on its type, name it for what it contains such as elements or pairs.
• cap: Is this a baseball cap?
  Spell this out as capacity.
• max: Maximum what? Speed? Value?
  Go for clarity with maxSize.
• resize: Does this always resize?
  No, thus your comment when calling it. Use resizeIfNeeded instead.
• getAll: All what: keys or values?
  Java's Map interface defines keySet and values.

Comments

You can remove a lot of these extraneous comments simply by using more expressive names. One of the main problems with comments is that they aren't compiled or checked for correctness. They can flat out lie to you like "Get the given key" which actually returns the value for the given key. Comments like "Find the key" in a method that by it's name obviously looks for the given key don't add anything.

99% of your comments should explain why you are doing something in a particular way when it's not obvious or trivial. If the code is so complicated that you can't tell what it does, rewrite it rather than adding a comment. In other words, avoid comments that merely translate the code into prose.

JavaDoc

Yes! It's never too early to build good habits, and they are very easy to write. Here's an example:

/**
 * Returns the value that is mapped to the given key.
 *
 * @param key the key to locate
 * @return the value mapped to {@code key} or {@code null} if not found
 */
public V get(K key) { ... }

Clarity

For the most part your code is pretty clean. Once you make the names more expressive it would be pretty easy to see what it does. Here are a few points:

• You don't need reflection. Instead of Array.newInstance use
  

  Pair[] newItems = new Pair[newCapacity];
  

• Consider implementing java.util.Map instead of creating your own ST interface. It has all the same methods as yours except checkSize which you can add just in your implementation as hasCorrectSize.
• Don't specify a size for HashSet. Most of the time you should let the libraries work it out.
• Using ArrayList in delete seems a little like cheating. ;)

OOP and Generics

The design looks pretty good, and your usage of generics looks correct.

• Pair should be static since it doesn't need a reference to its enclosing hashtable. It should also be private unless you need it for testing.
• Since Pair is internal, I don't see a need for getters. You might want to make it immutable by creating a new one instead of overwriting the value, but again it's internal and won't matter in this case.

Importing Classes

I used to prefer to import each class separately (no *) so you can see at a glance what the class uses. However, as I focus more on creating smaller classes it's not such a big deal. I still do it, but I'm not anal about it like I used to be. Pick a style and stick to it.

Answer 2

In the get method in the while loop, are you not getting a NullPointerException? I believe you should be checking for arr[i] != null.

Also, when you calculate a hash and the key you are looking for is not at that position, you move ahead to search for that key. To do that, why don't you use i = (i+1) % cap?