3
\$\begingroup\$

Implementation of a hash function in java, haven't got round to dealing with collisions yet. I tried to use good code, refactored, descriptive variable names, nice syntax.

My code must be efficient and extensible.

Would be interested to know how you guys would improve. Three classes:

  1. TestHash - main method is here, hash is initialised and data inserted and read
  2. HashTable -object were the hash table is held
  3. HashEntry - each entry in the array is a 'HashEntry' object

HashTable

import java.io.*;

public class HashTable {
    // number of indexes in hash table
    private final static int TABLE_SIZE = 100;
    // initialise array of HashEntry (table)
    HashEntry[] table;

    // constructor, create array, assign all values to null
    HashTable() {
        // create array of HashEntry, predefined size
        table = new HashEntry[TABLE_SIZE];
        // assign all values to null
        for (int i = 0; i < TABLE_SIZE; i++) {
            table[i] = null;
        }
    }

    // from key, find the correct index, load the HashEntry object and return the value
    public String getValue(String key) {
        int index = this.getKeyIndex(key);
        HashEntry chosen_entry = table[index];
        String chosen_entry_value = chosen_entry.getValue(key);
        return chosen_entry_value;
    }

    // creates a new HashEntry object, inserts that into the table array at the correct index
    // determined by getKeyIndex(key)
    public void insert(String key, String value) {
        int index = this.getKeyIndex(key);
        HashEntry keyValuePair;
        keyValuePair = new HashEntry(key, value);
        table[index] = keyValuePair;
        return;
    }

    // ** PRIVATE FUNCTIONS ** //
    // get index from key
    private Integer getKeyIndex(String key) {
        int hash = 7;
        for (int i = 0; i < key.length(); i++) {
            hash = (hash*31 + key.charAt(i))%100;
        }
        return hash;
    }
}

HashEntry

public class HashEntry {
    private String key;
    private String value;

    HashEntry(String key, String value) {
        this.key = key;
        this.value = value;
    }

    public String getKey() {
        return this.key;
    }

    public String getValue(String key) {
        // use string key to move down linked list in case of collision
        // haven't implemented this yet
        return this.value;
    }
}

TestHash

public class TestHash {
    public static void main(String[] args)
    {
        HashTable tableHash = new HashTable();
        tableHash.insert("david", "england");
        tableHash.insert("joe", "united states");
        tableHash.insert("maria", "china");
        System.out.println(tableHash.getValue("joe"));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Are you willing to look at any other answers? I was working on one, but you've already accepted the current one. If you still want a review, please tell me. \$\endgroup\$ – user2296177 Nov 21 '15 at 18:18
  • \$\begingroup\$ @user2296177 feel free to share your inputs too, it may help others looking at this question! :) \$\endgroup\$ – h.j.k. Nov 22 '15 at 3:12
  • \$\begingroup\$ If your answer is significantly better than what is currently given I would be happy to accept yours. \$\endgroup\$ – par Nov 22 '15 at 9:27
3
\$\begingroup\$

Very nifty-looking code right there. However, you should declare table as private final. Also, you don't need to initialize each array component of table to null, Java already does this for you. What comes to insert, you could write simply

table[index] = new HashEntry(key, value);

omitting the return statement. Point is to write only necessary statements. In getValue, you might want to check whether table[index] is null, since if that is the case, your implementation will throw NullPointerException.

\$\endgroup\$
  • \$\begingroup\$ Nice answer, clear and understandable. What do you think of the getKeyIndex method in the HashTable class, could this be improved (I was a bit unsure myself)? \$\endgroup\$ – par Nov 21 '15 at 18:11
  • 1
    \$\begingroup\$ I am not an expert on hashing, yet your implementation seems sufficient. However, I would consider using/reusing String.hashCode: it seems to do pretty much the same you do, but the point is that each String computes its hashCode only once and caches it (subsequent calls to hashCode will just return the cached hash value), so if you would use just String.hashCode instead of getKeyIndex, you would have better performance. \$\endgroup\$ – coderodde Nov 21 '15 at 18:24
  • \$\begingroup\$ The caching sounds like good advice, so how would I add a 'hashCode' variable to the specific String object I am working with? I would google this, but I am not sure what search terms to use. \$\endgroup\$ – par Nov 22 '15 at 21:24
  • 1
    \$\begingroup\$ I can't parse your question what comes to "add a hashCode variable". Create a String. Call hashCode on it; it will compute the hash code, cache it, and finally return it. Call hashCode one more time, and your String will return the cached value without actually computing it. This is all because strings are immutable (do not change state). \$\endgroup\$ – coderodde Nov 23 '15 at 15:45
  • \$\begingroup\$ Sorry, I massively miss-read what you was saying. Caching sounds like a good idea. Although correct me if I am wrong, the caching process itself would likely rely on an implementation of a hash map. \$\endgroup\$ – par Nov 23 '15 at 19:00

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.