Hash table in Java with arrays and linear probing

Question

I did some manual tests by instantiating the class and it seems to be working okay. I wanted some feedback on the following:

1. Is the code well structured? I notice I have a lot of redundancy. The search and delete methods are almost the same.

2. I use a string to flag deleted keys until they are replaced, is there a better way to do this. Another boolean array maybe?

public class HashTable {
 //known limitation: This will break if the key value is set to none because I use none as the identifier string for deleted keys.
 private int capacity;
 String values[];
 String keys[];
 public HashTable(int capacity){
 this.capacity = capacity;
 values = new String[this.capacity];
 keys = new String[this.capacity];
 }
 public int hash(String key){
 int sum = 0;
 for (int i=0; i<key.length();i++){
 sum+=key.charAt(i);
 }
 return sum%capacity;
 }
 public void add(String key, String value){
 int keyhash;
 int i = 0;
 while(i!=capacity-1){
 keyhash = (hash(key)+i)%capacity;
 System.out.println("Try "+ i);
 if(values[keyhash]==null || values[keyhash].equals("none")) { //add delete flag to this condition after implementing delete.
 values[keyhash] = value;
 keys[keyhash] = key;
 break;
 }
 if(values[keyhash]!=null && keys[keyhash].equals(key)){
 values[keyhash]=value;
 break;
 }
 i++;
 }
 if(i==capacity-1)
 System.out.println("Table appears to be full,unable to insert value");
 else
 System.out.println("Value inserted successfully.");
 }
 public String get(String key){
 int i = 0;
 int keyhash = (hash(key)+i)%capacity;
 while(values[keyhash]!=null && i<capacity){
 //System.out.println("Try " +i + " of finding the key.");
 if(keys[keyhash].equals(key))
 return values[keyhash];
 i++;
 keyhash = (hash(key)+i)%capacity;
 }
 return null;
 }
 public void remove(String key){
 int i = 0;
 int keyhash = (hash(key)+i)%capacity;
 while(keys[keyhash]!=null && i<capacity) {
 if (keys[keyhash].equals(key)) {
 keys[keyhash] = "none";
 values[keyhash] = "none";
 return;
 }
 i++;
 keyhash = (hash(key)+i)%capacity;
 }
 System.out.println("Key does not exist in table");
 }
 public void getHashedValues(){
 System.out.println();
 for(int i = 0; i<values.length;i++){
 System.out.print(" "+ values[i]);
 }
 System.out.println();
 }
 }

• Solubris: If the capacity is a power of 2, then can use bit wise logic instead of modulo which is quite expensive

Answer 1

I formatted your code and added a main method to test the functionality of your HashTable.

I removed all System calls from the HashTable class and replaced the important text displays with Exceptions. Generally, utility classes don't write to System.out or System.err.

I modified your getHashedValues method to return the values.

I'd change your use of i to index, but that's a minor point.

All in all, good work.

public class HashTableTestbed {
 public static void main(String[] args) {
 HashTableTestbed test = new HashTableTestbed();
 HashTable hashTable = test.new HashTable(3);
 hashTable.add("alpha", "zeta");
 hashTable.add("beta", "theta");
 hashTable.add("gamma", "tau");
 System.out.println(hashTable.get("alpha"));
 System.out.println(hashTable.get("beta"));
 System.out.println(hashTable.get("gamma"));
 hashTable.remove("beta");
 System.out.println(hashTable.get("beta"));
 hashTable.add("beta", "theta");
 System.out.println(hashTable.get("beta"));
 }
 public class HashTable {
 // known limitation: This will break if the key value
 // is set to none because I
 // use none as the identifier string for deleted keys.
 private int capacity;
 String values[];
 String keys[];
 public HashTable(int capacity) {
 this.capacity = capacity;
 values = new String[this.capacity];
 keys = new String[this.capacity];
 }
 public int hash(String key) {
 int sum = 0;
 for (int i = 0; i < key.length(); i++) {
 sum += key.charAt(i);
 }
 return sum % capacity;
 }
 public void add(String key, String value) {
 int keyhash;
 int i = 0;
 while (i != capacity - 1) {
 keyhash = (hash(key) + i) % capacity;
 if (values[keyhash] == null ||
 values[keyhash].equals("none")) {
 // add delete flag to this condition
 // after implementing delete.
 values[keyhash] = value;
 keys[keyhash] = key;
 break;
 }
 if (values[keyhash] != null &&
 keys[keyhash].equals(key)) {
 values[keyhash] = value;
 break;
 }
 i++;
 }
 if (i == capacity - 1) {
 String text = "Table appears to be full, "
 + "unable to insert value";
 throw new ArrayIndexOutOfBoundsException(text);
 }
 }
 public String get(String key) {
 int i = 0;
 int keyhash = (hash(key) + i) % capacity;
 while (values[keyhash] != null && i < capacity) {
 if (keys[keyhash].equals(key))
 return values[keyhash];
 i++;
 keyhash = (hash(key) + i) % capacity;
 }
 return null;
 }
 public void remove(String key) {
 int i = 0;
 int keyhash = (hash(key) + i) % capacity;
 while (keys[keyhash] != null && i < capacity) {
 if (keys[keyhash].equals(key)) {
 keys[keyhash] = "none";
 values[keyhash] = "none";
 return;
 }
 i++;
 keyhash = (hash(key) + i) % capacity;
 }
 String text = "Key does not exist in table";
 throw new IllegalArgumentException(text);
 }
 public String[] getHashedValues() {
 return values;
 }
 }
}