How Hash Map Works

24 07 2014

How Hash Map Works

  • Hash Map Internally work as Linked List.
  • It is implemented array of Entry class.
  • transient Entry[] table;

Entry Class

    static class Entry<K,V> implements Map.Entry<K,V> {

        final K key;

        V value;

        Entry<K,V> next;

        final int hash;

        /**

         * Creates new entry.

         */

        Entry(int h, K k, V v, Entry<K,V> n) {

            value = v;

            next = n;

            key = k;

            hash = h;

        }

        public final K getKey() {

            return key;

        }

        public final V getValue() {

            return value;

        }

        public final V setValue(V newValue) {

            V oldValue = value;

            value = newValue;

            return oldValue;

        }

        public final boolean equals(Object o) {

            if (!(o instanceof Map.Entry))

                return false;

  1. Entry e = (Map.Entry)o;

            Object k1 = getKey();

            Object k2 = e.getKey();

            if (k1 == k2 || (k1 != null && k1.equals(k2))) {

                Object v1 = getValue();

                Object v2 = e.getValue();

                if (v1 == v2 || (v1 != null && v1.equals(v2)))

                    return true;

            }

            return false;

        }

        public final int hashCode() {

            return (key==null   ? 0 : key.hashCode()) ^

                   (value==null ? 0 : value.hashCode());

        }

        public final String toString() {

            return getKey() + “=” + getValue();

        }

        /**

         * This method is invoked whenever the value in an entry is

         * overwritten by an invocation of put(k,v) for a key k that’s already

         * in the HashMap.

         */

        void recordAccess(HashMap<K,V> m) {

        }

        /**

         * This method is invoked whenever the entry is

         * removed from the table.

         */

        void recordRemoval(HashMap<K,V> m) {

        }

    }

  • Entry Class Contains

       final K key;

        V value;

        Entry<K,V> next;

       final int hash;

While initializing the default hash map, it will load the default values:

  /**

     * Constructs an empty <tt>HashMap</tt> with the default initial capacity

     * (16) and the default load factor (0.75).

     */

    public HashMap() {

  1. loadFactor = DEFAULT_LOAD_FACTOR;

        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

        table = new Entry[DEFAULT_INITIAL_CAPACITY];

        init();

    }

 hashmap

Adding Element to the Hash map:

public V put(K key, V value) {

        if (key == null)

            return putForNullKey(value);

        int hash = hash(key.hashCode());

        int i = indexFor(hash, table.length);

        for (Entry<K,V> e = table[i]; e != null; e = e.next) {

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

  1. value = value;
  2. recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i);

        return null;

    }

  • While adding Key, Value to the Hash Map first it will create the hash code for the key using hash function.

   /**

     * Applies a supplemental hash function to a given hashCode, which

     * defends against poor quality hash functions.  This is critical

     * because HashMap uses power-of-two length hash tables, that

     * otherwise encounter collisions for hashCodes that do not differ

     * in lower bits. Note: Null keys always map to hash 0, thus index 0.

     */

    static int hash(int h) {

        // This function ensures that hashCodes that differ only by

        // constant multiples at each bit position have a bounded

        // number of collisions (approximately 8 at default load factor).

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

   }

  • After that it will find the index using the indexFor function.

/**

     * Returns index for hash code h.

     */

    static int indexFor(int h, int length) {

        return h & (length-1);

    }

  • If we have the key and hash code is same then value will be replace, otherwise will add to another node in the linked list. New Entry node’s next will point to the previous node. Initial Entry node’s next will point to null value.

Getting Value from the Hash Map:

    /**

     * Returns the value to which the specified key is mapped,

     * or {@code null} if this map contains no mapping for the key.

     *

     * <p>More formally, if this map contains a mapping from a key

     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :

     * key.equals(k))}, then this method returns {@code v}; otherwise

     * it returns {@code null}.  (There can be at most one such mapping.)

     *

     * <p>A return value of {@code null} does not <i>necessarily</i>

     * indicate that the map contains no mapping for the key; it’s also

     * possible that the map explicitly maps the key to {@code null}.

     * The {@link #containsKey containsKey} operation may be used to

     * distinguish these two cases.

     *

     * @see #put(Object, Object)

     */

    public V get(Object key) {

        if (key == null)

            return getForNullKey();

        int hash = hash(key.hashCode());

        for (Entry<K,V> e = table[indexFor(hash, table.length)];

             e != null;

             e = e.next) {

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

                return e.value;

        }

        return null;

    }

  • While getting value from the hash map first it will get the hash value for the key using hash function
  • This function we already used for adding the hash map.
  • Using indexFor to find the index for that key and get the value from the map.
  • If we have to more than one value, it will check for the hash and keys to find the exact value.

How it is doing index for the next value?

In indexFor function always use bitwise and operator for the index position.

For example

    int a = 60;  /* 60 = 0011 1100 */ 

     int b = 13; /* 13 = 0000 1101 */

     int c = 0;

     c = a & b;       /* 12 = 0000 1100 */





Tech Sivam Tips

13 07 2014

Hi All,

All My Old Posts are available in http://techsivamtips.wordpress.com/

Planning to post only technical things in this blog.

Thanks for your support.








Follow

Get every new post delivered to your Inbox.

Join 1,494 other followers

%d bloggers like this: