trjhtr

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

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.

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.