Hash散列基本思想

哈希表使用数组和链表共同实现散列存储，每一个数组元素可以认为是散列表中的桶位（buket），每个桶位存放一个链表，该链表由散列码（hashCode）相同的节点构成。Hash表的查找就是根据需要查找的对象（key, value）中的key，利用散列函数计算key对应的hashCode，即数组的下标（buket的索引），在O(1)时间内找到对应的桶位，再遍历该桶位内的链表，查找对应的value值即可。

在JDK8中，当桶位数目过多（默认至少64）或者某一个桶位的链表长度过长时（默认是8），查找效率会显著降低。因此HashMap会将链表的普通节点转化为树节点（TreeNode）存储，链表List也将转为Tree树将搜索效率提升到O(logn)，但是TreeNode的空间消耗是普通Node空间消耗的两倍，在HashMap进行多次remove操作之后，如果桶位数目和链表长度低于阈值，TreeNode重新转化为Node，Tree树转为List链表。

Hash表长度为 ${2^n}$ 与查找效率

Hash表中的table数组存放node，table的长度size必须为2的幂，在这个前提下有如下规律：对任意一个哈希码hashCode利用求余运算进行散列，即index=hashCode%size时，index为hashCode所在的数组桶位下标，由于求余取模运算效率低下，在size为2的幂的前提下，可以用位与运算代替，即index=hashCode & (size – 1)，得到的是相同的结果。（参见博文）

下面是保证输入一个表的初始长度，是table的size总是2的幂:

/**     * Returns a power of two size for the given target capacity.     */    static final int tableSizeFor(int cap) {        int n = cap - 1;        n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;    }

重点函数实现

初始容量和负载因子

在HashMap中有两个很重要的参数，容量(Capacity)和负载因子(Load factor)：

Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.

Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

简单的说，Capacity就是bucket的大小，Load factor就是bucket填满程度的最大比例。如果对迭代性能要求很高的话不要把capacity设置过大，也不要把load factor设置过小。当bucket中的entries的数目大于capacity*load factor时就需要调整bucket的大小为当前的2倍。

put函数的实现

对key的hashCode()做hash，然后再计算index;

如果没碰撞直接放到bucket里；

如果碰撞了，以链表的形式存在buckets后；

如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；

如果节点已经存在就替换old value(保证key的唯一性；

如果bucket满了(超过load factor*current capacity)，就要resize。

public V put(K key, V value) {    // 对key的hashCode()做hash    return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node
   
    [] tab; Node
    
      p; int n, i;    // tab为空则创建    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // 计算index，并对null做处理    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    else {        Node
     
       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
      
       )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;    // 超过load factor*current capacity，resize    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}

get函数实现

bucket里的第一个节点，直接命中；

如果有冲突，则通过key.equals(k)去查找对应的entry
- 若为树，则在树中通过key.equals(k)查找，O(logn)；
- 若为链表，则在链表中通过key.equals(k)查找，O(n)。

public V get(Object key) {    Node
   
     e;    return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node
    
      getNode(int hash, Object key) {    Node
     
      [] tab; Node
      
        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) {            // 在树中get            if (first instanceof TreeNode)                return ((TreeNode
       
        )first).getTreeNode(hash, key);            // 在链表中get            do {                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;            } while ((e = e.next) != null);        }    }    return null;}

hash()、resize()

强烈推荐阅读，里面有详细的介绍。