Java Hash Table Implementation

Question

In my implementation of a Hash Table, my hash function simply takes the value of the item I pass, call hashCode (inherited from the Object class), and modulo the size of the internal array. This internal array is an array of LinkedLists. Now if my LinkedLists become too long (and my efficiency begins to slip from O(1) to O(n)), I figured it would make sense to simply grow the size of the array. But that's where my problems lie, since I stated I hash the items I pass and modulo the size of the array (which has just changed). If I were to continue, wouldn't the hashes point to different indices in the array, thus lose the ability to refer to items in my hash table? How could I solve this?

• Oliver Charlesworth: You need to re-hash everything. en.wikipedia.org/wiki/Hash_table#Dynamic_resizing

Answer 1

You need the actual hash values for each of the items so that you can put them into the correct hash chain in the resized table. (Otherwise, as you observed, the items are liable to end up on the wrong chain and to not be locatable as a result.)

There are two ways to deal with this:

• You could simply recalculate the hash value for each item as you add it to the new table.

• You could keep a copy of the original hash values for each item in the hash chain. This is what the standard Java HashMap implementation does ... at least in the versions I've looked at.

(The latter is a time vs space trade-off that could pay off big time if your items have an expensive hashcode method. However, if you amortize over the lifetime of a hash table, this optimization does not alter the "big O" complexity of any of the public API methods ... assuming that your hash table resizing is exponential; e.g. you roughly double the table size each time.)

Answer 2

package com.codewithsouma.hashtable;
import java.util.LinkedList;
public class HashTable {
 private class Entry {
 private int key;
 private String value;
 public Entry(int key, String value) {
 this.key = key;
 this.value = value;
 }
 }
 LinkedList<Entry>[] entries = new LinkedList[5];
 public void put(int key, String value) {
 var entry = getEntry(key);
 if (entry != null){
 entry.value = value;
 return;
 }
 getOrCreateBucket(key).add(new Entry(key,value));
 }
 public String get(int key) {
 var entry = getEntry(key);
 return (entry == null) ? null : entry.value;
 }
 public void remove(int key) {
 var entry = getEntry(key);
 if (entry == null)
 throw new IllegalStateException();
 getBucket(key).remove(entry);
 }
 private LinkedList<Entry> getBucket(int key){
 return entries[hash(key)];
 }
 private LinkedList<Entry> getOrCreateBucket(int key){
 var index = hash(key);
 var bucket = entries[index];
 if (bucket == null) {
 entries[index] = new LinkedList<>();
 bucket = entries[index];
 }
 return bucket;
 }
 private Entry getEntry(int key) {
 var bucket = getBucket(key);
 if (bucket != null) {
 for (var entry : bucket) {
 if (entry.key == key) return entry;
 }
 }
 return null;
 }
 private int hash(int key) {
 return key % entries.length;
 }
}