# Java集合之HashMap

## 一、简介

HashMap采用hash表的数据结构，本质上就是数组+单向链表（或者是红黑树）。

静态变量：

```java
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //hash表的初始容量
static final int MAXIMUM_CAPACITY = 1 << 30; //hash表的最大容量，2的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;
```

成员变量：

```java
transient Node<K,V>[] table; //hash表
transient Set<Map.Entry<K,V>> entrySet; //KV数据
transient int size; //元素个数
transient int modCount; //修改次数
int threshold; //负载容量
final float loadFactor; //负载系数
```

单向链表节点结构：

```java
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    ......
    ......
}
```

红黑树节点结构：

```java
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
     ......
     ......
}
```

## 二、初始化

```java
//构建一个空的HashMap，默认容量16（第一次put时初始化容量），默认负载系数0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}
```

## 三、增加

```java
//将指定的key和value写入map，如果key已经存在，那么新的value会覆盖旧的value
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//根据key算出hash值：高16位不动，低16位和高16位异或
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//实现put以及相关的方法
//onlyIfAbsent 如果为true，则不改变原来的值
//evict 如果是false，那么该表处于创建模式
//return 之前的值，如果之前没有值，则返回null
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)
        //初始化hash表
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//(n-1)&hash决定元素在hash表位置,n=2^x情况等价于模运算
        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; //key相同，则默认覆盖
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //key不相同并且是tree数据结构，则处理树
        else {
            //key不相同并且是链表结构则放在链表的尾部
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) //链表长度大于阈值则转成tree结构
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break; //key相同，则默认覆盖
                p = e;
            }
        }
        if (e != null) { // map中已经存在key，则默认覆盖，返回旧value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; //修改次数+1
    if (++size > threshold)
        resize(); //超过负载系数，需要扩容
    afterNodeInsertion(evict);
    return null;
}
```

## 四、删除

```java
//return 返回key对应的value，如果没有则返回null
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

//实现remove及相关的方法
//value 如果key对应的值是value则移除，否则忽略
//matchValue 和value一起使用，为true时，value生效
//movable 如果是false，在删除时不移动其他节点（红黑树结构使用）
//return 移除的value
final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;//如果hash和key都相同则移除
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);//在红黑树中查找节点
                else {
                    //在单向链表中查找节点
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//如果是红黑树,则调用红黑树的移除逻辑
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
```

## 五、查找

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

//实现get及相关的方法
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 && //检查第一个节点
            ((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;
}
```

## 六、修改

复用增加方法`put`

## 七、快速失败机制

**fail—fast**快速失败机制是是java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

**原理**

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。

集合在被遍历期间如果内容发生变化，就会改变modCount的值。

每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。

**解决方案**

在单线程遍历中如果使用remove或者add就会导致这个问题，那么在单线程中如何解决呢，有两种方式：

1. 使用for循环
2. 使用`iterator.remove();`

## 八、安全失败机制

java.util里面的集合是快速失败机制，而java.util.concurrent里面则是安全失败机制（fail-safe）。采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，故不会抛 ConcurrentModificationException 异常。

缺点就是：

1. 需要复制集合，产生大量的无效对象，开销大；
2. 无法保证读取的数据是目前原始数据结构中的数据。

## 九、线程不安全导致的问题

1. 数据不一致；
2. 扩容rehash的时候可能会形成循环链表，后续遍历的时候产生死锁；（[https://www.jianshu.com/p/4930801e23c8）](https://www.jianshu.com/p/4930801e23c8%EF%BC%89)
3. 多线程put操作可能导致数据丢失，比如两个线程两个不同的key产生了hash冲突，在插入的时候都发现没有值，就都去put，那么后面put的会把前面put的值覆盖掉；

> 参考：
>
> <https://liuyanzhao.com/9034.html>

## 重点问题

### 1 如何扩容

```java
//初始化表或将表的容量扩大2倍
//return 初始化或扩容后的hash表
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; //新容量和新负载容量都乘以2
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else { //初始化表容量和负载容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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];//新建扩容后的hash表
    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 { // 链表重新计算位置，同一链表中高位为0的组成新新链表在新数组位置不变，高位为1的组成新链表在新数组位置为：原位置+旧容量。相当于重新计算了一下hash在新表中的位置
                    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) { //高位为0
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else { //高位为1
                            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;
}
```