Linear Probing on Java HashTable implementation

Question

So I have a HashTable implementation here that I wrote using only Arrays and had a little bit of help with the code. Unfortunately, I don't quite understand one of the lines someone added while running the "get" or "put" method. What exactly is happening in the while loop below? It is a method for linear probing correct? Also why is the loop checking the conditions it's checking?

Specifically,

int hash = hashThis(key);

    while(data[hash] != AVAILABLE && data[hash].key() != key) {

        hash = (hash + 1) % capacity;
    }

Here's the whole Java class below for full reference.

public class Hashtable2 {

private Node[] data;
private int capacity;
private static final Node AVAILABLE = new Node("Available", null);

public Hashtable2(int capacity) {

    this.capacity = capacity; 
    data = new Node[capacity];
    for(int i = 0; i < data.length; i++) {

        data[i] = AVAILABLE;
    }
}

public int hashThis(String key) {

    return key.hashCode() % capacity; 
}

public Object get(String key) {

    int hash = hashThis(key);

    while(data[hash] != AVAILABLE && data[hash].key() != key) {

        hash = (hash + 1) % capacity;
    }
    return data[hash].element();
}

public void put(String key, Object element) {

    if(key != null) {
        int hash = hashThis(key);
        while(data[hash] != AVAILABLE && data[hash].key() != key) {

            hash = (hash + 1) % capacity;
        }

        data[hash] = new Node(key, element);

    }

}



public String toString(){

    String s="<";

    for (int i=0;i<this.capacity;i++)
    {
        s+=data[i]+", ";    

    }

    s+=">";

    return s;
    }

Thank you.

Answer 1

I just rewrote some part of the code and added the findHash-method - try to avoid code-duplication!

private int findHash(String key) {
    int hash = hashThis(key);

    // search for the next available element or for the next matching key
    while(data[hash] != AVAILABLE && data[hash].key() != key) {

        hash = (hash + 1) % capacity;
    }
    return hash;
}

public Object get(String key) {

    return data[findHash(key)].element();
}

public void put(String key, Object element) {

    data[findHash(key)] = new Node(key, element); 
}

What you asked for is - what exactly does this findHash-loop? The data was initialized with AVAILABLE - meaning: the data does not (yet) contain any actual data. Now - when we add an element with put - first a hashValue is calculated, that is just an index in the data array where to put the data. Now - if we encounter that the position has already been taken by another element with the same hash value but a different key, we try to find the next AVAILABLE position. And the get method essentially works the same - if a data element with a different key is detected, the next element is probed and so on. The data itself is a so called ring-buffer. That is, it is searched until the end of the array and is next search again at the beginning, starting with index 0. This is done with the modulo % operator.

Alright?

Answer 2

Sample Hashtable implementation using Generics and Linear Probing for collision resolution. There are some assumptions made during implementation and they are documented in javadoc above class and methods.

This implementation doesn't have all the methods of Hashtable like keySet, putAll etc but covers most frequently used methods like get, put, remove, size etc.

There is repetition of code in get, put and remove to find the index and it can be improved to have a new method to find index.

class HashEntry<K, V> {
    private K key;
    private V value;
    public HashEntry(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public void setKey(K key) { this.key = key; }
    public K getKey() { return this.key; }

    public void setValue(V value) { this.value = value; }
    public V getValue() { return this.value; }
}

/**
 * Hashtable implementation ...
 *   - with linear probing
 *   - without loadfactor & without rehash implementation.
 *   - throws exception when table is full
 *   - returns null when trying to remove non existent key
 *
 * @param <K>
 * @param <V>
 */
public class Hashtable<K, V> {

    private final static int DEFAULT_CAPACITY = 16;

    private int count;
    private int capacity;
    private HashEntry<K, V>[] table;

    public Hashtable() {
        this(DEFAULT_CAPACITY);
    }

    public Hashtable(int capacity) {
        super();
        this.capacity = capacity;
        table = new HashEntry[capacity];
    }

    public boolean isEmpty() { return (count == 0); }

    public int size() { return count; }

    public void clear() { table = new HashEntry[this.capacity]; count = 0; }

    /**
     * Returns null if either probe count is higher than capacity else couldn't find the element.
     * 
     * @param key
     * @return
     */
    public V get(K key) {
        V value = null;
        int probeCount = 0;
        int hash = this.hashCode(key);
        while (table[hash] != null && !table[hash].getKey().equals(key) && probeCount <= this.capacity) {
            hash = (hash + 1) % this.capacity;
            probeCount++;
        }
        if (table[hash] != null && probeCount <= this.capacity) {
            value = table[hash].getValue();
        }
        return value; 
    }

    /**
     * Check on the no of probes done and terminate if probe count reaches to its capacity.
     * 
     * Throw Exception if table is full.
     * 
     * @param key
     * @param value
     * @return
     * @throws Exception
     */
    public V put(K key, V value) throws Exception {
        int probeCount = 0;
        int hash = this.hashCode(key);
        while (table[hash] != null && !table[hash].getKey().equals(key) && probeCount <= this.capacity) {
            hash = (hash + 1) % this.capacity;
            probeCount++;
        }
        if (probeCount <= this.capacity) {
            if (table[hash] != null) {
                table[hash].setValue(value);                
            } else {
                table[hash] = new HashEntry(key, value);
                count++;
            }
            return table[hash].getValue();
        } else {
            throw new Exception("Table Full!!");
        }
    }

    /**
     * If key present then mark table[hash] = null & return value, else return null.  
     * 
     * @param key
     * @return
     */
    public V remove(K key) {
        V value = null;
        int probeCount = 0;
        int hash = this.hashCode(key);
        while (table[hash] != null && !table[hash].getKey().equals(key) && probeCount <= this.capacity) {
            hash = (hash + 1) % this.capacity;
            probeCount++;
        }
        if (table[hash] != null && probeCount <= this.capacity) {
            value = table[hash].getValue(); 
            table[hash] = null;
            count--;
        }
        return value;
    }

    public boolean contains(Object value) {
        return this.containsValue(value);
    }

    public boolean containsKey(Object key) {
        for (HashEntry<K, V> entry : table) {
            if (entry != null && entry.getKey().equals(key)) {
                return true;
            }
        }
        return false;
    }

    public boolean containsValue(Object value) {
        for (HashEntry<K, V> entry : table) {
            if (entry != null && entry.getValue().equals(value)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder data = new StringBuilder();
        data.append("{");
        for (HashEntry<K, V> entry : table) {
            if (entry != null) {
                data.append(entry.getKey()).append("=").append(entry.getValue()).append(", ");
            }
        }
        if (data.toString().endsWith(", ")) {
            data.delete(data.length() - 2, data.length());
        }
        data.append("}");
        return data.toString();
    }

    private int hashCode(K key) { return (key.hashCode() % this.capacity); }

    public static void main(String[] args) throws Exception {
        Hashtable<Integer, String> table = new Hashtable<Integer, String>(2);
        table.put(1, "1");
        table.put(2, "2");
        System.out.println(table);
        table.put(1, "3");
        table.put(2, "4");
        System.out.println(table);
        table.remove(1);
        System.out.println(table);
        table.put(1, "1");
        System.out.println(table);
        System.out.println(table.get(1));
        System.out.println(table.get(3));
        // table is full so below line
        // will throw an exception
        table.put(3, "2");
    }
}

---

Sample run of the above code.

{2=2, 1=1}
{2=4, 1=3}
{2=4}
{2=4, 1=1}
1
null
Exception in thread "main" java.lang.Exception: Table Full!!
    at Hashtable.put(Hashtable.java:95)
    at Hashtable.main(Hashtable.java:177)