HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Simple Chaining Implementation of HashMap

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationsimplehashmapchaining

Problem

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 {
    private class Entry {
      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);
        }
    }
}

Solution

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]);
        }
    }

Code Snippets

public void put(K key, V value) {
    int hash = hash(key);
    table[hash] = new Entry(key, value, table[hash]);
}
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]);
        }
    }

Context

StackExchange Code Review Q#136491, answer score: 2

Revisions (0)

No revisions yet.