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 :)

4 comments:

oakleyses said...

louis vuitton handbags, oakley sunglasses, louboutin, longchamp outlet, nike shoes, louis vuitton outlet stores, chanel handbags, burberry outlet, prada outlet, jordan shoes, tiffany and co, michael kors outlet, tory burch outlet, louis vuitton outlet, longchamp handbags, nike free, true religion jeans, michael kors outlet, kate spade outlet, polo ralph lauren outlet, tiffany and co, prada handbags, polo ralph lauren outlet, michael kors outlet, michael kors outlet, longchamp handbags, oakley sunglasses, ray ban sunglasses, kate spade handbags, burberry outlet, louis vuitton outlet, louboutin outlet, louboutin, coach factory outlet, air max, air max, coach outlet, gucci outlet, christian louboutin shoes, michael kors outlet, coach purses, ray ban sunglasses, michael kors outlet, louis vuitton, coach outlet store online, true religion jeans, oakley sunglasses cheap

oakleyses said...

ralph lauren, lululemon, air max, hollister, north face, nike air max, polo lacoste, vanessa bruno, timberland, vans pas cher, louboutin, louis vuitton, oakley pas cher, air max pas cher, nike roshe run, air max, true religion outlet, barbour, sac longchamp, air force, hollister, sac louis vuitton, nike free, polo ralph lauren, nike trainers, louis vuitton uk, nike roshe, sac hermes, longchamp, michael kors, sac burberry, sac guess, mulberry, new balance pas cher, converse pas cher, sac louis vuitton, hogan outlet, nike tn, north face, true religion outlet, ray ban pas cher, michael kors, air jordan, nike blazer, nike free pas cher, michael kors pas cher, abercrombie and fitch, ray ban sunglasses

oakleyses said...

mac cosmetics, mont blanc, marc jacobs, canada goose outlet, nike huarache, vans shoes, soccer jerseys, hollister, giuseppe zanotti, beats by dre, abercrombie and fitch, longchamp, insanity workout, celine handbags, bottega veneta, ghd, nfl jerseys, north face outlet, chi flat iron, ugg boots, birkin bag, ugg australia, canada goose, herve leger, ugg pas cher, rolex watches, valentino shoes, canada goose uk, canada goose, ferragamo shoes, canada goose, ugg boots, uggs outlet, north face jackets, soccer shoes, asics running shoes, new balance shoes, p90x, lululemon outlet, canada goose jackets, mcm handbags, instyler, babyliss pro, ugg, wedding dresses, jimmy choo outlet, reebok outlet, nike roshe run

oakleyses said...

parajumpers, karen millen, air max, converse, pandora charms, moncler, louboutin, moncler, links of london, lancel, juicy couture outlet, oakley, hollister, pandora charms, supra shoes, thomas sabo, canada goose, gucci, wedding dresses, timberland boots, swarovski crystal, air max, coach outlet store online, moncler, ray ban, canada goose, moncler, ugg, louis vuitton, swarovski, hollister, montre homme, moncler, hollister clothing store, ralph lauren, rolex watches, moncler outlet, moncler, iphone 6 cases, baseball bats, juicy couture outlet, toms shoes, vans, pandora jewelry, ugg, converse shoes