Friday, December 27, 2013

Creating our own hashmap in java

This is an attempt to come up with my own hashmap in java. It serves all basic needs of original java.util.HashMap with O(1) complexity in read operations.
To look into the internals of java.util.HashMap itself, see here
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
package algorithms.hashmap;
 
/**
 * @author ntallapa
 *
 */
public class TMHashMap {
    // for simplicity size is taken as 2^4
    private static final int SIZE = 16;
    private Entry table[] = new Entry[SIZE];
 
    /**
     * User defined simple Map data structure
     * with key and value.
     * This is also used as linked list in case multiple
     * key-value pairs lead to the same bucket with same
     * hashcodes and different keys (collisions) using
     * pointer 'next'.
     *
     * @author ntallapa
     */
    class Entry {
        final String key;
        String value;
        Entry next;
 
        Entry(String k, String v) {
            key = k;
            value = v;
        }
 
        public String getValue() {
            return value;
        }
 
        public void setValue(String value) {
            this.value = value;
        }
 
        public String getKey() {
            return key;
        }
    }
 
    /**
     * Returns the entry associated with the specified key in the
     * HashMap.  Returns null if the HashMap contains no mapping
     * for the key.
     */
    public Entry get(String k) {
        int hash = k.hashCode() % SIZE;
        Entry e = table[hash];
 
        // if bucket is found then traverse through the linked list and
        // see if element is present
        while(e != null) {
            if(e.key.equals(k)) {
                return e;
            }
            e = e.next;
        }
        return null;
    }
 
    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     */
    public void put(String k, String v) {
        int hash = k.hashCode() % SIZE;
        Entry e = table[hash];
        if(e != null) {
            // it means we are trying to insert duplicate
            // key-value pair, hence overwrite the current
            // pair with the old pair
            if(e.key.equals(k)) {
                e.value = v;
            } else {
                // traverse to the end of the list and insert new element
                // in the same bucket
                while(e.next != null) {
                    e = e.next;
                }
                Entry entryInOldBucket = new Entry(k, v);
                e.next = entryInOldBucket;
            }
        } else {
            // new element in the map, hence creating new bucket
            Entry entryInNewBucket = new Entry(k, v);
            table[hash] = entryInNewBucket;
        }
    }
 
    // for testing our own map
    public static void main(String[] args) {
        TMHashMap tmhm = new TMHashMap();
 
        tmhm.put("Niranjan", "SMTS");
        tmhm.put("Ananth", "SSE");
        tmhm.put("Niranjan", "SMTS1");
        tmhm.put("Chandu", "SSE");
 
        Entry e = tmhm.get("Niranjan");
        System.out.println(""+e.getValue());
    }
}
Output is ‘SMTS1′ which says when key is duplicated, it is getting replaced.
To cross verify the concept like collisions we need to choose the user defined key instead of ‘String’, I hope one can take it further from here on :)

No comments: