HashMap详解 · 造舟野渡

本文尝试梳理一遍HashMap，基于Java8。先看一个使用示例：

public static void main(String[] args) {
        // init 
        Map<Integer, Integer> map = new HashMap<>();
        // put
        IntStream.range(0, 20).forEach(item->map.put(item,item+1));
        // iterator
        map.forEach((k,v)-> System.out.println("k:"+k+" v:"+v));
        // get
        System.out.println(map.get(1);
}

继承AbstractMap，实现 Cloneable, Serializable。重要filed：

initialCapacity:初始容量，是哈希表创建中桶的数量。默认16(1«4)
loadFactor:加载因子(默认0.75)，指容量自动增加之前可以达到多满的一个系数。

所以，使用时，如果明确知道map的容量，可以定一个初始值，避免自动扩容的消耗。

常量：

/**
 * 默认的初始容量（容量为HashMap中槽的数目）是16
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 最大容量 : 必须是2的幂且小于2的30次方，传入容量过大将被这个值替换
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 *  默认加载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 链表转为红黑树的临界值
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 删除冲突节点后，hash相同的节点数目小于这个数，红黑树就恢复成链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 可能被树化的最小容量
 */
static final int MIN_TREEIFY_CAPACITY = 64;

初始化

如果使用模式默认构造方法，loadFactor=0.75f：

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

指定容量初始化:

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

threshold: (capacity * load factor) , 扩容时容量大小。但此处使用了方法tableSizeFor。

//  返回容量对应的2的幂:比如cap=31，return 32，cap=33，return 64
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;
}

1. PUT

Put主要包含以下步骤：

对key的hashcode做hash处理，再获取index
如果没有hash碰撞，直接put
如果碰撞，以链表形式存储
如果链表过长，装换为红黑树
如果已经存在，替换value
如果达到扩展临界值，则扩容

数据结构示意图:

从图中看出，HashMap有数组、链表、红黑树等数据结构。使用数组是为方便hash后定位到具体节点(也作bucket)，时间复杂度O(1)，如果bucket位置相同，使用链表方便插入，但是链表过长，查找时间复杂度增加O(n)。使用红黑树，查找时间复杂度O(logn)。

Node和TreeNode结构如下：

源码

/**
 * 1.  存放key-value，如果key已经存在，则替换掉
 * 2.  如果已经有key，返回对应value，否则返回null
 * 3. 对 key 作hash并传递给putVal方法
 */
 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
 }

static final int hash(Object key) {
    int h;
    // key 为null 返回 0
    // key 非null：获取hashcode 和hashcode无符号右移16位安位与，即大于2的16次方后，重新调整hashcode。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

例如”string“对应的hash值如下：

h :     1100 1010 1101 0101  0110 0000 0001 0001
h>>>16: 0000 0000 0000 0000  1100 1010 1101 0101
^       1100 1010 1101 0101  1010 1010 1100 0100

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
  
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        
         // tab为空则通过resize创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
         // 计算index = (n - 1) & hash，如果此下标Node空，新建一个Node
        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))))
                // hash相同，key相同：节点存在
                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;
        // size 叨叨临界值，扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上述内部类Node很重要，用来存储数据。如果put发现tab下标(index)对应的值为空，直接new 一个Node存放。

tab[i] = newNode(hash, key, value, null);// 第一个node
p.next = newNode(hash, key, value, null);// 链表添加node

2. 扩容

扩容resize，当bucket数量超过threshold,需要对数组table扩容，否则hash碰撞太厉害，影响性能。也就是put源码中的：

if (++size > threshold){
    resize();
}

每次扩容，新容量(newCap)都是原来的2倍，重新分配每个桶上的数据，下面重点看如何分配：从一个示例开始：

public class App {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        for (int i = 0; i < 16; i++) {
            map.put("key" + i, "value" + i);
        }
    }
}

case1: 没有碰撞，不用扩容循环插入16个数据从key0->key15。初始化map后：

cap = 16 
threshold = 16 * 0.75 = 12

对于put("key0","value0")，key0的hash值为十进制为3288451，则：hash & （cap-1）

hash 0011 0010 0010 1101 1000 0011
‭n-1  0000 0000 0000 0000 0000 1111
rst  0000 0000 0000 0000 0000 0011

结果是: 3 表示key0位置在数据是table[3] = node(3288451,“key0”,“value0”,null)；

case2: 碰撞，转为链表对于put("key12","value12") key12的hash值为十进制为101945043, 则：hash & （cap-1）

0110 0001 0011 1000 1110 1101 0011
0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0011

结果是3，和key0位置相同，赋值为key0.next

 p.next = newNode(hash, key, value, null);

如下图：此时，size = 13 > 12。到达扩容界限，进行扩容：

cap = 32
threshold = oldThr <<1  = 24

重新分配数据，还是以key0和key12为例: hash & (‭cap«1)-1

key0

hash        0011 0010 0010 1101 1000 0011
(‭n<<1)-1    0000 0000 0000 0000 0001 1111
rst         0000 0000 0000 0000 0000 0011

结果还是3，还是原来桶的位置；

key12

0110 0001 0011 1000 1110 1101 0011
0000 0000 0000 0000 0000 0001 1111
0000 0000 0000 0000 0000 0001 0011

结果是16 + 3 = 19, 位置改变，重新分配。

从key12 的例子可以看到。 hash & (cap-1)：其中hash值不变，不需要重新计算， cap左移一位(扩容一次)

如果hash对应位置上是0，则hash & (cap-1)结果不变
如果hash对应位置上是1，结果是（hash & (cap-1) + cap = hash & (cap « 2 -1)，即原值+cap

这样，数据迁移的成本不是很高。

下面是resize源码：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
         // 超过最大值就不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 扩展为原来两倍(double threshold)
    }else if (oldThr > 0) {// initial capacity was placed in threshold
        newCap = oldThr;
    }else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 对树的处理
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 对链表的处理
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

知道put和resize方法，get方法就比较简单了。这儿不作分析。

总结：

Hashmap由3种数据结构组成，分别是数组、链表、红黑树。数组存储相「桶」，桶里面是链表或红黑树，桶的定位通过hashcode和(hashcode»>16)异或计算结果。
hash碰撞问题：如果，少量数据通过链表，数据多通过红黑树。但如果碰撞过于严重，其实效率就退化为红黑树的效率，O(1)->O(logN)。通过动态扩容解决。
动态扩容：数据达到某个阈值进行扩容，但扩容需要对所有数据重新hash，可能会导致扩容时出现严重性能问题；hashMap都是原来两倍，保证数据迁移要么在原位，要么+oldCap，减少重新计算桶和数据迁移复杂性。

Menu

初始化

1. PUT

2. 扩容