current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite

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);
        }
    }
}
share|improve this question
1  
What you may and may not do after receiving answers. I've rolled back Rev 3 → 2. – 200_success♦ 23 hours ago
up vote 4 down vote

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

share|improve this answer
up vote 2 down vote

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]);
        }
    }
share|improve this answer
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.