2
\$\begingroup\$

This is my own implementation of an hashtable. I would like to receive some reviews or some feedbacks.

public class HashTableEntry<K,V> {

        private K key;
        private V value;
        private HashTableEntry<K,V> next;

        public HashTableEntry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public HashTableEntry<K, V> getNext() {
            return next;
        }

        public void setNext(HashTableEntry<K, V> next) {
            this.next = next;
        }
}

public class HashTable<K, V> {

    private static int DEFAULT_CAPACITY = 31;

    private HashTableEntry<K,V>[] table;

    @SuppressWarnings("unchecked")
    public HashTable() {
        table = (HashTableEntry<K,V>[])new Object[DEFAULT_CAPACITY];
    }

    @SuppressWarnings("unchecked")
    public HashTable(int capacity) {
        table = (HashTableEntry<K,V>[])new Object[capacity];
    }

    public void put(K key, V value) {

        int index = getIndex(key);

        HashTableEntry<K,V> entry = getLastEntry(table[index]);

        entry.setNext(new HashTableEntry<K,V>(key, value));             
    }

    public V get(K key) {

        int index = getIndex(key);

        return findValue(table[index], key);
    }

    private int getIndex(K key) {

        return key.hashCode() % table.length;
    }

    private HashTableEntry<K,V> getLastEntry(HashTableEntry<K,V> entry) {

        if (entry == null) return null;

        HashTableEntry<K,V> currentEntry = entry;

        while(currentEntry.getNext() != null)
            currentEntry = currentEntry.getNext();

        return currentEntry;
    }

    private V findValue(HashTableEntry<K,V> entry, K key) {

        if (entry == null) return null;

        HashTableEntry<K,V> currentEntry = entry;

        while(currentEntry.getNext() != null) {

            if (currentEntry.getKey().equals(key)) {
                return currentEntry.getValue();
            }

            currentEntry = currentEntry.getNext();
        }

        return null;
    }
}
\$\endgroup\$
1
\$\begingroup\$

With two tightly related classes like HashTable and HashTableEntry, you should probably nest them inside each other:

public class HashTable<K, V> {
    public static class Entry<K, V> {
        ...
    }
    ...
}

This way, the relationship between the classes is clear.


In your Entry class, you make it mutable. However, why not make it immutable? Immutability wouldn't cost much, but it would make some stuff easier to keep track of, such as providing the user an immutable view of your hashtable (this may be undesired, but it's what I'd do).

public static class Entry<K,V> { // This was nested within HashTable<K, V>
    private final K key;
    private final V value;
    private final Entry<K,V> next;

    public Entry(K key, V value, Entry<K, V> next) {
        this.key = key;
        this.value = value;
        this.next = next; // This could be changed by the user, so we aren't quite immutable yet; we'd have to do a deep copy on `next`
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public Entry<K, V> getNext() {
        return next;
    }

    public Entry<K, V> withNext(Entry<K, V> newNext) {
        return new Entry<>(key, value, newNext);
    }
}

Interestingly, you are combining table entries with a linked-list. This makes sense from the implementation viewpoint of a hashtable, but for readability's sake, I recommend removing the Entry<K, V> next entirely and simply using an array of LinkedList in your HashTable class. If you don't want to use the built-in LinkedList class, I still feel it is clearer if you separate these two unrelated pieces of the hashtable.

This would require some other changes in the code as well.


In getLastEntry and findValue, you return null when the request cannot be met. However, this is a little bit unclear. I'd recommend instead using Optional<Entry<K, V>> and Optional<V> as your return types so you can just do this:

private Optional<V> findValue(HashTableEntry<K,V> entry, K key) {
    if (entry == null) return Optional.empty();

    HashTableEntry<K,V> currentEntry = entry;

    while(currentEntry.getNext() != null) {
        if (currentEntry.getKey().equals(key)) {
            return Optional.of(currentEntry.getValue());
        }

        currentEntry = currentEntry.getNext();
    }

    return Optional.empty();
}

Then to get the value, you'd call optional.get(), but first you should check optional.isPresent(). This speaks more clearly than a null, so I personally find it easier to follow in this case.

\$\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.