Java 知识点总结之Java 基本API（二）

太过爱你忘了你带给我的痛 2022-05-28 04:18 183阅读 0赞

### 7、JDK7.0下ConcurrentHashMap的内部实现机制，hash是怎么实现的，什么时候rehash ###

答：其基本结构如图所示：

![70][]

每一个segment都是一个HashEntry<K,V>\[\] table， table中的每一个元素本质上都是一个HashEntry的单向队列。比如table\[3\]为首节点，table\[3\]->next为节点1，之后为节点2，依次类推。

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
            implements ConcurrentMap<K, V>, Serializable {
    
        // 将整个hashmap分成几个小的map，每个segment都是一个锁；与hashtable相比，这么设计的目的是对于put, remove等操作，可以减少并发冲突，对
        // 不属于同一个片段的节点可以并发操作，大大提高了性能
        final Segment<K,V>[] segments;
    
        // 本质上Segment类就是一个小的hashmap，里面table数组存储了各个节点的数据，继承了ReentrantLock, 可以作为互拆锁使用
        static final class Segment<K,V> extends ReentrantLock implements Serializable {
            transient volatile HashEntry<K,V>[] table;
            transient int count;
        }
    
        // 基本节点，存储Key， Value值
        static final class HashEntry<K,V> {
            final int hash;
            final K key;
            volatile V value;
            volatile HashEntry<K,V> next;
        }
    }

### 8、JDK8.0下ConcurrentHashMap的内部实现机制，hash是怎么实现的，什么时候rehash ###

答：

改进一：取消segments字段，直接采用transient volatile HashEntry<K,V>\[\] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。

改进二：将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。对于hash表来说，最核心的能力在于将key hash之后能均匀的分布在数组中。如果hash之后散列的很均匀，那么table数组中的每个队列长度主要为0或者1。但实际情况并非总是如此理想，虽然ConcurrentHashMap类默认的加载因子为0.75，但是在数据量过大或者运气不佳的情况下，还是会存在一些队列长度过长的情况，如果还是采用单向列表方式，那么查询某个节点的时间复杂度为O(n)；因此，对于个数超过8(默认值)的列表，jdk1.8中采用了红黑树的结构，那么查询的时间复杂度可以降低到O(logN)，可以改进性能。

final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            // 如果table为空，初始化；否则，根据hash值计算得到数组索引i，如果tab[i]为空，直接新建节点Node即可。注：tab[i]实质为链表或者红黑树的首节点。
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin        }
            // 如果tab[i]不为空并且hash值为MOVED，说明该链表正在进行transfer操作，返回扩容完成后的table。
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                // 针对首个节点进行加锁操作，而不是segment，进一步减少线程冲突
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                // 如果在链表中找到值为key的节点e，直接设置e.val = value即可。
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                // 如果没有找到值为key的节点，直接新建Node并加入链表即可。
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        // 如果首节点为TreeBin类型，说明为红黑树结构，执行putTreeVal操作。
                        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) {
                    // 如果节点数>＝8，那么转换链表结构为红黑树结构。
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        // 计数增加1，有可能触发transfer操作(扩容)。
        addCount(1L, binCount);
        return null;
    }

补充：

ConcurrentHashMap(JDK1.8)为什么要使用synchronized而不是可重入锁？

1. 减少内存开销   
假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。   
2. 获得JVM的支持   
可重入锁毕竟是API这个级别的，后续的性能优化空间很小。   
synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。

1.     锁的粒度   
首先锁的粒度并没有变粗，甚至变得更细了。每当扩容一次，ConcurrentHashMap的并发度就扩大一倍。

2.     Hash冲突   
JDK1.7中，ConcurrentHashMap从过二次hash的方式（Segment -> HashEntry）能够快速的找到查找的元素。在1.8中通过链表加红黑树的形式弥补了put、get时的性能差距。

3.     扩容   
JDK1.8中，在ConcurrentHashmap进行扩容时，其他线程可以通过检测数组中的节点决定是否对这条链表（红黑树）进行扩容，减小了扩容的粒度，提高了扩容的效率。

### 9、foreach原理，如何边遍历边删除？ ###

答：（1）集合类都实现了Iterable接口，该接口中定义了Iterator迭代器

（2）边遍历边删除，需要用Iterator

Iterator<String>iter = list.iterator();
    
                       while(iter.hasNext()) {
    
                                Stringv = iter.next();
    
                                if("4".equals(v)) {
    
                                         iter.remove();
    
                                }
    
                       }

### 10、Java的队列都有哪些，有什么区别？ ###

答：（1）并发队列：ConcurrentLinkedQueue

ConcurrentLinkedQueue是Queue的一个安全实现，Queue中元素按FIFO原则进行排序，采用CAS操作，来保证元素的一致性。适用于高并发场景下的队列

（2）阻塞队列：BlockingQueue

BlockingQueue的主要功能并不在于提高并发时的队列性能，简化多线程之间的数据共享。BlockingQueue的典型应用在于生产者-消费者。才有ReentrantLock的Condition操作。

BlockingQueue提供了线程安全的队列访问方式：当阻塞队列进行插入数据时，如果队列已满，线程将会阻塞等待直到队列非满；从阻塞队列取数据时，如果队列已空，线程将会阻塞等待直到队列非空。

![70 1][]

抛异常：如果试图的操作无法立即执行，抛一个异常。

特定值：如果试图的操作无法立即执行，返回一个特定的值(常常是 true / false)。

阻塞：如果试图的操作无法立即执行，该方法调用将会发生阻塞，直到能够执行。

超时：如果试图的操作无法立即执行，该方法调用将会发生阻塞，直到能够执行，但等待时间不会超过给定值。返回一个特定值以告知该操作是否成功(典型的是true / false)。

ArrayBlockingQueue：ArrayBlockingQueue是一个有界的阻塞队列，其内部实现是将对象放到一个数组里。有界也就意味着，它不能够存储无限多数量的元素。它有一个同一时间能够存储元素数量的上限。你可以在对其初始化的时候设定这个上限，但之后就无法对这个上限进行修改了(译者注：因为它是基于数组实现的，也就具有数组的特性：一旦初始化，大小就无法修改)。

DelayQueue：DelayQueue 对元素进行持有直到一个特定的延迟到期。注入其中的元素必须实现 java.util.concurrent.Delayed 接口。

LinkedBlockingQueue：LinkedBlockingQueue内部以一个链式结构(链接节点)对其元素进行存储。如果需要的话，这一链式结构可以选择一个上限。如果没有定义上限，将使用 Integer.MAX\_VALUE 作为上限。

PriorityBlockingQueue：PriorityBlockingQueue是一个无界的并发队列。它使用了和类 java.util.PriorityQueue 一样的排序规则。你无法向这个队列中插入null 值。所有插入到 PriorityBlockingQueue 的元素必须实现java.lang.Comparable 接口。因此该队列中元素的排序就取决于你自己的Comparable 实现。

SynchronousQueue：SynchronousQueue是一个特殊的队列，它的内部同时只能够容纳单个元素。如果该队列已有一元素的话，试图向队列中插入一个新元素的线程将会阻塞，直到另一个线程将该元素从队列中抽走。同样，如果该队列为空，试图向队列中抽取一个元素的线程将会阻塞，直到另一个线程向队列中插入了一条新的元素。据此，把这个类称作一个队列显然是夸大其词了。它更多像是一个汇合点。

[70]: /images/20220528/359300945f9341d897fe03670bfeab0c.png
[70 1]: /images/20220528/ed9fa3bd67864f959340d5bed519a8e3.png