3
\$\begingroup\$

I'm practicing writing my own simple version of a Java HashMap. I don't have much experience with generics in Java.

public class HashMap<K, V> {
    private class Entry<K, V> {
      private K key;
      private V value;
      private Entry next;

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

      public K getKey() {
            return key;
      }

      public V getValue() {
            return value;
      }
    }

    private final static int TABLE_SIZE = 32;
    private Entry[] table;

    public HashMap() {
          table = new Entry[TABLE_SIZE];
    }

    private int hash(K key) {
        return Math.abs(key.hashCode() % TABLE_SIZE);
    }

    public V get(K key) {
        int index = hash(key);
        Entry curr = table[index];
        while (curr != null) {
            if (curr.getKey().equals(key)) {
                return (V) curr.getValue();
            }
            curr = curr.next;
        }
        return null;
    }

    public V remove(K key) {
        int hash = hash(key);
        Entry curr = table[hash];
        if (curr == null) {
            return null;
        }
        if (curr.getKey().equals(key)) {
            V temp = (V) curr.getValue();
            table[hash] = curr.next;
            return temp;
        }
        while (curr.next != null) {
            if (curr.next.getKey().equals(key)) {
                V temp = (V) curr.next.getValue();
                curr.next = curr.next.next;
                return temp;
            }
        }
        return null;
    }

    public void put(K key, V value) {
        int hash = hash(key);
        Entry curr = table[hash];
        if (curr == null) {
            table[hash(key)] = new Entry(key, value);
        } else {
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = new Entry(key, value);
        }
    }
}
\$\endgroup\$
1
2
\$\begingroup\$

Choose a better value for TABLE_SIZE:

You should specially avoid powers of 2 for this value in the division method. Why?

Because for TABLE_SIZE equal to the hash will simply be the p lowest-order bits. Is better to design a hash function that depends on all the bits of the key, so a prime number not too close to a power of 2 is generally a better choice.

Put method:

Your put method can be greatly simplified and also you could implement it so it doesn't depend on the load factor. By adding a constructor in Entry that also receives the next element you will have something like this:

public void put(K key, V value) {
    int hash = hash(key);
    table[hash] = new Entry(key, value, table[hash]);
}

But you probably want to update the value if the key is already there :

   public void put(K key, V value) {
        Entry n = get(key);
        if(n != null) {
            n.value = value;               
        }
        else {
            int hash = hash(key);
            table[hash] = new Entry(key, value, table[hash]);
        }
    }
\$\endgroup\$
7
\$\begingroup\$

There is a bug in 'remove' method. A while loop never changes 'curr' object so in case when key is not equals then loop will never exit

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Yes, just have to add curr = curr.next; below if () { .. } block inside while loop in remove method. \$\endgroup\$
    – Ashwin
    Aug 24 '17 at 8:04
1
\$\begingroup\$

Overall this looks pretty good. Very readable. Nice formatting.

One issue I found is when you call put with a key that already has a value, rather than overwriting the value it just adds another entry to the list for that key's hash. I'm sure now it's been pointed out, you can solve the problem yourself.

Maybe you could also make it resize once it reaches a certain size over it's current table size.

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