3
\$\begingroup\$

Looking for feedback on my java hash table implementation. Code uses an array of lists of entries as a sort of separate-chaining; not sure how much I prefer this approach in practice, and am considering using linear / quadratic probing instead. Table should resize above a certain load %. I also tried to handle negative hashes being generated, and use a prime # for table size in order to prevent clustering.

It seems as though there are many different methods and techniques to use when building a hash table from scratch, so any comments or suggestions on my approach, coding style, conventions, etc would be greatly appreciated! Thanks in advance.

HashTable implementation:

public class HashTable<K, V> {

    private ListNode<Entry<K, V>>[] table;
    private int size;
    private final int initSize = 5;
    private final double loadFactor = 0.70;
    private final int resizeFactor = 2;

    public HashTable() {
        this.table = new ListNode[this.initSize];
        for(int i = 0; i < this.table.length; i++) {
            this.table[i] = new ListNode();
        }
    }

    public V get(K key) throws Exception {
        try {
            ListNode<Entry<K, V>> bucket = getBucket(key);
            while(bucket != null) {
                if(bucket.getData().getKey().equals(key)) {
                    return bucket.getData().getValue();
                }
            }
            return null;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public boolean put(K key, V value) throws Exception {
        try {
            if(put(new Entry(key, value))) {
                resize();
                return true;
            }
            return false;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }
    private boolean put(Entry<K, V> entry) throws Exception {
        try {
            // if bucket's data at hash index is empty, add entry
            if(this.table[hashFunction(entry.getKey())] == null) { // if bucket is null
                this.table[hashFunction(entry.getKey())] = new ListNode(entry);
                this.size++;
                return true;
            } else if(this.table[hashFunction(entry.getKey())].getData() == null) { // if bucket holds no entry data
                this.table[hashFunction(entry.getKey())].setData(entry);
                this.size++;
                return true;
            } else { // if bucket contains data:
                // iterate through bucket until a. bucket with data containing key is found, b. bucket with no entry data is found, or c. null bucket is found
                ListNode<Entry<K, V>> tempBucket = this.table[hashFunction(entry.getKey())];
                if(tempBucket.getData().getKey().equals(entry.getKey())) { // if bucket contains correct entry key data
                    tempBucket.getData().setValue(entry.getValue());
                    return true;
                }
                while(tempBucket.getNext() != null) {
                    if(tempBucket.getData().getKey().equals(entry.getKey())) { // if bucket contains correct entry key data
                        tempBucket.getData().setValue(entry.getValue());
                        return true;
                    } else { // check next bucket in list
                        tempBucket = tempBucket.getNext();
                    }
                }
                // null bucket has been found, add new entry data:
                tempBucket.setNext(new ListNode(entry));
                this.size++;
                return true;
            }
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public boolean containsKey(K key) throws Exception {
        try {
            ListNode<Entry<K, V>> bucket = getBucket(key);
            while(bucket != null) {
                if(bucket.getData() != null) {
                    if(bucket.getData().getKey().equals(key)) {
                        return true;
                    }
                }
                bucket = bucket.getNext();
            }
            return false;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public boolean remove(K key) throws Exception {
        try {
            ListNode<Entry<K, V>> bucket = getBucket(key);
            ListNode<Entry<K, V>> prev = null;
            while(bucket != null) {
                if(bucket.getData().getKey().equals(key)) {
                    break;
                }
                prev = bucket;
                bucket = bucket.getNext();
            }
            if(bucket == null) {
                return false;
            }
            if(prev != null) {
                prev.setNext(bucket.getNext());
            } else {
                this.table[hashFunction(key)] = bucket.getNext();
            }
            this.size--;
            return true;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    private ListNode<Entry<K, V>> getBucket(K key) {
        return this.table[hashFunction(key)];
    }

    private int hashFunction(K key) {
        int hash = key.hashCode() % this.table.length;
        return (hash < 0) ? hash * -1 : hash;
    }

    private void resize() throws Exception {
        try {
            if(this.size / (double)this.table.length > this.loadFactor) {
                int newSize = this.table.length * this.resizeFactor;
                while(newSize % 2 == 0 || newSize % 3 == 0) { // find > double current size prime number for new table size.
                    newSize++;
                }
                SinglyLinkedList<ListNode<Entry<K, V>>> oldEntries = new SinglyLinkedList(); // store current data to be rehashed later.
                for(int i = 0; i < this.table.length; i++) {
                    if(this.table[i].getData() != null) {
                        oldEntries.insertEnd(this.table[i]);
                    }
                }
                this.table = new ListNode[newSize];
                for(int i = 0; i < this.table.length; i++) {
                    this.table[i] = new ListNode();
                }
                for(int i = 0; i < oldEntries.getSize(); i++) { // rehash old values into newly-allocated array.
                    ListNode<Entry<K, V>> oldEntry = oldEntries.getElementAt(i);
                    while(oldEntry != null) {
                        put(oldEntry.getData().getKey(), oldEntry.getData().getValue());
                        this.size--; // ensure that size isn't being artificially inflated during rehash
                        oldEntry = oldEntry.getNext();
                    }
                }
            }
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public int getSize() throws Exception {
        try {
            return this.size;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

    public boolean isEmpty() throws Exception {
        try {
            return this.size <= 0;
        } catch(Exception e) {
            throw new Exception(e);
        }
    }

}

Entry class, used within HashTable:

public class Entry<K, V> {
    private K key;
    private V value;

    public Entry() {}

    public Entry(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Have you tested this at all? Your HashTable.get method doesn't seem to advance bucket, so it would infinite loop whenever the first value isn't the right value. \$\endgroup\$ – mdfst13 Jan 27 '18 at 1:35
  • \$\begingroup\$ @mdfst13 I have written some tests, but I guess I must have missed that case. Thanks for the heads up. \$\endgroup\$ – koprulu Jan 27 '18 at 2:51
3
\$\begingroup\$
  1. Please add null check for 'keys' I am assuming you are getting a NPE, if key==null.

  2. If key == null, then hashcode is 0.

  3. In the while loop in 'get' method, I am struggling to understand, where you are advancing to next entry in the same bucket ?

  4. Your Entry class can contain 'next' pointer, such that it behaves like a linkedlist.

  5. ListNode<Entry<K, V>> bucket = getBucket(key); this can be made final since its not changed in scope of method. Similarly final K key can be added.

  6. In your get method you are catching and throwing the same exception. You would typically catch an exception only if you want to pad it with additional message or cast it into a more generic exception.

  7. You always call resize and there is a logic inside resize that tells you wether to proceed with resize or not. Now, if you could either rename it to tryResize or do the check before calling resize it would be more meaningful.

\$\endgroup\$
0
\$\begingroup\$

Advice 1

The problem behind open addressing (probing) is that the operations slow down far beyond \$\Theta(1)\$ which is pretty much guaranteed by collision chains (your current implementation) under assumption that the load factor and the hash function are reasonable. Advice: stick to collision chains.

Advice 2

You explicitly create an entire table of ListNode objects. I suggest you roll something like

// Partially a pseudocode.
private static final class CollisionChainNode<K, V> {
    private final K key;
    private V value;
    private CollisionChainNode<K, V> prev;
    private CollisionChainNode<K, V> next;
    private final int keyHashCode; // This may add to performance if the key is a string/collection. For the node, the key is `final`, so that you need to compute that only once.
}

... and you populate the actual hash table only there where needed.

Advice 3

You are prepared to catch some exceptions. That is not quite correct when dealing with data structures in general: you should make sure via invariants that the data structure works as expected. The only exception you may need to throw/catch are those that are related to resources; most usually, memory.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the response! When you mention using 'invariants' in order to verify that the data structure works as expected, what exactly do you mean? \$\endgroup\$ – koprulu Jan 26 '18 at 23:17
  • 1
    \$\begingroup\$ @koprulu Basically, you need to master your code such that it cannot throw, say, NullPointerException or any other exception that is not caused by exhaustion of resources (such as memory). We can always run out of memory; nothing we can do here, but your algorithms must be written such that they cannot "break" otherwise. \$\endgroup\$ – coderodde Jan 26 '18 at 23:32
  • 1
    \$\begingroup\$ I disliked this because probing can work faster, even when you consider collisions if you use a good collision resolution system. Python for example uses a version where you shift in 5 bits of hash code at a time, with some mixing factors to ensure that large numbers of collisions are rare. Here is a link explaining the approach. hg.python.org/cpython/file/52f68c95e025/Objects/… \$\endgroup\$ – Oscar Smith Jan 27 '18 at 2:15
  • 1
    \$\begingroup\$ @Oscar Smith Fair enough. Any suggestions how I could improve my answer? \$\endgroup\$ – coderodde Jan 27 '18 at 7:51
  • \$\begingroup\$ If you removed the "probing is bad", I'd remove the down-vote. If you added a brief bit explaining with more nuance what the relative advantages/disadvantages were, it would be a stronger answer. \$\endgroup\$ – Oscar Smith Jan 27 '18 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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