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

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

About these ads

27 Responses to Creating our own hashmap in java

  1. Pingback: Hashmap Internal Implementation Analysis in Java | java tech stack

  2. Koushik says:

    Hi, How to calculate the time o-notation complexity for your algm / program

    • It is O(1) for insertion and retrieval. I am making use of implicit hashcode method of string object. While inserting and retrieving I will get the hashcode from String implicit hashcode method and look for it in the entry map which is O(1).

  3. tarun says:

    Nicely code and very to understand.Thanks for sharing …..

  4. Abhik says:

    Niranjan,

    Great job on the blogs. One question though: this custom hashmap can only hold upto 16 (SIZE) entries- is it an implementation detail that you want your followers to be able to pick up?

    • thank you Abhik, I took the size as 16 to make it simple (2^4), and why powers of 2 is explained in another article ‘http://tekmarathon.wordpress.com/2012/12/04/hashmap-internal-implementation-analysis-in-java/’.

  5. Nitish says:

    Hi Niranjan,
    I really like the way you implemented it. I just have one quick question.
    In put method you are just checking key for the head element and not for all elements. Is there any specific reason or I am not able to get the correct idea ?

    Thanks

  6. Udhav says:

    I think the put element should check for HashCode collision instead of checking the first Entry from the table [].

  7. Eugene says:

    I Don’t understand: in this line – “Entry e = table[hash];”
    I get this exeption table[hash] = java.lang.IndexOutOfBoundsException : Invalid array index: -5 ?

  8. Vladislaaaav says:

    Hi,

    thank you for your posts, especially the one explaining HashMap implementation. That was what i was looking for for a long time. Regarding your hashmap

    1) In your put method you check equality of keys only for the 1st entry in the list. So, put doesn’t replace same keys afterwards, am I right?
    2) you don’t use that stuff with hash function, so size == power of 2 is irrelevant

    I’m just trying to understand if i get things correctly :) Thank you once more

  9. Raja says:

    really handy

    • Pranav says:

      hi am not sure about the get function. When there is already something there, it means it is a collision right? so when e!=null we should do the link list part of the code, and when e is null, we put it there as it is. Please correct me if my understanding is wrong..

  10. HM says:

    In line 77, you’re only checking for the first bucket, isn’t it? What if the buckets with keys were as follows. 1–>11–>21 (Chaining). And then you wish to insert a duplicate key 21 with another value. Your code will not reach that Entry node because you’ve written a while loop to iterate over the linked list in line 88. Please correct me if I am wrong. Thanks. And, great explanation. Thank you, again. :)

  11. dhruvaa says:

    Always nicely explained Niranjan! :)

    umm.. would you guide me with any pointers for developing understanding for algorithm development, plz? :)

  12. Pranav says:

    hi am not sure about the get function. When there is already something there, it means it is a collision right? so when e!=null we should do the link list part of the code, and when e is null, we put it there as it is. Please correct me if my understanding is wrong..

  13. Abc says:

    Thanks for the great article.

    I have been looking for such detailed explanations everywhere and i finally found this and your other one explaining the detailed implementation of the orginal hashmap.

    I have one question though:

    You said it does not use tail traversing when inserting new node in the linked list as it inserts at the head always. But in this implementation, why are you inserting at the tail?
    Was this deliberate or Am I missing something.

    Can you please answer this?

    Thanks

  14. Sumit says:

    I don’t think this implementation will work with every string. Taking a big string as key sometimes gives negative index.

  15. Sumit says:

    Can you bit explain on hashing part…can you share some good example on hashing

  16. kk says:

    Hi,
    In the Put method, if a duplicate value is inserted, you are overwriting the old value with the new value. The duplicate value could be anywhere in the linked list. But you are check the condition only on the first entry in the linked list. Correct me if I am wrong here.

  17. Hi,
    The below line i think can be better written
    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;

    —————————–

    for (Entry e = table[hash]; e != null; e = e.next) {
    if (e.key.equals(k)) {
    return e;
    }
    }

  18. Sayooj Valsan says:

    There is a bug in the implementation. At line 82, the implementation just traverse to the end, it doesn’t check if the key exists. This could lead to chaining duplicate values.

    The correct implementation is to check if the key exists inside the while loop. Please correct it.

  19. Dheeraj says:

    Hello Sir,

    many times i came across this statement about hashmap “HashMap doesn’t append the new element at tail instead it append new element at head to avoid tail traversing”.
    What if i add new entry to last of linked list. because in any case i need to traverse through linked list for checking key’s hash and key by equals.

    basically where this tail traversing applies, what can be the problem if i write the code in following way,

    public V put(K key, V value) {

    if (key == null)
    return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    Entry temp; //this temp will be updated and will store last element in linked list
    for (Entry e = table[i]; e != null; e = e.next) {
    temp = e;
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
    }
    }
    //will add new entry to this temp (temp.e = new Entry(hash, key, value, null))
    modCount++;
    addEntry(hash, key, value, i);
    return null;

    }

  20. bhuvnesh says:

    Hi TM,

    please update the above code @line 83 with this :

    if(e.next == null){
    break;
    }else{
    e = e.next;
    }

    because it give null pointer if there will be more than one value in any linked list.

    OR is there any alternative for this or there is some lack in my understanding of above code

    please let me know thanks

  21. Randheer says:

    Hey,

    Nice implementation!!

    Two things i would like to mention as modifications here are :

    1. In the put() method you should first check for null key, if key is null store it at table[0] index as null key has hascode 0. This satisfies the HashMap accepting one null key criteria.

    2. When you find an Entry present at a location in table, you start iterating the linked list and insert the new Entry at the end of the linked list in that bucket. Instead, you can add this new Entry to the head of the linked list. This would avoid unnecessary traversal of list. The same logic is used in the actual HashMap implementation of Java.

    Please correct me if I am wrong. Thanks!!

  22. Neelabh Singh says:

    In line 77. we are comparing the given k with the existing Key in the linked list.
    This only done for the head of linked list. There is also possibility, Inside the linked list given K
    and Key will be same so We have to override old value of Key (Key, oldValue) with new value of Key
    (K, newValue );
    Suppose for hash is same for the following (key, pairs) So they are in same linked list
    (Key, Value)
    (12, 4), (4, 5) (6, 8)
    Here 12, 12, 4, 6 , 6 are key. Suppose they have same hashcode.
    (12, 4)–> (4, 5)–>(6,8)
    Now some new pairs comes
    (12,5) 12 has same hashcode so updated value of head of the linkedlist with new value. So linked
    list will be
    (12, 5)–> (4, 5)–>(6,8)

    (9, 3)

    So insert new pair at the end of list
    (12, 5)–> (4, 5)–>(6,8)–> (9,6)

    Now (4, 9) comes linkedlist already contains it so update it with new value
    (12, 5)–> (4, 9)–>(6,8)–> (9,6)// I thing this is not implemented in your code, may be I am wrong. Please
    conform it.

  23. Neelabh Singh says:

    I implemented the above my comments please check it,
    public void put(String k, String v)
    {
    int hash=k.hashCode%SIZE;
    Entry e=table[hash];
    if(e!=null)
    {
    while(e.next!=null)
    {
    if(e.key.equal(k){
    e.value=v;
    return ;
    }
    e=e.next;
    }
    Entry entryInOldBucket=new Entry(k,v);
    e.next=entryInOldBucket;
    }
    else
    {
    Entry entryInNewBucket=new Entry(k,v);
    table[hash]=entryNewBucket;
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

java coding algorithms

before software can be reusable it first has to be usable - Ralph Johnson

Follow

Get every new post delivered to your Inbox.

Join 171 other followers