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;
}
}
HashTable.getmethod doesn't seem to advancebucket, so it would infinite loop whenever the first value isn't the right value. \$\endgroup\$