2
\$\begingroup\$

I'm new to hash codes/hash tables, so I'm very unsure of my implementation. I want to create a hash table, but I can only use arrays. Specifically, I want to be able to insert things like a dictionary (a word and its meaning). Here is what I have:

public class HashTable {
    String[][] table;
    int tableSize;

    HashTable(int size) {
        table = new String[size][];
        tableSize = size;
    }

    public void add(String key, String value) {

        if (key == null || value == null) {
            System.out.println("Cannot input null values");
        }

        int iter = 0;
        int code = Math.abs(key.hashCode()) % tableSize;

        if (table[code] == null) {
            table[code] = new String[]{key, value};
        } else {

            while (table[code] != null) {
                if (table[code][0].equals(key)) {
                    System.out.println("Already submitted submitted the word " + key);
                    return;
                }

                if (iter == tableSize) {
                    System.out.println("Table is full. Cannot add word \"" + key + "\"");
                    return;
                }

                code++;
                code %= tableSize;
                iter++;
            }

            table[code] = new String[]{key, value};

        }
    }

    public void remove(String key) {

        if (key == null) {
            System.out.println("Cannot input null value");
        }

        int iter = 0;
        int code = Math.abs(key.hashCode()) % tableSize;

        if (table[code][0].equals(key)) {
            table[code] = null;
        } else {
            while (!table[code][0].equals(key)) {
                if (iter == tableSize) {
                    System.out.println("Could not find word \"" + key + "\"");
                    return;
                }
                code++;
                code %= tableSize;
                iter++;
            }

            table[code] = null;

        }
    }

    public String get(String key) {

        if (key == null) {
            return "Cannot input null value.";
        }

        int iter = 0;
        int code = Math.abs(key.hashCode()) % tableSize;

        if (table[code][0].equals(key)) {
            return table[code][1];
        } else {
            while (!table[code][0].equals(key)) {
                if (iter == tableSize) {
                    return "Could not find word \"" + key + "\"";
                }
                code++;
                code %= tableSize;
                iter++;
            }

            return table[code][1];

        }
    }

}

Is this an okay implementation? How can I make it better?

Thanks!

\$\endgroup\$
1
\$\begingroup\$
  • Do not special case an immediate success. The test for table[code] == null in

        if (table[code] == null) {
            table[code] = new String[]{key, value};
        } else {
            while (table[code] != null) {
            ....
    

    does not do anything useful, but only adds noise. Dive into the loop immediately.

    Ditto for table[code][0].equals(key) in remove and get.

  • Such low level utility functions shall not System.out.println (in any case, an error message shall go to System.err). Prefer returning an error code, and let the caller decide what to do.

  • It is unclear how well String.hashCode() is suited for this design of a hash table. Depending on the table size, you may get plenty of collisions. Using Math.abs on a hash code also biases the distribution. Need to measure.

|improve this answer|||||
\$\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.