How to implement your own Map

This post is to show how you can implement a simple Map with only Put, Get and Size operations. This map implementation does not take care of any thread safety and just here to illustrate what all may needed to implement a map kind of data structure.

What all needed - 

1. eclispe -Juno
2. JDK 1.7
3. Junit 4.5
4. Hamcrest-all-1.1.jar

Test First -

package com.chatar.practice;

import org.junit.Assert;
import org.junit.Test;
import static org.hamcrest.CoreMatchers.*;

import com.chatar.pratice.MyMap;

public class MyMapTest {
   
    @Test(expected=NullPointerException.class)
    public void shouldThrowExceptionIfInsertingNullKey() {
        MyMap myMap = new MyMap();
        myMap.put(null, "some_value");
    }
   
    @Test(expected=NullPointerException.class)
    public void shouldThrowExceptionIfGetingValueForNullKey() {
        MyMap myMap = new MyMap();
        myMap.get(null);
    }
   
    @Test
    public void shouldAbleToPutValues() {
        MyMap myMap = new MyMap();
        myMap.put("key1", "value1");
        myMap.put("key2", "value2");       
        Assert.assertThat(myMap.size(), is(2));
    }
   
    @Test
    public void shouldReturnNullIfKeyNotFound() {
        MyMap myMap = new MyMap();       
        Assert.assertThat(myMap.get("key1"), nullValue());
    }
   
    @Test
    public void shouldOverrideValueIfKeyIsUnique() {
        MyMap myMap = new MyMap();
        myMap.put("key1", "value1");
        Assert.assertThat(myMap.size(), is(1));
        Assert.assertThat(myMap.get("key1"), is("value1"));
        myMap.put("key1", "value2");       
        Assert.assertThat(myMap.size(), is(1));
        Assert.assertThat(myMap.get("key1"), is("value2"));
       
    }
   
    @Test
    public void shouldGetValueByPassingKey() {
        MyMap myMap = new MyMap();
        myMap.put("key1", "value1");
        myMap.put("key2", "value2");       
        Assert.assertThat(myMap.size(), is(2));
        Assert.assertThat(myMap.get("key1"), is("value1"));
        Assert.assertThat(myMap.get("key2"), is("value2"));
    }
}

And Implementation -

package com.chatar.pratice;

public class MyMap {
   
    private Entry[] backets;
    private int size = 0;
   
    public MyMap() {}{
        backets = new Entry[128];
    }
   
    public void put(K key, V value) {
        validate(key);
        Entry entry = backets[backet(key)];
        if(entry != null) {
            addTo(entry, key, value);
        } else {
            backets[backet(key)] = new Entry(key, value);
        }
        size++;
    }

    public V get(K key) {
        validate(key);
        Entry entry = backets[backet(key)];
        while(entry != null && !key.equals(entry.key)) {
            entry = entry.next;
        }
        return entry != null ? entry.value : null;
    }
   
    public int size() {
        return size;
    }

    private void validate(K key) {
        if(key == null) {
            throw new NullPointerException("Key can't be null");   
        }
    }
   
    private void addTo(Entry entry, K key, V value) {
        boolean notFound = true;
        while(notFound) {
            if(entry.hasNext()) {
                if(entry.key.equals(key)) {
                    entry.value = value;
                    notFound = false;
                    size--;
                }
            }
            else if (entry.key.equals(key)) {
                entry.value = value;
                notFound = false;
                size--;
            }
        }
    }

    private int backet(K key) {
        return key.hashCode() % backets.length;
    }
   
    static class Entry {
        K key;
        V value;
        Entry next;
       
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
       
        public Entry next() {
            return next;
        }
       
        public boolean hasNext() {
            return next != null;
        }
    }
}