Java HashMap

http://www.geeksforgeeks.org/internal-working-of-hashmap-java/

A bucket is one element of HashMap array. It is used to store nodes. Two or more nodes can have the same bucket. In that case link list structure is used to connect the nodes. Buckets are different in capacity. A relation between bucket and capacity is as follows:

capacity = number of buckets * load factor

A single bucket can have more than one nodes, it depends on hashCode() method. The better your hashCode() method is, the better your buckets will be utilized.

Index Calculation in Hashmap

Hash code of key may be large enough to create an array. hash code generated may be in the range of integer and if we create arrays for such a range, then it will easily cause outOfMemoryException. So we generate index to minimize the size of array. Basically following operation is performed to calculate index.

index = hashCode(key) & (n-1).

where n is number of buckets or the size of array. In our example, I will consider n as default size that is 16.

http://www.geeksforgeeks.org/implementing-our-own-hash-table-with-separate-chaining-in-java/

// A node of chains

class HashNode<K, V>

{

    K key;

    V value;

    // Reference to next node

    HashNode<K, V> next;

    // Constructor

    public HashNode(K key, V value)

    {

        this.key = key;

        this.value = value;

    }

}

// Class to represent entire hash table

class Map<K, V>

{

    // bucketArray is used to store array of chains

    private ArrayList<HashNode<K, V>> bucketArray;

    // Current capacity of array list

    private int numBuckets;

    // Current size of array list

    private int size;

    // Constructor (Initializes capacity, size and

    // empty chains.

    public Map()

    {

        bucketArray = new ArrayList<>();

        numBuckets = 10;

        size = 0;

        // Create empty chains

        for (int i = 0; i < numBuckets; i++)

            bucketArray.add(null);

    }

    public int size() { return size; }

    public boolean isEmpty() { return size() == 0; }

    // This implements hash function to find index

    // for a key

    private int getBucketIndex(K key)

    {

        int hashCode = key.hashCode();

        int index = hashCode % numBuckets;

        return index;

    }

    // Method to remove a given key

    public V remove(K key)

    {

        // Apply hash function to find index for given key

        int bucketIndex = getBucketIndex(key);

        // Get head of chain

        HashNode<K, V> head = bucketArray.get(bucketIndex);

        // Search for key in its chain

        HashNode<K, V> prev = null;

        while (head != null)

        {

            // If Key found

            if (head.key.equals(key))

                break;

            // Else keep moving in chain

            prev = head;

            head = head.next;

        }

        // If key was not there

        if (head == null)

            return null;

        // Reduce size

        size--;

        // Remove key

        if (prev != null)

            prev.next = head.next;

        else

            bucketArray.set(bucketIndex, head.next);

        return head.value;

    }

    // Returns value for a key

    public V get(K key)

    {

        // Find head of chain for given key

        int bucketIndex = getBucketIndex(key);

        HashNode<K, V> head = bucketArray.get(bucketIndex);

        // Search key in chain

        while (head != null)

        {

            if (head.key.equals(key))

                return head.value;

            head = head.next;

        }

        // If key not found

        return null;

    }

    // Adds a key value pair to hash

    public void add(K key, V value)

    {

        // Find head of chain for given key

        int bucketIndex = getBucketIndex(key);

        HashNode<K, V> head = bucketArray.get(bucketIndex);

        // Check if key is already present

        while (head != null)

        {

            if (head.key.equals(key))

            {

                head.value = value;

                return;

            }

            head = head.next;

        }

        // Insert key in chain

        size++;

        head = bucketArray.get(bucketIndex);

        HashNode<K, V> newNode = new HashNode<K, V>(key, value);

        newNode.next = head;

        bucketArray.set(bucketIndex, newNode);

        // If load factor goes beyond threshold, then

        // double hash table size

        if ((1.0*size)/numBuckets >= 0.7)

        {

            ArrayList<HashNode<K, V>> temp = bucketArray;

            bucketArray = new ArrayList<>();

            numBuckets = 2 * numBuckets;

            size = 0;

            for (int i = 0; i < numBuckets; i++)

                bucketArray.add(null);

            for (HashNode<K, V> headNode : temp)

            {

                while (headNode != null)

                {

                    add(headNode.key, headNode.value);

                    headNode = headNode.next;

                }

            }

        }

    }

}

http://liujiacai.net/blog/2015/09/03/java-hashmap/
在语法层面继承接口Map是多余的，这么做仅仅是为了让阅读代码的人明确知道HashMap是属于Map体系的，起到了文档的作用

Cloneable这个接口设计的非常不好，最致命的一点是它里面竟然没有clone方法，也就是说我们自己写的类完全可以实现这个接口的同时不重写clone方法。

Map虽然并不是Collection，但是它提供了三种“集合视角”（collection views），与下面三个方法一一对应：

• Set<K> keySet()，提供key的集合视角
• Collection<V> values()，提供value的集合视角
• Set<Map.Entry<K, V>> entrySet()，提供key-value序对的集合视角，这里用内部类Map.Entry表示序对

• Map m = Collections.synchronizedMap(new HashMap(...)); 通过这种方式可以得到一个线程安全的map。

• 线程非安全，并且允许key与value都为null值，HashTable与之相反，为线程安全，key与value都不允许null值。
• 不保证其内部元素的顺序，而且随着时间的推移，同一元素的位置也可能改变（resize的情况）

/**

* Retrieve object hash code and applies a supplemental hash function to the

* result hash, 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.

*/

final int hash(Object k) {

int h = hashSeed;

if (0 != h && k instanceof String) {

return sun.misc.Hashing.stringHash32((String) k);

}



h ^= k.hashCode();



// 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);

}



/**

* Returns index for hash code h.

*/

static int indexFor(int h, int length) {

// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

return h & (length-1);

}

    public V put(K key, V value) {

        if (table == EMPTY_TABLE) {

            inflateTable(threshold);

        }

        if (key == null)

            return putForNullKey(value);

        int hash = hash(key);

        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;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i);

        return null;

    }

JDK8 

* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
transient Node<K,V>[] table;

     * Computes key.hashCode() and spreads (XORs) higher bits of hash

     * to lower.  Because the table uses power-of-two masking, sets of

     * hashes that vary only in bits above the current mask will

     * always collide. (Among known examples are sets of Float keys

     * holding consecutive whole numbers in small tables.)  So we

     * apply a transform that spreads the impact of higher bits

     * downward. There is a tradeoff between speed, utility, and

     * quality of bit-spreading. Because many common sets of hashes

     * are already reasonably distributed (so don't benefit from

     * spreading), and because we use trees to handle large sets of

     * collisions in bins, we just XOR some shifted bits in the

     * cheapest possible way to reduce systematic lossage, as well as

     * to incorporate impact of the highest bits that would otherwise

     * never be used in index calculations because of table bounds.

    static final int hash(Object key) {

        int h;

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

    }

hashCode(key) & (length-1)

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;

}

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

方法2其实也比较好理解：

因为length为2的指数倍，所以length-1所对应的二进制位都为1，然后在与hashCode(key)做与运算，即可得到[0,length)内的索引

但是这里有个问题，如果hashCode(key)的大于length的值，而且hashCode(key)的二进制位的低位变化不大，那么冲突就会很多，举个例子：

Java中对象的哈希值都32位整数，而HashMap默认大小为16，那么有两个对象那么的哈希值分别为：0xABAB0000与0xBABA0000，它们的后几位都是一样，那么与16异或后得到结果应该也是一样的，也就是产生了冲突。

造成冲突的原因关键在于16限制了只能用低位来计算，高位直接舍弃了，所以我们需要额外的哈希函数而不只是简单的对象的hashCode方法了。
具体来说，就是HashMap中hash函数干的事了

首先有个随机的hashSeed，来降低冲突发生的几率

然后如果是字符串，用了sun.misc.Hashing.stringHash32((String) k);来获取索引值

最后，通过一系列无符号右移操作，来把高位与低位进行异或操作，来降低冲突发生的几率

右移的偏移量20，12，7，4是怎么来的呢？因为Java中对象的哈希值都是32位的，所以这几个数应该就是把高位与低位做异或运算，至于这几个数是如何选取的，就不清楚了，网上搜了半天也没统一且让人信服的说法，大家可以参考下面几个链接：

• http://stackoverflow.com/questions/7922019/openjdks-rehashing-mechanism/7922219#7922219
• http://stackoverflow.com/questions/9335169/understanding-strange-java-hash-function/9336103#9336103
• http://stackoverflow.com/questions/14453163/can-anybody-explain-how-java-design-hashmaps-hash-function/14479945#14479945

在哈希表容量（也就是buckets或slots大小）为length的情况下，为了使每个key都能在冲突最小的情况下映射到[0,length)（注意是左闭右开区间）的索引（index）内，一般有两种做法：

1. 让length为素数，然后用hashCode(key) mod length的方法得到索引
2. 让length为2的指数倍，然后用hashCode(key) & (length-1)的方法得到索引

HashTable用的是方法1，HashMap用的是方法2。

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;key为null的Entry用于放在table[0]中

public V get(Object key) {

//单独处理key为null的情况

if (key == null)

return getForNullKey();

Entry<K,V> entry = getEntry(key);



return null == entry ? null : entry.getValue();

}

private V getForNullKey() {

if (size == 0) {

return null;

}

//key为null的Entry用于放在table[0]中，但是在table[0]冲突链中的Entry的key不一定为null

//所以需要遍历冲突链，查找key是否存在

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

if (e.key == null)

return e.value;

}

return null;

}

final Entry<K,V> getEntry(Object key) {

if (size == 0) {

return null;

}



int hash = (key == null) ? 0 : hash(key);

//首先定位到索引在table中的位置

//然后遍历冲突链，查找key是否存在

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 != null && key.equals(k))))

return e;

}

return null;

}

HashMap中提供的三种集合视角，底层都是用HashIterator实现的。

注意到modCount声明为volatile，保证线程之间修改的可见性。

1 2 3

final Entry<K,V> nextEntry() {     if (modCount != expectedModCount)         throw new ConcurrentModificationException();

由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

private abstract class HashIterator<E> implements Iterator<E> {

Entry<K,V> next;        // next entry to return

//在初始化Iterator实例时，纪录下当前的修改次数

int expectedModCount;   // For fast-fail

int index;              // current slot

Entry<K,V> current;     // current entry



HashIterator() {

expectedModCount = modCount;

if (size > 0) { // advance to first entry

Entry[] t = table;

//遍历HashMap的table，依次查找元素

while (index < t.length && (next = t[index++]) == null)

;

}

}



public final boolean hasNext() {

return next != null;

}



final Entry<K,V> nextEntry() {

//在访问下一个Entry时，判断是否有其他线程有对集合的修改

//说明HashMap是线程非安全的

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

Entry<K,V> e = next;

if (e == null)

throw new NoSuchElementException();



if ((next = e.next) == null) {

Entry[] t = table;

while (index < t.length && (next = t[index++]) == null)

;

}

current = e;

return e;

}



public void remove() {

if (current == null)

throw new IllegalStateException();

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

Object k = current.key;

current = null;

HashMap.this.removeEntryForKey(k);

expectedModCount = modCount;

}

}



private final class ValueIterator extends HashIterator<V> {

public V next() {

return nextEntry().value;

}

}



private final class KeyIterator extends HashIterator<K> {

public K next() {

return nextEntry().getKey();

}

}



private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {

public Map.Entry<K,V> next() {

return nextEntry();

}

}

    public Set<K> keySet() {

        Set<K> ks = keySet;

        return (ks != null ? ks : (keySet = new KeySet()));

    }

    private final class KeySet extends AbstractSet<K> {

        public Iterator<K> iterator() {

            return newKeyIterator();

        }

        public int size() {

            return size;

        }

        public boolean contains(Object o) {

            return containsKey(o);

        }

        public boolean remove(Object o) {

            return HashMap.this.removeEntryForKey(o) != null;

        }

        public void clear() {

            HashMap.this.clear();

        }

    }

    public Collection<V> values() {

        Collection<V> vs = values;

        return (vs != null ? vs : (values = new Values()));

    }

    private final class Values extends AbstractCollection<V> {

        public Iterator<V> iterator() {

            return newValueIterator();

        }

        public int size() {

            return size;

        }

        public boolean contains(Object o) {

            return containsValue(o);

        }

        public void clear() {

            HashMap.this.clear();

        }

    }

序列化

• Object.hashCode方法对于一个类的两个实例返回的是不同的哈希值

我们可以试想下面的场景：

我们在机器A上算出对象A的哈希值与索引，然后把它插入到HashMap中，然后把该HashMap序列化后，在机器B上重新算对象的哈希值与索引，这与机器A上算出的是不一样的，所以我们在机器B上get对象A时，会得到错误的结果。

所以说，当序列化一个HashMap对象时，保存Entry的table是不需要序列化进来的，因为它在另一台机器上是错误的。

因为这个原因，HashMap重现了writeObject与readObject 方法

private void writeObject(java.io.ObjectOutputStream s)
    throws IOException
{
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();

    // Write out number of buckets
    if (table==EMPTY_TABLE) {
        s.writeInt(roundUpToPowerOf2(threshold));
    } else {
       s.writeInt(table.length);
    }

    // Write out size (number of Mappings)
    s.writeInt(size);

    // Write out keys and values (alternating)
    if (size > 0) {
        for(Map.Entry<K,V> e : entrySet0()) {
            s.writeObject(e.getKey());
            s.writeObject(e.getValue());
        }
    }
}

private static final long serialVersionUID = 362498820763181265L;

private void readObject(java.io.ObjectInputStream s)
     throws IOException, ClassNotFoundException
{
    // Read in the threshold (ignored), loadfactor, and any hidden stuff
    s.defaultReadObject();
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new InvalidObjectException("Illegal load factor: " +
                                           loadFactor);
    }

    // set other fields that need values
    table = (Entry<K,V>[]) EMPTY_TABLE;

    // Read in number of buckets
    s.readInt(); // ignored.

    // Read number of mappings
    int mappings = s.readInt();
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " +
                                           mappings);

    // capacity chosen by number of mappings and desired load (if >= 0.25)
    int capacity = (int) Math.min(
                mappings * Math.min(1 / loadFactor, 4.0f),
                // we have limits...
                HashMap.MAXIMUM_CAPACITY);

    // allocate the bucket array;
    if (mappings > 0) {
        inflateTable(capacity);
    } else {
        threshold = capacity;
    }

    init();  // Give subclass a chance to do its thing.

    // Read the keys and values, and put the mappings in the HashMap
    for (int i = 0; i < mappings; i++) {
        K key = (K) s.readObject();
        V value = (V) s.readObject();
        putForCreate(key, value);
    }
}
private void putForCreate(K key, V value) {
    int hash = null == key ? 0 : hash(key);
    int i = indexFor(hash, table.length);

    /**
     * Look for preexisting entry for key.  This will never happen for
     * clone or deserialize.  It will only happen for construction if the
     * input Map is a sorted map whose ordering is inconsistent w/ equals.
     */
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            e.value = value;
            return;
        }
    }

    createEntry(hash, key, value, i);
}

简单来说，在序列化时，针对Entry的key与value分别单独序列化，当反序列化时，再单独处理即可。

http://examples.javacodegeeks.com/core-java/util/hashmap/hashmap-changes-in-java-8/

The way java.util.HashMap entries are indexed and stored has changed in the Java 8 update. Hash elements use balanced trees instead of linked lists under certain circumstances now. 

The main idea is that when the number of items in a hash is larger than a certain value, the hash will change from using a linked list of elements or entries to a balanced tree, this will improve the worst case performance from O(n) to O(log n).

http://www.nagarro.com/at/de/blog/post/24/Performance-Improvement-for-HashMap-in-Java-8
http://www.importnew.com/14417.html

How linked list is replaced with binary tree?

In Java 8, HashMap replaces linked list with a binary tree when the number of elements in a bucket reaches certain threshold. While converting the list to binary tree, hashcode is used as a branching variable. If there are two different hashcodes in the same bucket, one is considered bigger and goes to the right of the tree and other one to the left. But when both the hashcodes are equal, HashMap assumes that the keys are comparable, and compares the key to determine the direction so that some order can be maintained. It is a good practice to make the keys of HashMap comparable.

This JDK 8 change applies only to HashMap, LinkedHashMap and ConcurrentHashMap.

- See more at: http://www.nagarro.com/at/de/blog/post/24/Performance-Improvement-for-HashMap-in-Java-8#sthash.bynyrm4r.dpuf
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/HashMap.java
如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
final float loadFactor;
int threshold;
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
static final int MIN_TREEIFY_CAPACITY = 64;

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

* @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

http://blog.jooq.org/2014/02/14/java-8-friday-goodies-map-enhancements/

http://www.javaspecialists.eu/archive/Issue212.html

    Set<String> names = Collections.newSetFromMap(
        new ConcurrentHashMap<String, Boolean>()
    );

Don't use hashmap in mutliple thread - as it may cause forever loop.
疫苗：Java HashMap的死循环
不正当使用HashMap导致cpu 100%的问题追究
上面只是一种情况,造成单线程死循环,双核 cpu 的话占用率是 50%,还有导致 100%的情况,应该也都是链表的闭环所致。

最终,这并不是 HashMap 的问题,是使用场景的不当,在并发情况下选择非线程 安全的容器是没有保障的。

危险！在HashMap中将可变对象用作Key

http://www.java-fries.com/2014/09/mutable-keys-in-hashmap-dangerous-practice/

在HashMap中使用不可变对象。在HashMap中，使用String、Integer等不可变类型用作Key是非常明智的。

我们也能定义属于自己的不可变类。

如果可变对象在HashMap中被用作键，那就要小心在改变对象状态的时候，不要改变它的哈希值了。
http://howtodoinjava.com/2013/06/14/popular-hashmap-and-concurrenthashmap-interview-questions/
1) How to design a good key for HashMap

Key’s hash code is used primarily in conjunction to its equals() method, for putting a key in map and then searching it back from map. So if hash code of key object changes after we have put a key-value pair in map, then its almost impossible to fetch the value object back from map. It is a case of memory leak. To avoid this, map keys should be immutable. These are few things to create an immutable of class.

This is the main reason why immutable classes like String, Integer or other wrapper classes are a good key object candidate.

But remember that immutability is recommended and not mandatory. If you want to make a mutable object as key in hashmap, then you have to make sure that state change for key object does not change the hash code of object. This can be done by overriding the hashCode() method. Also, key class must honor the hashCode() and equals() methods contract to avoid the undesired and surprising behavior on run time. Read more about this contract in linked post.

5) Difference between HashMap and HashTable
The major difference is that HashTable is synchronized and HashMap is not.
HashTable is legacy class (part of JDK 1.0) which was promoted into collections framework by implementing Map interface later. It still has some extra features like Enumerator with it, which HashMap lacks.

Another minor reason can be: HashMap supports null key (mapped to zero bucket), HashTable does not support null keys and throws NullPointerException on such attempt.

7) Impact of random/fixed hashcode() value for key

The impact of both cases (fixed hashcode or random hashcode for keys) will have same result and that is “unexpected behavior“. The very basic need of hashcode in HashMap is to identify the bucket location where to put the key-value pair, and from where it has to be retrieved.

If the hashcode of key object changes every time, the exact location of key-value pair will be calculated different, every time. This way, one object stored in HashMap will be lost forever and there will be very minimum possibility to get it back from map.

For this same reason, key are suggested to be immutable, so that they return a unique and same hashcode each time requested on same key object.



3) Difference between HashMap and Collections.synchronizedMap(HashMap)

HashMap is non-synchronized and Collections.synchronizedMap() returns a wrapped instance of HashMap which has all get, put methods synchronized.

Essentially, Collections.synchronizedMap() returns the reference of internally created inner-class “SynchronizedMap”, which contains key-value pairs of input HashMap, passed as argument.

This instance of inner class has nothing to do with original parameter HashMap instance and is completely independent.

     * Returns a synchronized (thread-safe) map backed by the specified

     * map.  In order to guarantee serial access, it is critical that

     * <strong>all</strong> access to the backing map is accomplished

     * through the returned map.<p>

     *

     * It is imperative that the user manually synchronize on the returned

     * map when iterating over any of its collection views:

     * <pre>

     *  Map m = Collections.synchronizedMap(new HashMap());

     *      ...

     *  Set s = m.keySet();  // Needn't be in synchronized block

     *      ...

     *  synchronized (m) {  // Synchronizing on m, not s!

     *      Iterator i = s.iterator(); // Must be in synchronized block

     *      while (i.hasNext())

     *          foo(i.next());

     *  }

    public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
        return new SynchronizedMap<>(m);
    }

    /**
     * @serial include
     */
    private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize

        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNonNull(m);
            mutex = this;
        }

        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }
        // all methods are synchronized
        private transient Set<K> keySet;
        private transient Set<Map.Entry<K,V>> entrySet;
        private transient Collection<V> values;

        public Set<K> keySet() {
            synchronized (mutex) {
                if (keySet==null)
                    keySet = new SynchronizedSet<>(m.keySet(), mutex);
                return keySet;
            }
        }

        public Set<Map.Entry<K,V>> entrySet() {
            synchronized (mutex) {
                if (entrySet==null)
                    entrySet = new SynchronizedSet<>(m.entrySet(), mutex);
                return entrySet;
            }
        }

        public Collection<V> values() {
            synchronized (mutex) {
                if (values==null)
                    values = new SynchronizedCollection<>(m.values(), mutex);
                return values;
            }
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            synchronized (mutex) {return m.equals(o);}
        }
        public int hashCode() {
            synchronized (mutex) {return m.hashCode();}
        }
        public String toString() {
            synchronized (mutex) {return m.toString();}
        }

        private void writeObject(ObjectOutputStream s) throws IOException {
            synchronized (mutex) {s.defaultWriteObject();}
        }
    }

Implement hashmap
https://gist.github.com/gcrfelix/e850d605591f449e2363
The implementation is flaw.

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

        final int hash;

        final K key;

        V value;

        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {

            this.hash = hash;

            this.key = key;

            this.value = value;

            this.next = next;

        }

        public final int hashCode() {

            return Objects.hashCode(key) ^ Objects.hashCode(value);

        }

        public final V setValue(V newValue) {

            V oldValue = value;

            value = newValue;

            return oldValue;

        }

        public final boolean equals(Object o) {

            if (o == this)

                return true;

            if (o instanceof Map.Entry) {

                Map.Entry<?,?> e = (Map.Entry<?,?>)o;

                if (Objects.equals(key, e.getKey()) &&

                    Objects.equals(value, e.getValue()))

                    return true;

            }

            return false;

        }

    }