Creating our own hashmap in java

MARCH 11, 2013 BY NIRANJAN TALLAPALLI 6 COMMENTS

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