2
\$\begingroup\$

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


    }
\$\endgroup\$
1
  • \$\begingroup\$ If the capacity is a power of 2, then can use bit wise logic instead of modulo which is quite expensive \$\endgroup\$ – Solubris May 19 '20 at 16:47
2
\$\begingroup\$

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

    }

}
\$\endgroup\$

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.