面试题：Java中ConcurrentHashMap与Hashtable在高并发场景下性能对比及原理

Question

在高并发环境中，ConcurrentHashMap与Hashtable的性能表现有何差异？详细说明两者在实现机制上如何影响性能，例如锁的粒度、数据结构等方面。

Answer 1

性能差异

1. ConcurrentHashMap：在高并发环境下性能更优。因为它采用了更细粒度的锁机制，允许多个线程同时访问不同的段（Segment，在Java 8后摒弃了Segment概念，采用Node数组 + 链表/红黑树结构，并使用CAS和synchronized实现并发控制），大大降低了锁竞争的可能性，提高了并发访问效率。
2. Hashtable：性能较差。它使用一个全局锁来保证线程安全，同一时间只允许一个线程访问，这在高并发场景下会导致大量线程等待，严重影响性能。

实现机制对性能的影响

1. 锁的粒度
   • ConcurrentHashMap：
     • Java 7及之前：将数据分成多个Segment，每个Segment独立加锁，锁的粒度细化到Segment级别，不同Segment之间可以并发访问。例如，假设有16个Segment，当一个线程对其中一个Segment进行写操作时，其他线程可以同时对其他Segment进行读写操作。
     • Java 8及之后：摒弃了Segment概念，采用Node数组 + 链表/红黑树结构，使用CAS和synchronized关键字实现并发控制。在链表头节点或树的根节点上加锁，锁的粒度进一步细化到单个节点，并发性能更高。例如，在插入新节点时，首先通过CAS操作尝试直接插入，如果失败则使用synchronized锁住该节点所在链表或树的根节点进行插入。
   • Hashtable：对整个哈希表加锁，所有的读写操作都需要获取这个全局锁。这意味着当一个线程正在进行读或写操作时，其他线程都必须等待锁的释放，极大地限制了并发性能。
2. 数据结构
   • ConcurrentHashMap：
     • Java 7及之前：内部由Segment数组和HashEntry数组组成。Segment继承自ReentrantLock，每个Segment包含一个HashEntry数组，HashEntry用来存储键值对。这种结构使得ConcurrentHashMap在保证线程安全的同时能提高并发性能。
     • Java 8及之后：采用Node数组 + 链表/红黑树结构。当链表长度超过阈值（默认为8）时，链表会转换为红黑树，以提高查找效率。这种数据结构的设计在保证并发性能的同时，也优化了查找、插入和删除操作的时间复杂度。
   • Hashtable：采用数组 + 链表的传统哈希表结构。在高并发环境下，由于锁的粒度较大，链表的遍历和操作容易成为性能瓶颈，尤其是当链表长度较长时，查找、插入和删除操作的时间复杂度会退化为O(n)。