面试之CurrentHashMap的底层原理

首先回答HashMap的底层原理?

HashMap是数组+链表组成。数字组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。要将key 存储到（put）HashMap中，key类型实现必须计算hashcode方法，默认这个方法是对象的地址。接着还必须要覆盖对应的equals方法。如果对于插入的操作的来说，那么对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部。对于查找的来说话，就需要遍历链表，然后key的equals方法去逐一对比查找。但是对应的key可以为空。所以，HashMap对应的链表越少，性能才越好。

如何解决冲突?

1：链式寻址法，这是一种常见的方法，简单理解就是把存在Hash冲突的key，以单向链表来进行存储。

2：开放定址法也称线性探测法，就是从发生冲突的那个位置开始，按照一定次序从Hash表找到一个空闲位置然后把发生冲突的元素存入到这个位置，而在java中，ThreadLocal就用到了线性探测法来解决Hash冲突

3、再Hash法，就是通过某个Hash函数计算的key，存在冲突的时候，再用另外一个Hash函数对这个可以进行Hash，一直运算，直到不再产生冲突为止，这种方式会增加计算的一个时间,性能上呢会有一些影响

HashMap在JDK1.8版本中是通过链式寻址法以及红黑树来解决Hash冲突的问题，其中红黑树是为了优化Hash表的链表过长导致时间复杂度增加的问题，当链表长度大于等于8并且Hash表的容量大于64的时候，再向链表添加元素，就会触发链表向红黑树的一个转化。（红黑树是一种自平衡的二叉搜索树）

hashCode方法的作用：它返回的就是根据对象的内存地址换算出的一个值。这样一来，当
集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理
位置上。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如
果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相
同就散列其它的地址。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

HashTable的底层原理?

hashtable是通过数组与链表来储存数据，但是它与hashmap不同的是它的key不能为空同时其为线程安全的。虽然hashmap是线程安全的不过其保证线程安全的手段低效，它只是简单的对每个方法加上synchronized（悲观锁）相当于就是对底层的数组加上一把大锁。这种方式出现锁冲突的概率非常大，因为不管是读还是写都需要去竞争同一把锁所以其效率低下。

再次回答CurrentHashMap的底层原理？

ConcurrentHashMap与HashMap等的区别？

其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。

1.数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
2.保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
3.锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
5.查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

CurrentHashMap是如何保证线程安全。

这里的链表长度如果大于8 会自动转换为红黑树。这里的数据结构和jdk1.8的HashMap数据结构大致相同。只是在HashMap的基础上增加线程安全的操作。

final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException(); // 键或值为空，抛出异常
        // 键的hash值经过计算获得hash值，这里的 hash 计算多了一步 & HASH_BITS，HASH_BITS 是 0x7fffffff，该步是为了消除最高位上的负符号 hash的负在ConcurrentHashMap中有特殊意义表示在扩容或者是树结点
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;) { // 无限循环
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0) // 表为空或者表的长度为0
                // 初始化表
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 表不为空并且表的长度大于0，并且该桶不为空
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null))) // 比较并且交换值，如tab的第i项为空则用新生成的node替换
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED) // 该结点的hash值为MOVED
                // 进行结点的转移（在扩容的过程中）
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) { // 加锁同步
                    if (tabAt(tab, i) == f) { // 找到table表下标为i的结点
                        if (fh >= 0) { // 该table表中该结点的hash值大于0
                            // binCount赋值为1
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) { // 无限循环
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) { // 结点的hash值相等并且key也相等
                                    // 保存该结点的val值
                                    oldVal = e.val;
                                    if (!onlyIfAbsent) // 进行判断
                                        // 将指定的value保存至结点，即进行了结点值的更新
                                        e.val = value;
                                    break;
                                }
                                // 保存当前结点
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) { // 当前结点的下一个结点为空，即为最后一个结点
                                    // 新生一个结点并且赋值给next域
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    // 退出循环
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) { // 结点为红黑树结点类型
                            Node<K,V> p;
                            // binCount赋值为2
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) { // 将hash、key、value放入红黑树
                                // 保存结点的val
                                oldVal = p.val;
                                if (!onlyIfAbsent) // 判断
                                    // 赋值结点value值
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) { // binCount不为0
                    if (binCount >= TREEIFY_THRESHOLD) // 如果binCount大于等于转化为红黑树的阈值
                        // 进行转化
                        treeifyBin(tab, i);
                    if (oldVal != null) // 旧值不为空
                        // 返回旧值
                        return oldVal;
                    break;
                }
            }
        }
        // 增加binCount的数量
        addCount(1L, binCount);
        return null;
}

JDK1.8的CurrentHashMap与 JDK1.7的CurrentHashMap的对比：

1：抛弃了JDK1.7中的原有的Segment中分段锁。而是采用了CAS+synchronized来保证并发性。

2：将 JDK 1.7 中存放数据的 HashEntry 改为 Node，但作用是相同的。

我们看下对应的put方法思想: （主要是6步法：思想:通过cas将新生成node节点插入table，若对应的node节点已经存在，则将sychronized锁住哈希桶进行更新或者插入尾巴的下一个节点）[CAS补充一下思想:CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。]

1:如果key=null或者value =null,那么对应的对应的异常

2:计算此key的hash值,然后就进入自旋，自旋确保数据可以插入。首先判断对应的table表为空或者长度为0，若为空，则初始化table表。

3：根据 key 的 hash 值取出 table 表中的结点元素，若取出的结点为空（该桶为空），则使用CAS将对应的key,value,hash放入对应的桶中。（就是上面图片中对于table的长度计算，对应还有没有空，有空的话，就生成对应的Node节点。）

4：若该结点的的 hash 值为 MOVED（-1），则对该桶中的结点进行转移。节点转移就是扩容的过程中。

5: 对于桶中的（第一个节点）进行加锁，然后进行遍历。，根据桶中的hash值和key值与本次添加key的值和根据key计算的hash 进行逐一比对。若出现相等的情况则根据对应的value值进行更新。否则就生成一个节点则赋值给最后一个节点的下一个节点。

6：若binCount的值达到一个转换为红黑树的阈值。则转换为红黑树。

ConcurrentHashmap 不支持 key 或者 value 为 null 的原因？

1：ConcurrentHashmap 和 Hashtable 都是支持并发的，当通过 get(k) 获取对应的 value 时，如果获取到的是 null 时，无法判断是 put(k,v) 的时候 value 为 null，还是这个 key 从来没有做过映射。
2：HashMap 是非并发的，可以通过 contains(key) 来做这个判断。
3：支持并发的 Map 在调用 m.contains(key) 和 m.get(key) 时，m 可能已经发生了更改。
因此 ConcurrentHashmap 和 Hashtable 都不支持 key 或者 value 为 null。