并发编程（六）

1、HashMap、HashTable、ConcurrentHashMap的比较

HashMap、HashTable和ConcurrentHashMap是Java中的几种重要的数据结构，它们都可以用来存储键值对。但是，它们之间存在一些重要的差异，尤其是在线程安全和性能方面。以下是它们之间的比较：

①线程安全：

HashMap：是非线程安全的。如果多个线程同时修改HashMap，那么它不会提供任何形式的同步。

HashTable：是线程安全的。它的所有公共方法都是同步的，因此一次只有一个线程可以访问这个表。

ConcurrentHashMap：也是线程安全的，但它比HashTable更高效。ConcurrentHashMap使用了分段锁技术，这意味着它的大部分操作（如get和put）都是线程安全的，即使在并发环境下也不会阻塞。

②性能：

HashMap：在单线程环境下通常有最好的性能，因为它不需要进行任何同步。

HashTable：在多线程环境下，由于其同步机制，性能可能会受到影响。

ConcurrentHashMap：在多线程环境下提供了更好的性能，因为它使用了分段锁技术，减少了锁的竞争。

③初始容量和加载因子：

HashMap 和 HashTable：允许你设置初始容量和加载因子，但它们通常需要手动调整。

ConcurrentHashMap：内部实现了动态调整大小的功能，因此通常不需要手动设置这些参数。

④迭代器：

HashMap 和 HashTable：迭代器是弱一致性的，意味着它们不会抛出ConcurrentModification Exception。但是，迭代器并不保证能反映出在迭代过程中对映射所做的修改。

ConcurrentHashMap：迭代器也是弱一致性的，类似于HashMap和HashTable。但是，它提供了一种称为“条件性弱一致性”的迭代器，可以安全地用于几乎所有并发修改的情况。

⑤null键和值：

HashMap 和 HashTable：允许null键和值。

ConcurrentHashMap：不允许null键和值。

⑥访问顺序：

HashMap 和 HashTable：不保证元素的访问顺序。

ConcurrentHashMap：提供了一种基于红黑树的并发哈希映射实现，因此它可以保证元素的有序性。但是，这并不是通过锁机制实现的，而是在内部使用了更复杂的算法。

2、HashMap的实现原理（jdk1.7与jdk1.8对比）

HashMap是Java中常用的数据结构之一，它使用哈希表来存储键值对。在JDK 1.7和JDK 1.8中，HashMap的实现原理有所不同，主要体现在扩容、冲突解决和数据结构优化等方面。

在JDK 1.7中，HashMap使用数组+链表的方式实现。当发生哈希冲突时，将链表存储在同一个数组位置上。当数组容量超过一定阈值（默认为8）时，会对数组进行扩容。扩容后，需要重新计算所有元素的哈希值，并将元素重新放入新的数组中。此外，JDK 1.7中的HashMap不支持null键和null值。

在JDK 1.8中，HashMap进行了许多优化和改进。首先，它使用数组+链表+红黑树的方式实现，以提高搜索效率。当链表长度超过一定阈值（默认为8）时，将链表转换为红黑树。此外，JDK 1.8中的HashMap扩容更加高效，扩容后不再需要重新计算所有元素的哈希值。此外，JDK 1.8中的HashMap还支持null键和null值。

3、HashMap扩容会导致的问题

HashMap扩容会导致一些问题，主要包括性能下降和死循环问题。

1. 性能下降：当HashMap需要扩容时，需要重新计算所有元素的哈希值，并将元素重新放入新的数组中。这个过程需要消耗大量的计算资源，并且会阻塞其他线程对哈希表的访问。因此，在扩容期间，HashMap的性能会显著下降。
2. 死循环问题：在JDK 1.7中，HashMap扩容后使用了头插法将元素插入到新的数组中，可能会导致出现环链问题。在多个线程同时进行扩容操作的情况下，可能会出现一个线程已经完成扩容操作，而另一个线程还在进行扩容操作的情况。此时，如果使用头插法插入元素，可能会出现环链问题，导致死循环。

为了避免这些问题，可以使用ConcurrentHashMap代替HashMap，因为ConcurrentHashMap使用了分段锁技术，可以避免锁竞争和死循环问题。同时，也可以预先指定HashMap的初始容量，以减少扩容的频率，提高性能。

4、ConcurrentHashMap的实现原理（jdk1.7与jdk1.8对比）

ConcurrentHashMap是Java中线程安全的哈希表实现，它在JDK 1.7和JDK 1.8中也有一些不同的实现原理和优化。

在JDK 1.7中，ConcurrentHashMap使用分段锁技术实现线程安全。它将整个哈希表分成若干个段（Segment），每个段都是一个小的哈希表。对某个段进行操作时，只需要对该段加锁，不会阻塞其他线程对其他段的访问。这种实现方式可以显著提高并发性能，因为多个线程可以同时访问不同的段。但是，由于每个段都是一个小的哈希表，因此在高并发情况下，可能会存在热点数据问题，即多个线程同时访问同一个段，导致锁竞争激烈。

在JDK 1.8中，ConcurrentHashMap进行了许多优化和改进。首先，它使用红黑树实现哈希表的平衡搜索。当链表长度超过一定阈值（默认为8）时，将链表转换为红黑树，提高搜索效率。此外，JDK 1.8中的ConcurrentHashMap还使用了锁分段技术，将整个哈希表分成若干个桶（Bucket），每个桶都对应一个锁。这种技术可以提高并发性能，同时避免热点数据问题。此外，JDK 1.8中的ConcurrentHashMap还使用了一种称为“写前通知”（Write-Ahead Notification）的机制，可以提高并发写操作的性能。

5、为什么要使用ConcurrentHashMap

在并发编程中使用HashMap可能导致程序死循环。而使用线程安全的HashTable效率又非

常低下，基于以上两个原因，便有了ConcurrentHashMap的登场机会。

（1）线程不安全的HashMap

在多线程环境下，使用HashMap进行put操作会引起死循环，导致CPU利用率接近100%，所

以在并发情况下不能使用HashMap。例如，执行以下代码会引起死循环。

HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表

形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获

取Entry。

（2）效率低下的HashTable

HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable

的效率非常低下。因为当一个线程访问HashTable的同步方法，其他线程也访问HashTable的同

步方法时，会进入阻塞或轮询状态。如线程1使用put进行元素添加，线程2不但不能使用put方

法添加元素，也不能使用get方法来获取元素，所以竞争越激烈效率越低。

（3）ConcurrentHashMap的锁分段技术可有效提升并发访问率

HashTable容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的

线程都必须竞争同一把锁，假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么

当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效提高并

发访问效率，这就是ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段地存

储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数

据也能被其他线程访问。

6、java中的阻塞队列

ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。

·LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列。

·PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。

·DelayQueue：一个使用优先级队列实现的无界阻塞队列。

·SynchronousQueue：一个不存储元素的阻塞队列。

·LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。

·LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

7、Fork/Join框架

一个用于并行执行任务的框架，是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。