从0开始回顾Java---系列九

TreeMap

1、TreeMap 有什么特点？

1. TreeMap是基于红黑树的一种提供顺序访问的Map，增删改查的平均和最差时间复杂度均为 O(logn) ，最大特点是 Key 有序。
2. Key 必须实现 Comparable 接口或提供的 Comparator 比较器，所以 Key 不允许为 null。
3. TreeMap是一个线程不安全，有序的键值对集合，因为TreeMap实现了SotredMap接口。  
4. TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化；  

2、讲讲 TreeMap 怎么实现有序的？

TreeMap 是按照 Key 的自然顺序或者 Comprator 的顺序进行排序，内部是通过红黑树来实现。所以要么 key 所属的类实现 Comparable 接口，或者自定义一个实现了 Comparator 接口的比较器，传给 TreeMap 用于 key 的比较。

3、HashMap 和 TreeMap 的区别？

1. 数据结构：

• HashM：在JDK1.7 中，由“数组+链表”组成，在JDK1.8 中，由“数组+链表+红黑树”组成。
• TreeMap：红黑树

2. 线程安全

• HashMap 和 TreeMap 都不是线程安全的， 没有关键字synchronized修饰，也没有JUC包类的同步机制。

3. 实现的接口

• TreeMap 和 HashMap 都继承自 AbstractMap ，但是需要注意的是 TreeMap 它还实现了 NavigableMap 接口和 SortedMap 接口。

• 实现 AbstractMap 类，覆盖了hashcode() 和 equals() 方法，以确保两个相等的映射返回相同的哈希值。
• 实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。
• 实现 SortedMap 接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

4. 应用场景

• HashMap：适用于在Map中插入、删除和定位元素。
• Treemap：适用于按自然顺序或自定义顺序遍历键(key)。  

5. 效率

• HashMap是基于哈希桶实现的，平均时间复杂度为O(1)。
• TreeMap基于红黑树实现的，平均时间复杂度为O(logn)。

6. 是否有序

• HashMap是通过hashcode()对其内容进行快速查找的；HashMap中的元素是没有顺序的。
• TreeMap中所有的元素都是有某一固定顺序的，如果需要得到一个有序的结果，就应该使用TreeMap。

ConcurrentHashMap

1、ConcurrentHashMap 的实现原理是什么？

ConcurrentHashMap  在 JDK1.7 和 JDK1.8  的实现方式是不同的。

先来看下JDK1.7

1. 在 JDK7 中，ConcurrentHashMap 使用“分段锁”机制实现线程安全，数据结构可以看成是"Segment数组+HashEntry数组+链表"，一个 ConcurrentHashMap 实例中包含若干个 Segment 实例组成的数组，每个 Segment 实例又包含由若干个桶，每个桶中都是由若干个 HashEntry 对象链接起来的链表。是一个链表的结构，用于存储键值对数据。
2. 因为Segment 类继承 ReentrantLock 类，所以能充当锁的角色，通过 segment 段将 ConcurrentHashMap 划分为不同的部分，就可以使用不同的锁来控制对哈希表不同部分的修改，从而允许多个写操作并发进行，默认支持 16 个线程执行并发写操作，及任意数量线程的读操作。

再来看下JDK1.8

1. 在数据结构上， JDK1.8  中的ConcurrentHashMap  选择了与 HashMap 相同的数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加低粒度的锁。
2. 将锁的级别控制在了更细粒度的哈希桶元素级别，也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度。

2、ConcurrentHashMap  的 put 方法执行逻辑是什么？

先来看JDK1.7

首先，会尝试获取锁，如果获取失败，利用自旋获取锁；如果自旋重试的次数超过 64 次，则改为阻塞获取锁。

获取到锁后：

1. 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
2. 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
3. 为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
4. 释放 Segment 的锁。

再来看JDK1.8

大致可以分为以下步骤：

1. 根据 key 计算出 hash值。
2. 判断table是否需要进行初始化。
3. 定位到 Node，拿到首节点 f，判断首节点 f：

• 如果为  null  ，则通过cas的方式尝试添加。
• 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容。
• 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入。

4. 当在链表长度达到8的时候，数组扩容或者将链表转换为红黑树。

源码分析可看这篇文章：面试 ConcurrentHashMap ，看这一篇就够了！

3、ConcurrentHashMap  的 get 方法执行逻辑是什么？  

先来看JDK1.7

1. 首先，根据 key 计算出 hash 值定位到具体的 Segment ，再根据 hash 值获取定位 HashEntry 对象，并对 HashEntry 对象进行链表遍历，找到对应元素。
2. 由于 HashEntry 涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以每次获取时都是最新值。

再来看JDK1.8

大致可以分为以下步骤：

1. 根据 key 计算出 hash 值，判断数组是否为空；
2. 如果是首节点，就直接返回；
3. 如果是红黑树结构，就从红黑树里面查询；
4. 如果是链表结构，循环遍历判断。

4、ConcurrentHashMap 的 get 方法是否要加锁，为什么？

• get 方法不需要加锁，因为 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。
• 这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 安全效率高的原因之一。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //可以看到这些都用了volatile修饰
    volatile V val;
    volatile Node<K,V> next;
}

5、get方法不需要加锁与volatile修饰的哈希桶有关吗？

没有关系。哈希桶table用volatile修饰主要是保证在数组扩容的时候保证可见性。

6、ConcurrentHashMap  不支持 key 或者 value 为  null  的原因？支持-key-或者-value-为-null-的原因？

我们先来说value 为什么不能为 null ，因为ConcurrentHashMap是用于多线程的 ，如果map.get(key)得到了 null ，无法判断，是映射的value是 null ，还是没有找到对应的key而为 null ，这就有了二义性。

而用于单线程状态的HashMap却可以用containsKey(key) 去判断到底是否包含了这个 null 。

我们用反证法来推理：

1. 假设ConcurrentHashMap 允许存放值为 null 的value，这时有A、B两个线程，线程A调用ConcurrentHashMap .get(key)方法，返回为  null ，我们不知道这个 null 是没有映射的 null ，还是存的值就是 null。
2. 假设此时，返回为 null 的真实情况是没有找到对应的key。那么，我们可以用ConcurrentHashMap .containsKey(key)来验证我们的假设是否成立，我们期望的结果是返回false。
3. 但是在我们调用ConcurrentHashMap .get(key)方法之后，containsKey方法之前，线程B执行了ConcurrentHashMap .put(key, null  )的操作。那么我们调用containsKey方法返回的就是true了，这就与我们的假设的真实情况不符合了，这就有了二义性。

7、ConcurrentHashMap 的并发度是多少？

在JDK1.7中，并发度默认是16，这个值可以在构造函数中设置。如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度，也就是比如你设置的值是17，那么实际并发度是32。

8、ConcurrentHashMap 迭代器是强一致性还是弱一致性？

1. 与HashMap迭代器是强一致性不同，ConcurrentHashMap 迭代器是弱一致性。
2. ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。
3. 这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。

9、JDK1.7与JDK1.8 中ConcurrentHashMap 的区别？

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

Hashtable

1、ConcurrentHashMap 和Hashtable的效率哪个更高？为什么？

• ConcurrentHashMap 的效率要高于Hashtable，因为Hashtable给整个哈希表加了一把大锁从而实现线程安全。
• ConcurrentHashMap 的锁粒度更低，在JDK1.7中采用分段锁实现线程安全，在JDK1.8 中采用CAS+Synchronized实现线程安全。

2、Hashtable的锁机制 ?

Hashtable是使用Synchronized来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差！

3、ConcurrentHashMap 和 Hashtable 的区别？

1. 底层数据结构：

• JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。
• Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

2. 实现线程安全的方式（重要）：

• 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作；
• Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

3. 效率

• ConcurrentHashMap 的效率要高于Hashtable，因为Hashtable给整个哈希表加了一把大锁从而实现线程安全。