1
\$\begingroup\$

I have implemented a very simple idea of HashMap, I tried to cover cases like "get, put, delete, containsKey, resize," etc in the following implementation. Please take a look and suggest improvements to my coding styles and thought processes.

Interface

public interface Map<K, V> {
    boolean isEmpty();

    int size();

    boolean containsKey(Object k);

    void print(); //testing purpose

    V get(Object k);

    V put(K k, V v);

    V delete(Object k);
}

Implementation of Map interface

package com.sa.design.map.custom;

import java.util.Arrays;
import java.util.Objects;

public class SaHashMap<K, V> implements Map<K, V> {

    private static final int initialCapacity = 1 << 4; // its always a power of 2
    private Entry<K, V>[] entries;
    private int size = 0;
    private double loadFactor = 0.75;
    private int capacity = initialCapacity;

    public SaHashMap() {
        this(initialCapacity);
    }

    public SaHashMap(int size) {
        this.capacity = size;
        entries = new Entry[size];
    }

    public boolean isEmpty() {
        return (size == 0);
    }

    public int size() {
        return size;
    }

    public Entry[] entries() {
        return entries.clone();
    }

    public boolean containsKey(Object k) {
        return get(k) != null;
    }

    public V get(Object k) {
        if (k == null) {
            return entries[0].value;
        }
        int pos = hash(k);
        Entry<K, V> entry = entries[pos];
        if (entry == null) {
            return null;
        }

        while (entry.next != null && !Objects.equals(entry.key, k)) {
            entry = entry.next;
        }

        if (Objects.equals(entry.key, k)) {
            return entry.value;
        }

        return null;
    }

    private int hash(Object k) {
        return Objects.hash(k) % entries.length;
    }

    public void print() {
        System.out.println(Arrays.toString(entries));
    }

    public V put(K k, V v) {
        if (shouldResize()) {
            resize();
        }
        Entry entry = new Entry(k, v, null);
        // handle null case.
        if (k == null) {
            Entry nullEntry = entries[0];
            if (nullEntry != null) {
                entry.next = nullEntry;
                entries[0] = entry;
            } else {
                entries[0] = entry;
                size++;
            }
            return v;
        }

        // find the bucket
        int pos = hash(k);
        if (putInternal(entry, entries, pos) != null) {
            size++;
            return v;
        }

        return v;
    }

    private V putInternal(Entry<K, V> entry, Entry[] entries, int pos) {
        Entry<K, V> existing = entries[pos];
        if (existing != null) {
            // if key is same, then update the value
            if (Objects.equals(existing.key, entry.key)) {
                existing.value = entry.value;
            } else {
                System.out.println("Found collision for put for key:: " + entry.key + " Value ::" + entry.value);
                // insert at the head of next (o(1) operation)
                Entry tmp = existing.next;
                entry.next = tmp;
                existing.next = entry;
            }
        } else {
            entries[pos] = entry;
        }

        return entry.value;
    }

    private boolean shouldResize() {
        return this.size > Math.ceil((double) this.capacity * this.loadFactor);
    }

    private void resize() {
        capacity = capacity * 2;
        int i = 0;
        Entry<K, V>[] oldTable = entries;
        // reset current state
        entries = new Entry[capacity];
        Arrays.fill(entries, null);
        size = 0;
        for (Entry<K, V> entry : oldTable) {
            // we need to read the nodes again
            // and insert it back, as bucket size increased
            // there should be a chance to reduce collision with new size
            // as long as no poor equals and hashcode
            Entry<K, V> tmp = entry;
            if (tmp != null) {
                while (tmp != null) {
                    put(tmp.key, tmp.value);
                    tmp = tmp.next;
                }

            }
        }
        System.out.println("Done Resize, New Capacity ::"+ capacity);
    }

    public V delete(Object k) {
        int pos = hash(k);
        Entry<K, V> entry = entries[pos];
        if(entry == null) return null;

        if (Objects.equals(entry.key, k)) {

            // if deleted node as nodes on it, lets give them a chance to re insert it back
            if(entry.next != null) {
                Entry<K,V> tmp = entry.next;
                while(tmp != null) {
                    put(tmp.key, tmp.value);
                    tmp = tmp.next;
                }
            }
            // mark current bukcet pos null as head is deleted now
            entries[pos] = null;
            size--;
            return entry.value;
        }
        // collision state, so we need find and delete and reattach nodes
        Entry<K, V> head = entry.next;
        Entry<K, V> parent = entry;
        // 1 [2,3,4]
        while (head != null) {
            if (Objects.equals(head.key, k)) {
                // re attach nodes
                parent.next = head.next;
                size--;
                return head.value;
            }
            parent = head;
            head = head.next;
        }

        return null;
    }


}

Entry class

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

    public Entry(K key, V value, Entry<K, V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }


    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;

        }

        if (!(o instanceof Entry)) {
            return false;
        }

        Entry e = (Entry) o;
        return Objects.equals(e.key, this.key)
                && Objects.equals(e.value, this.value);
    }

    @Override
    public String toString() {
        return "Entry{" +
                "key=" + key +
                ", value=" + value +
                ", next=" + next +
                '}';
    }

    @Override
    public int hashCode() {
        return Objects.hash(this.key, this.value);
    }
}

Tests

package com.sa.design.map.custom.test;

import com.sa.design.map.custom.Map;
import com.sa.design.map.custom.SaHashMap;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class SaJavaTest {

    private Map<String, Integer> map;

    @Before
    public void before() {
        map = new SaHashMap(16);
    }

    // Test if put is working fine
    @Test
    public void testPut() {
        map.put("A", 1);
        map.put("B", 2);
        Assert.assertEquals(2, map.size());
    }

    @Test
    public void testPutAndGet() {
        map.put("A", 1);
        map.put("B", 2);
        Assert.assertEquals(2, map.size());
        Integer v = map.get("A");
        Assert.assertEquals(Integer.valueOf(1), v);
    }

    @Test
    public void testPutAndDelete() {
        map.put("A", 1);
        map.put("B", 2);
        Assert.assertEquals(2, map.size());
        Integer v = map.delete("A");
        Assert.assertEquals(Integer.valueOf(1), v);
        Assert.assertEquals(1, map.size());
    }


    @Test
    public void testContiansKey() {
        map.put("A", 1);
        map.put("B", 2);
        Assert.assertEquals(2, map.size());
        boolean exist = map.containsKey("A");
        Assert.assertTrue(exist);
    }

    // Returns the head value of null entries bucket
    @Test
    public void testPutNull() {
        map.put(null, 2);
        map.put(null, 3);
        map.put(null, 4);
        Assert.assertEquals(1, map.size());
        Integer v = map.get(null);
        Assert.assertTrue(v != null);
        Assert.assertTrue(v == 4);
    }

    @Test
    public void testPut1000() {
        for(int i= 1; i<= 1000; i++) {
            map.put(Integer.toString(i), i);
        }
        for(int i= 1; i<= 1000; i++) {
            Integer v = map.get(Integer.toString(i));
            Assert.assertEquals(Integer.valueOf(i), map.get(Integer.toString(i)));
        }
    }

    @Test
    public void testPutAndDelete1000() {
        for(int i= 1; i<= 1000; i++) {
            map.put(Integer.toString(i), i);
        }
        for(int i= 1; i<= 1000; i++) {
            Integer v = map.delete(Integer.toString(i));
            Assert.assertEquals(null, map.get(Integer.toString(i)));
        }
        map.print();
    }


    @Test
    public void testPut10000() {
        for(int i= 1; i<= 10000; i++) {
            map.put(Integer.toString(i), i);
        }
        for(int i= 1; i<= 10000; i++) {
            Integer v = map.get(Integer.toString(i));
            Assert.assertEquals(Integer.valueOf(i), map.get(Integer.toString(i)));
        }

    }

}
```
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

Interface

There's a name conflict with java.util.map I'd try to avoid using names that are the same as existing library classes. Does print really belong on this interface? If you really wanted to have it as part of the implementation, it could be there without needing to be on the interface. However, it would be better to provide some kind of iterator (or add your entries method to the interface) so that it was possible for the client to iterate over the name/values in the map and print them out if desired.

Implementation

// its always a power of 2

This suggests that you're expecting the capacity of your map to always be a power of two. If the default constructors used, then this works. However, your custom constructor allows a capacity to be passed in. The client can pass in '3', at which point the capacity isn't going to be a power of two. If this linkage is important, consider rounding up/down to the nearest power when setting the initial capacity. The custom constructor also allows 0 to be passed in as a capacity in which case you get division by zero errors when calling other methods. You should probably default to initialCapacity in this scenario.

public boolean containsKey(Object k) {
    return get(k) != null;
}

It's often frowned upon to call public methods of a class from other methods. Consider pushing the implementation of get into a private method that can be called from both places.

Size bug

I don't think you're tracking size properly... 

map.put("A", 3) // size=1
map.put("A", 3) // size=2 .. even though it's overwriting the existing item

You're also treating null values as a special case, that doesn't increment the size

map.put("A", null) // size=0
map.put("A", 3) // size=1
map.put("A", null) // size=1

It's not clear from your tests what you're expecting here...

Tests

public class SaJavaTest {

Your test class name doesn't match the class you're testing. That's OK if you're testing multiple classes intentionally, however I'd still expect the name to have something to do with the unit being tested... 'Java' probably isn't the right name here.

public void testPut() {

As with most naming things, this is subjective, but I tend to not bother prefixing every test with the word test. It's in a test class, so this is really implied, every public method in a test class is a test. Instead these characters can be used to make the test name more descriptive. I like some form of 'method_condition_expectedResult'. So, for example:

put_twoItems_sizeTwo
get_validKey_valueRetrieved
containsKey_validKey_true

Consider trying to avoid redundancy in your test assertions. You're testing if adding two items has the right size in your testPut, do you really need to test it again with exactly the same setup in testPutAndGet.

public void testContiansKey() {

Small typo in name...

testPutNull

This is testing that you can use null as the key and that using the same key overwrites the previously added entry. I'd suggest that these are really two distinct tests.

@Test
public void put_null_ignored() {
    map.put("A", null);

    assertEquals(0, map.size());
}

@Test
public void put_previousValuePresentnull_overwrites() {
    map.put("A", 3);
    map.put("A", null);

    assertEquals((Integer)null, map.get("A"));
}

I think there are some tests missing here, about what you're expecting the behaviour to be if null is used as a value. As it stands, the behaviour seems a bit odd.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.