在实际的开发中，hashmap是比较常用的数据结构，如果所开发的系统并发量不高，那么没有问题，但是一旦系统的并发量增加一倍，那么就可能出现不可控的系统问题，所以在平时的开发中，我们除了需要考虑正常的情况，还需要考虑异常情况，高并发的场景，这样写的代码才具备稳定性。否则就是随时就是定时炸弹。只是目前没有触发而已。

hashmap为什么不安全

造成线程不安全的原因在于竞态读写共享资源，对于hashmap来说其实就是table数组以及数组中链表。
get：读操作 put：写操作，以及扩容和树化等。

1.读操作与读操作、写操作、扩容、树化之间是否线程安全
读和读之间显然不会有线程安全问题，读是从table中获取对应下标遍历链表，而写直接写在最后，也不存在。

读和扩容之间存在线程安全问题，扩容的基本流程是会创建一个新的table数组，然后将当前table引用指向新的数组，然后在将旧的table数组遍历迁移到新的数组中。所以在这个过程中，可能导致读操作获取不到原来旧数组中的某些值，从而导致出现数据丢失。

读操作与树化不存在线程安全问题，原因在于 链表的节点和树化的节点是不同的，需要创建新的树节点，而之前是不需要修改链表节点。在树化完全执行完毕之后，才会更新对应的引用。是一个写时复制操作。

2.写操作与写操作，扩容、树化之间是否线程安全
写与写操作是存在线程安全的，因为同时对链表进行尾部插入，如果同时有两个线程操作，那么就会出现丢失数据的情况。
同样写与扩容来说，一边写和扩容，并行操作。写与树化操作，因为是对链表操作，而在树化结束之后，没来得记更新，所以就会出现写操作无效。
3.扩容与扩容、树化操作之间是否安全
扩容与扩容 在同时操作不同的数据肯定会丢失数据。
4.树化与树化之间是否线程安全

ConcurrentHashMap

如上所示，hashmap是线程不安全的，所以在实际的开发中，我们会更多的使用concurrentHashMap。hashtable和Synchroinzed的原理其实是通过对全局的操作进行加一把锁，整体的并发粒度比较粗。

    public synchronized int size() {
        return count;
    }

而ConcurrentHashMap采用了分段锁的思想，按照table的粒度进行划分，如果是8个那么默认就是8个锁，这样对于数据的操作可以提升并发性能。

get实现原理

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // key 所在的 hash 位置
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果指定位置元素存在，头结点hash值相同
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                // key hash 值相等，key值相同，直接返回元素 value
                return e.val;
        }
        else if (eh < 0)
            // 头结点hash值小于0，说明正在扩容或者是红黑树，find查找
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            // 是链表，遍历查找
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

总结下其实就是如下几种步骤，
1.根据hash值计算位置，
2.找到指定位置，如果是头节点直接返回。
3.如果头节点hash值小于0，说明正在扩容或者是红黑树，查找
4.如果是链表，直接遍历链表。

put实现原理

public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key 和 value 不能为空
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        // f = 目标位置元素
        Node<K,V> f; int n, i, fh;// fh 后面存放目标位置的元素 hash 值
        if (tab == null || (n = tab.length) == 0)
            // 数组桶为空，初始化数组桶（自旋+CAS)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 桶内为空，CAS 放入，不加锁，成功了就直接 break 跳出
            if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
                break;  // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 使用 synchronized 加锁加入节点
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 说明是链表
                    if (fh >= 0) {
                        binCount = 1;
                        // 循环加入新的或者覆盖节点
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 红黑树
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

写操作的过程 其实是分两种情况，如果table[i] 为空，则使用cas方式将数据写入对应的节点，如果table[i]不为空 ，通过syn的方式枷锁实现。

树化操作，写入和扩容的同时会丢失数据，所以需要使用syn枷锁

扩容
ConcurrentHashMap使用的是分段锁，也就是一个table[i] 一个锁，那么在实际扩容的时候是怎么样的。
实际上也是通过扩容操作也是分段加锁执行的。整体就是写时复制、复制替代搬移

1.操作的时候，会对每个数组进行枷锁处理，复制、然后解锁，并且是多个线程同时处理。比如A线程复制1-3，B线程复制4-6。所以整体的流程就是已经完成复制的（已复制未加锁）、在复制中加锁、未复制未加锁。
2.因此在复制的过程中，对于已经复制的链表应该使用新的table数组，而在复制和没有复制的应该使用旧的table数组。
ForwardingNode 节点就是标记是否已复制未加锁，所以在已经复制的节点，会使用 ForwardingNode的nextTable指向新的数组。

static final class ForwardingNode<K, V> extends Node<K, V> {
        final Node<K, V>[] nextTable;

        ForwardingNode(Node<K, V>[] tab) {
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }
    }

3.在实际的扩容中，多个线程可以同时进行对数组进行扩容，通过tranferIndex，初始值为tab.length，通过CAS进行竞争获取。

4.最终谁来执行将table引用指向新数组，通过sizeCtl来判断，谁执行到最后 等于0 的时候，就负责处理。

小结

本篇主要介绍了 hashmap不安全的原因，在扩容、树化、put操作之间。以及介绍了ConcurrentHashMap 在8中的版本get、put的核心流程。主要介绍了扩容的机制/