1
\$\begingroup\$

For an assignment I have to make a HashTable using double hashing, but for the hashing part I am not allowed to use Object#hashCode(), so I have to write my own.

So far I have the following code and I am looking for feedback if I am on the right track or if I should go for a different approach (see hash and hash2 methods).

public class DoubleHashing<Key, Value> {

private int N;
private int M;
private Key[] keys;
private Value[] vals;

public DoubleHashing(final int capacity) {
    M = capacity;
    keys = (Key[]) new Object[M];
    vals = (Value[]) new Object[M];
}

public int hash(final Key key) {
    int hashKey = 0;
    if (key instanceof String) {
        final String k = (String) key;
        for (int i = 0; i < k.length(); i++) {
            int charCode = k.charAt(i);
            hashKey = ((hashKey * 27) + charCode) % M;
        }
    }
    return hashKey;
}

public int hash2(final Key key) {
    int hashKey = 0;
    if (key instanceof String) {
        final String k = (String) key;
        for (int i = 0; i < k.length(); i++) {
            int charCode = k.charAt(i);
            hashKey = 5 - ((hashKey * 27) + charCode) % 5;
        }
    }
    return hashKey;
}

public void put(final Key key, final Value val) {
    if (N == M) {
        System.err.println("Table is full");
        return;
    }
    int i;
    for (i = hash(key); keys[i] != null; i = (i + 1) % M)
        if (keys[i].equals(key)) { vals[i] = val; return; }
    keys[i] = key;
    vals[i] = val;
    N++;
}

public Value get(final Key key) {
    for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
        if (keys[i].equals(key))
            return vals[i];
    return null;
}

public int size() {
    return N;
}
}
\$\endgroup\$
4
\$\begingroup\$

Use meaningful names for your fields:

private int N;
private int M;

What do those fields hold? What is the purpose of them?
Ask yourself those questions and use names that represent the meaning of your field:

private int size;
private int capacity;

Don't cast where you don't need to:

keys = (Key[]) new Object[M];
vals = (Value[]) new Object[M];

This makes no sense; why do you cast a generic Object[] array to a Key[]/Value[] array?
Simply create them without casting:

keys = new Key[M];
vals = new Value[M];

Your hashing methods don't return hashes

Your code is entirely broken in that regard. They only work for Strings and you use them for getting your index. This is not how hashing works!
I don't know if this is a restriction of your assignment, but no matter how large the capacity of your table is, your hashing method should always return the same value in order to be comparable to other objects.

\$\endgroup\$
  • \$\begingroup\$ @GaintTree, yes, I had to rename my fields. I cast because I cannot directly instantiate Type Parameters in my class, what makes me use the Object class. And yes, I have only made it to String to test. What would be another way to hash in an Universal way for all objects? \$\endgroup\$ – Kevin S Oct 13 '15 at 19:46
  • \$\begingroup\$ @KevinS hashCode() is the only common way to hash an object. If you only have to hash Strings, then don't use parameters (Key/Value), but restrict your methods to only String objects. If you want to hash objects of various types, you have to write a hash function for each and every one of the different types you expect. \$\endgroup\$ – GiantTree Oct 13 '15 at 20:10

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.