More‎ > ‎

How Much JUnit Test Code is Needed for a Minimal HashMap Implementation in Java?

BY MARKUS SPRUNCK


This article describes a basic implementation of a HashMap and demonstrates the minimal needed test code. HashMaps are one of the most powerful data structures. The standard Java implementation is good for all standard tasks. Sometimes it is necessary to reduce a complex implementation like the standard Java class java.util.HashMap to understand the underling concepts.

Figure 1: Running the Example Code with EclEmma in Eclipse

You will see that with an 100% line and branch coverage approach for unit tests - the implementation of utility and/or framework classes should have a ratio of ~60% test code and ~40% production code. This is a rule of thumb and not a strict law, but I did the same for a larger web application (based on Spring Framework, JPA and Hibernate) and came to comparable results. 

Minimal HashMap Java Example Code with JUnit Test Code

The following implementation is one of the simplest one I can imagine (no re-sizing and re-hashing) and the test code has a 100% code coverage. Based on this sample - it gets obvious how much test code is needed for a framework and/or utility class implementation.

File MiniHashMap.java - implements a minimal hash map:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
package com.sprunck.sample;

public class MiniHashMap<K, V> {

    static class Entry<K, V> {

        private final K key;

        private V value;

        private MiniHashMap.Entry<K, V> next = null;

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

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(final V value) {
            this.value = value;
        }

        public void setNext(final Entry<K, V> newEntry) {
            next = newEntry;
        }

        public Entry<K, V> getNext() {
            return next;
        }

        public boolean isNotLast() {
            return (next != null);
        }
    }

    private final static int DEFAULT_CAPACITY = 16;

    private int capacity = DEFAULT_CAPACITY;
    private Entry<K, V>[] values = null;

    public MiniHashMap() {
        this(DEFAULT_CAPACITY);
    }

    public MiniHashMap(int capacity) {
        if (capacity > DEFAULT_CAPACITY) {
            this.capacity = capacity;
        }
        values = new Entry[this.capacity];
    }

    public void put(final K key, final V value) {
        // select bucket
        final int index = getIndex(key.hashCode());
        Entry<K, V> current = values[index];
        if (null == current) {
            // insert if still empty
            values[index] = new Entry<K, V>(key, value);
        } else {
            if (key.equals(current.getKey())) {
                // change value if already in the hash map and stop 
                current.setValue(value);
                return;
            }
            while (current.isNotLast()) {
                // search all entries in the bucket
                current = current.getNext();
                if (key.equals(current.getKey())) {
                    // change value if already in the hash map and stop 
                    current.setValue(value);
                    return;
                }
            }
            // insert at the end
            current.setNext(new Entry<K, V>(key, value));
        }
    }

    public boolean remove(final K key) {
        // select bucket
        final int index = getIndex(key.hashCode());
        Entry<K, V> current = values[index];
        Entry<K, V> previous = null;
        while (null != current) {
            if (key.equals(current.getKey())) {
                if (null == previous) {
                    // remove first entry + stop
                    values[index] = current.getNext();
                } else {
                    // remove middle + stop
                    previous.setNext(current.getNext());
                    current = null;
                }
                return true;
            }
            // continue with the next entries
            previous = current;
            current = current.getNext();
        }
        return false;
    }

    public V get(final K key) {
        final int index = getIndex(key.hashCode());
        Entry<K, V> current = values[index];
        while (null != current) {
            if (key.equals(current.getKey())) {
                return current.getValue();
            }
            current = current.getNext();
        }
        return null;
    }

    private int getIndex(int hash) {
        if (hash < 0) {
            hash = -hash;
        }
        return (hash % capacity);
    }
}

File MiniHashMapTest.java -implements tests for the minimal hash map:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
package com.sprunck.sample;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;

import java.util.HashMap;

import org.junit.Test;

public class MiniHashMapTest {

    @Test
    public void testRemove() {
        final MiniHashMap<String, Integer> map = new MiniHashMap<String, Integer>();
        map.put("Lars", 1);
        map.put("Günther", 12);
        map.put("Max", 2);

        assertEquals(null, map.get("Markus"));
        assertEquals(1, map.get("Lars"), 0);
        assertEquals(2, map.get("Max"), 0);
        assertEquals(12, map.get("Günther"), 0);

        map.remove("Max");
        assertEquals(null, map.get("Markus"));
        assertEquals(1, map.get("Lars"), 0);
        assertEquals(null, map.get("Max"));
        assertEquals(12, map.get("Günther"), 0);

        assertEquals(true, map.remove("Lars"));
        assertEquals(false, map.remove("Lars"));
        assertEquals(null, map.get("Markus"));
        assertEquals(null, map.get("Lars"));
        assertEquals(null, map.get("Max"));
        assertEquals(12, map.get("Günther"), 0);

        map.put("Lars", 1);
        map.put("Günther", 12);
        map.put("Max", 2);
        assertEquals(true, map.remove("Günther"));

    }

    @Test
    public void testStandard() {
        final MiniHashMap<String, Integer> map = new MiniHashMap<String, Integer>();
        map.put("Lars", 1);
        map.put("Günther", 12);
        map.put("Max", 2);

        assertEquals(null, map.get("Markus"));
        assertEquals(1, map.get("Lars"), 0);
        assertEquals(2, map.get("Max"), 0);
        assertEquals(12, map.get("Günther"), 0);

    }

    @Test
    public void testDoublePut() {
        final MiniHashMap<String, Integer> map = new MiniHashMap<String, Integer>();
        map.put("Lars", 1);
        map.put("Günther", 12);

        assertEquals(1, map.get("Lars"), 0);
        assertEquals(12, map.get("Günther"), 0);

        map.put("Lars", 14);
        map.put("Günther", 122);
        map.put("Fred", 11111);
        assertEquals(14, map.get("Lars"), 0);
        assertEquals(122, map.get("Günther"), 0);
    }

    @Test
    public void testBigNumber() {
        final MiniHashMap<String, Integer> map = new MiniHashMap<String, Integer>();
        final int maxIndex = 33; // set this to big number 
        for (int i = 0; i < maxIndex; i++) {
            map.put("Tom" + String.valueOf(i), i);
        }

        for (int i = 0; i < maxIndex; i++) {
            assertEquals(map.get("Tom" + String.valueOf(i)), i, 0);
        }

    }

    @Test
    public void testRemoveBigNumber() {
        final MiniHashMap<String, Integer> map = new MiniHashMap<String, Integer>();
        final int maxIndex = 1000;
        for (int i = 0; i < maxIndex; i++) {
            final String key = "Tom" + String.valueOf(i);
            map.put(key, i);
        }

        for (int i = maxIndex / 3; i < (maxIndex / 2); i++) {
            assertTrue(map.remove("Tom" + String.valueOf(i)));
        }

        for (int i = 0; i < maxIndex; i++) {
            if ((i >= (maxIndex / 3)) && (i < (maxIndex / 2))) {
                assertEquals(null, map.get("Tom" + String.valueOf(i)));
            } else {
                assertEquals(map.get("Tom" + String.valueOf(i)), i, 0);
            }
        }
    }

    @Test
    public void testRandom() {
        final MiniHashMap<String, Integer> map = new MiniHashMap<String, Integer>(997);
        final HashMap<String, Integer> mapJdK = new HashMap<String, Integer>(997);

        final int maxIndex = 10000;
        for (int i = 0; i < maxIndex; i++) {
            final String key = "Tom" + String.valueOf((int) (Math.random() * maxIndex));
            map.put(key, i);
            mapJdK.put(key, i);
            assertEquals(map.get(key), mapJdK.get(key), 0);
        }

        for (int i = 0; i < maxIndex; i++) {
            final String key = "Tom" + String.valueOf((int) (Math.random() * maxIndex));
            map.put(key, i);
            mapJdK.put(key, i);
            assertEquals(map.get(key), mapJdK.get(key), 0);
        }

        for (int i = 0; i < maxIndex; i++) {
            final String key = "Tom" + String.valueOf((int) (Math.random() * maxIndex));
            if ((null != map.get(key)) || (null != mapJdK.get(key))) {
                assertEquals(map.get(key), mapJdK.get(key), 0);
            }
        }

        for (int i = 0; i < maxIndex; i++) {
            final String key = "Tom" + String.valueOf((int) (Math.random() * maxIndex));
            map.remove(key);
            mapJdK.remove(key);
            assertNull(map.get(key));
            assertNull(mapJdK.get(key));
        }
    }
}

Conclusion

  • A test implementation of utility classes should have a ratio of ~60% test code
    and ~40% production code.

Sponsored Link