Java 知识点总结之Java 基本API(二)

标签: java

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

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


每一个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提供了线程安全的队列访问方式:当阻塞队列进行插入数据时,如果队列已满,线程将会阻塞等待直到队列非满;从阻塞队列取数据时,如果队列已空,线程将会阻塞等待直到队列非空。

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

特定值:如果试图的操作无法立即执行,返回一个特定的值(常常是 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是一个特殊的队列,它的内部同时只能够容纳单个元素。如果该队列已有一元素的话,试图向队列中插入一个新元素的线程将会阻塞,直到另一个线程将该元素从队列中抽走。同样,如果该队列为空,试图向队列中抽取一个元素的线程将会阻塞,直到另一个线程向队列中插入了一条新的元素。据此,把这个类称作一个队列显然是夸大其词了。它更多像是一个汇合点。


版权声明:本文为sunct原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sunct/article/details/79741461

智能推荐

线索二叉树-c++实现

基本思想 1.根据用户输入创建二叉树(一般用前序遍历) 2.线索化二叉树(一般用中序遍历线索化)(此时要把head节点加进来) 3.通过输出中序遍历结果来检验线索化是否正确 详细注释在代码中,可以先看main函数中的流程,再看具体函数实现 实验中采用的二叉树如图 完整代码 运行结果如图所示...

Hadoop实战(4)_Hadoop的集群管理和资源分配

系列目录: Hadoop实战(1)_阿里云搭建Hadoop2.x的伪分布式环境 Hadoop实战(2)_虚拟机搭建Hadoop的全分布模式 Hadoop实战(3)_虚拟机搭建CDH的全分布模式 DataNode数据目录 如果有多个挂载点,可以有多个DataNode数据目录。 目前服务器硬件,标准小型机配置:32核、64G(128G)、64T(4T*16盘SAS盘)。通常为了提升磁盘吞吐量,每个盘单...

Tornado day02

一,项目模板: Tornado的项目也可以像Django和flask一样,将功能细分为几个模块 1.1 _ _ init _ _.py 1.2 setting .py 1.3 urls .py 1.4 views .py 1.5 manage .py 将这个模板拷贝下来,以后创建新项目的时候可以直接拷贝一份,在此模板上修改使用 文件链接 链接:https://pan.baidu.com/s/11E...

PAT乙级 | 1095 解码PAT准考证 (25分)(做题过程+注意事项+运行超时解决方法)

PAT 准考证号由 4 部分组成: 第 1 位是级别,即 T 代表顶级;A 代表甲级;B 代表乙级; 第 2~4 位是考场编号,范围从 101 到 999; 第 5~10 位是考试日期,格式为年、月、日顺次各占 2 位; 最后 11~13 位是考生编号,范围从 000 到 999。 现给定一系列考生的准考证号和他们的成绩,请你按照要求输出各种统计信息。 输入格式: 输入首先在一行中给出两个正整数 ...

谈谈Java异常

0 概述 对于java工程师来说,是经常和异常打交道的,本文主要来谈一谈java中的异常。 1 异常类的继承关系 从下图(说明:图中只是列出部分异常类)可以看出: 异常的基类为Throwable,主要分为两个分支,即Error体系和Exception体系。 Exception下面分为RuntimeException和非RuntimeException(如IOException) 2 几种异常的区别...

猜你喜欢

通过设立FatFS隐藏分区,实现系统文件和用户文件的隔离

嘛。。这是一个关于个人使用FatFS文件系统的 一点小的经验。 我知道大家都会百度和谷歌,关于文件系统有什么用,文件系统怎么移植上自己的平台,看看资料也就懂了,在这里不再详述( 打字太慢一分钟50-60字懒得写)。本系列默认已经可以将设备模拟成u盘,并且已经通过修改diskio.c,可以实现ff.c中的各项功能( 不能实现的自行面壁)。FatFS项目官网 http://elm-chan.org/f...

Mysql之锁与事务知识要点小结

Mysql之锁与事务 平时的业务中,顶多也就是写写简单的sql,连事务都用的少,对锁这一块的了解就更加欠缺了,之前一个大神分享了下mysql的事务隔离级别,感觉挺有意思的,正好发现一个很棒的博文,然后也收集了一些相关知识,正好来学习下,mysql中锁与事务的神秘面纱,主要内容包括 共享锁和排它锁的区别以及适合范围 mysql的表锁和行锁的区别 怎么判断一个sql是否执行了锁,执行的是表锁还是行锁 ...

响应式图片二 通过srcset实现

具体方法如下: srcset=”图片地址+空格+尺寸描述符,图片地址+空格+尺寸描述符,图片地址+空格+尺寸描述符….” 浏览器会当前浏览的环境进行感知,这个感知包括网速、界面分辨率、DPR(屏幕像素比)等等,然后在图片中选择一个进行加载。 实际上,在相同DPR下,浏览器会根据屏幕的分辨率加载图片,但是加载了大的图片后再缩小还是会使用大的图片。综合考虑的算法非...

Training_model(2)

已经清洗处理了两个数据文件: application_{train|test}.csv :客户详细信息 bureau.csv : 客户历史信用报告 下面对这两个数据中的特征进行合并,然后Light Gradient Boosting Machine训练模型,之前只用客户数据的预测评分结果是0.734,这次加入了客户信用报告信息 load data 新增加了客户历史信用记录 Build Model ...

微信小程序 页面跳转(传参跟不传参)

跳转页面传参 1.首先我的目录结构是这样的,并在 cinema.wxml 定义了一个点击事件 bindtap=‘indetai’ 2.然后在 cinema.js 的data里面定义了一个 score,并实现了 indetai 方法 3.在 detai.js 的 data 里面也定义一个 score ,再在 onLoad 函数里面接收传递过来的值 4.在页面上显示得到的值 这...