源码分析HashMap的几个问题（JDK1.7）

• 如何存储数据 （put、get）

1. put数据

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        //计算key的hash值
        int hash = hash(key);
        //根据hash和数组的长度计算索引，即数组存放的位置
        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++;
        //将算出的key的hash值，key，value ，以及索引存放在entry对象中，并加入table数组中
        addEntry(hash, key, value, i);
        return null;
    }

1. get数据

public V get(Object key) {
    //如果key为null，则返回null对于的value
    if (key == null)
        return getForNullKey();
    //根据key获取entry
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    //计算出key的hash值
    int hash = (key == null) ? 0 : hash(key);
    //根据hash值获取索引，遍历索引下的所有的entry值
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        //如果hash值相同并且key也相同则返回value
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

• 默认容量为什么是16

//1前移4位 二进制1是 01 ，前移4位 则是 10000，即16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

我们先看一下源码如何获取index的值

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        //hash 值与 数组的长度-1进行位运算，长度必须是2的幂。
        return h & (length-1);
    }

index的值是通过key的hash值与数组长度-1进行位运算来的。举个例子，

1. 计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001；

2. HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111

3. 把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9
   可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。

==长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。==

• 负载因子为什么是0.75f

 /**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

加载因子需要在时间和空间成本上寻求一种折衷。

1. 加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本

2. 加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。

• hash冲突的产生与解决

1. 产生

例如我们现在要加入一个key=A，value=a，先需要计算A的index，假如是2。那么结果如下：

1. 解决hash冲突

这个时候我们需要使用链表来解决hash冲突，当产生相同的index是，则通过Next指向同一个index的下一个节点，如图：
(

• 什么时候会出现死锁

当扩容时，需要将老的table的数据转移到新的table上，调用transfer发放进行转移。
我们先看下transfer方法

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //循环遍历老的table
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            //判断是否需要重新计算hash值
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

正常情况下，转移前链表顺序是1->2->3，逆序转移后新的t顺序变成 3->2->1，但是在多线程环境中，使用HashMap进行put操作时会引起死循环，导致死循环的原因是在多线程的情况下，会形成环形链表，这时是没有问题的，我们再看看get()方法中的获取Entry的方法

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(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;
}

加入我们执行get方法找一个不存在的值的时候，for循环将会死循环，即会形成死锁。

参考博客：https://coolshell.cn/articles/9606.html