HashMap 一点记录（JDK 1.7）

JDK 1.8对HashMap改进很多，1.8中已经移除了 Entry 的这种实现方式了，改用了Node，所以存储结构也发生了很大的变化，代码也从1k行膨胀到了2k行，这次梳理的是1.7的 HashMap 实现。1.8 下次再详细看看。

HashMap继承AbstractMap，实现了Map接口。

属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化容量值，16，要求2的N次幂（计算table index要求），可以在构造方法指定，如果在构造函数指定50，那么 Map 会自动选择扩容到50以后的2次幂，即：64

static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量

static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认负载因子，可以在构造方法指定实际值

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;// 所有 HashMap 实例初始化时，共享该值，表示空集合

transient int size;// Map 中k-v个数

int threshold;// 临界值，size >= 该值的时候，进行 resize

final float loadFactor;// 负载因子，用于计算threshold，threshold = (int)Math.min(capacity* loadFactor, MAXIMUM_CAPACITY + 1);

transient int modCount;// 记录 Map 结构被修改的次数，这里的修改可能是 Map 的 size 改变，比如put，remove，clear 等；rehash；当 clone 的时候，返回的克隆 Map 对象的 modCout 被为0

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;//默认替换散列阈值

private static class Holder.ALTERNATIVE_HASHING_THRESHOLD // 替换散列阈值，该值在VM启动以后初始化，如果系统属性（system property）数定义了jdk.map.althashing.threshold >= 0时，则使用定义的值作为该值；否则使用Integer.MAX_VALUE。当调用 resize 或者inflateTable的时候，如果满足条件 capacity >= 该值，会进行 rehash，rehash的目的是为了避免hash值的碰撞。

transient int hashSeed = 0;// hashSeed 用于计算 key 的 hash 值，它与 key 的 hashCode 进行按位异或运算。这个 hashSeed 是一个与实例相关的随机值，主要用于解决 hash 冲突。上面说到 rehash 其实就是事先改变 hashSeed 的值，以至于计算 key 的新 hash 值与原 hash 值不同

构造方法

public HashMap(int initialCapacity, float loadFactor)

public HashMap(int initialCapacity)

public HashMap()

public HashMap(Map<? extends K, ? extends V> m)

常用方法

public V put(K key, V value)

public V get(Object key)

public V remove(Object key)

public boolean containsKey(Object key)

内部存储结构（JDK 1.7）

（图片来源：http://javaconceptoftheday.com/how-hashmap-works-internally-in-java/）

Entry结构

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

V value;

Entry&lt;K,V&gt; next;

int hash;

}

Entry自身持有另外一个Entry对象next，构成了链表的数据结构。

put方法

算哈希值 --> 算 table index --> 存。

1、检查 table ，如果 == EMPTY_TABLE，先按照指定的容量扩容 table ，即：table = new Entry[capacity]，如果capacity的值不是2的N次幂，则capacity值会被修改为比capacity大的最近一个2的N次幂数。

2、检查 key == null ，如果是，则认为 key 的 hashValue 对应的 table index 为 0，否则需要计算 key 的 hashValue ，计算方法：

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

}</pre>

然后，计算 hashValue 对应的 table index ，方法：index = hashValue & (table.length-1);
这个运算相当于 hashValue 对 table.length 的取模运算。因为 table.length 是优化过的，是2的N次幂，所以可以这样计算。（数学原理参考另外篇文章：http://blog.fenxiangz.com/articles/2016/08/22/1471922812071.html，ThreadLocalMap部分）
最后，就算出了这个key-value 对于的 table[index] 了。
3、put，如果table[index] == null , 则直接 new Entry，存就好了；
否则，先计算table[index] 链表上的所有Entry e，确认是否有 e.hash == hashValue && e.key.equals(key) 的 e，
如果有，则用新的value替换旧的e.value 并返回旧的e.value；
否则，e1 = new Entry， table[index] = e1 ，并把原有的table[index]作为e1.next。
存的过程，如果(size >= threshold) && (null != table[index])，会导致 resize 扩容，并且如果满足条件 capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD的时候会进行 rehash，rehash的目的是为了避免hash值的碰撞。
rehash的成本是很高的，所以，如果使用HashMap的时候，指定了capacity ，capacity 应该尽可能的大于业务预期的大小。防止过程中rehash。