一、java源码相关
HashMap 的创建,put原理,和HashTable的区别,resize的原理,currentHashMap线程安全的具体实现,分段锁
底层结构
//默认初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//默认负载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//Hash数组(在resize()中初始化)
transient Node<K,V>[] table;
//元素个数
transient int size;
//容量阈值(元素个数超过该值会自动扩容)
int threshold;
// 底层结构时Node组成的数组,下面时Node的实现
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);//^表示相同返回0,不同返回1
//Objects.hashCode(o)————>return o != null ? o.hashCode() : 0;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
//Objects.equals(1,b)————> return (a == b) || (a != null && a.equals(b));
if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
扩容
主要逻辑是resize方法,如下
/*扩容*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 容量阈值(元素个数超过该值会自动扩容)
int oldThr = threshold;
int newCap, newThr = 0;
//1、若旧数组长度oldCap>0 说明hash数组table已被初始化
if (oldCap > 0) {
// 如果旧的数组长度大于等于位运算结果(1 << 30),即达到最大容量无法扩容,返回旧的长度
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}//按当前table数组长度的2倍进行扩容,容量阈值也变为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}//2、若数组未被初始化,而threshold>0说明调用了HashMap(initialCapacity)和HashMap(initialCapacity, loadFactor)构造器
else if (oldThr > 0)
newCap = oldThr;//新容量设为数组阈值
else { //3、若table数组未被初始化,且threshold为0说明调用HashMap()构造方法
newCap = DEFAULT_INITIAL_CAPACITY;//默认初始容量为16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//默认初始扩容阈值16*0.75
}
//若计算过程中,阈值溢出归零,则按阈值公式重新计算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//创建新的hash数组,hash数组的初始化也是在这里完成的
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果旧的hash数组不为空,则遍历旧数组并映射到新的hash数组
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//GC
if (e.next == null)//如果只链接一个节点,重新计算并放入新数组
newTab[e.hash & (newCap - 1)] = e;
//若是红黑树,则需要进行拆分
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//rehash————>重新映射到新数组
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
/*注意这里使用的是:e.hash & oldCap,若为0则索引位置不变,不为0则新索引=原索引+旧数组长度*/
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
currentHashMap线程安全的实现
1.HashMap
我们知道HashMap是线程不安全的,在多线程环境下,使用Hashmap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。
2.HashTable
HashTable和HashMap的实现原理几乎一样,差别无非是
- HashTable不允许key和value为null
- HashTable是线程安全的
但是HashTable线程安全的策略实现代价却太大了,简单粗暴,get/put所有相关操作都是synchronized的,这相当于给整个哈希表加了一把大锁。
多线程访问时候,只要有一个线程访问或操作该对象,那其他线程只能阻塞,相当于将所有的操作串行化,在竞争激烈的并发场景中性能就会非常差。
3.ConcurrentHashMap
主要就是为了应对hashmap在并发环境下不安全而诞生的,ConcurrentHashMap的设计与实现非常精巧,大量的利用了volatile,final,CAS等lock-free技术来减少锁竞争对于性能的影响。
我们都知道Map一般都是数组+链表结构(JDK1.8该为数组+红黑树)。
ConcurrentHashMap避免了对全局加锁改成了局部加锁操作,这样就极大地提高了并发环境下的操作速度,由于ConcurrentHashMap在JDK1.7和1.8中的实现非常不同,接下来我们谈谈JDK在1.7和1.8中的区别。
JDK1.7版本的CurrentHashMap的实现原理
在JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。
1.Segment(分段锁)
ConcurrentHashMap中的分段锁称为Segment,它即类似于HashMap的结构,即内部拥有一个Entry数组,数组中的每个元素又是一个链表,同时又是一个ReentrantLock(Segment继承了ReentrantLock)。
2.内部结构
ConcurrentHashMap使用分段锁技术,将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问,能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图:
从上面的结构我们可以了解到,ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。
第一次Hash定位到Segment,第二次Hash定位到元素所在的链表的头部。
3.该结构的优劣势
坏处
这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长
好处
写操作的时候可以只对元素所在的Segment进行加锁即可,不会影响到其他的Segment,这样,在最理想的情况下,ConcurrentHashMap可以最高同时支持Segment数量大小的写操作(刚好这些写操作都非常平均地分布在所有的Segment上)。
所以,通过这一种结构,ConcurrentHashMap的并发能力可以大大的提高。
JDK1.8版本的CurrentHashMap的实现原理
JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现,采用了数组+链表+红黑树的实现方式来设计,内部大量采用CAS操作,这里我简要介绍下CAS。
CAS是compare and swap的缩写,即我们所说的比较交换。cas是一种基于锁的操作,而且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住,等一个之前获得锁的线程释放锁之后,下一个线程才可以访问。而乐观锁采取了一种宽泛的态度,通过某种方式不加锁来处理资源,比如通过给记录加version来获取数据,性能较悲观锁有很大的提高。
CAS 操作包含三个操作数 —— 内存位置(V)、预期原值(A)和新值(B)。如果内存地址里面的值和A的值是一样的,那么就将内存里面的值更新成B。CAS是通过无限循环来获取数据的,若果在第一轮循环中,a线程获取地址里面的值被b线程修改了,那么a线程需要自旋,到下次循环才有可能机会执行。
JDK8中彻底放弃了Segment转而采用的是Node,其设计思想也不再是JDK1.7中的分段锁思想。
Node:保存key,value及key的hash值的数据结构。其中value和next都用volatile修饰,保证并发的可见性。
class Node<K,V> implements Map.Entry<K,V> {
final int hash; final K key; volatile V val; volatile Node<K,V> next; //... 省略部分代码
}
Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样,不过保证线程安全性。
在JDK8中ConcurrentHashMap的结构,由于引入了红黑树,使得ConcurrentHashMap的实现非常复杂,我们都知道,红黑树是一种性能非常好的二叉查找树,其查找性能为O(logN),但是其实现过程也非常复杂,而且可读性也非常差,DougLea的思维能力确实不是一般人能比的,早期完全采用链表结构时Map的查找时间复杂度为O(N),JDK8中ConcurrentHashMap在链表的长度大于8的时候会将链表转换成红黑树进一步提高其查找性能。
总结
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言,ConcurrentHashMap只是增加了同步的操作来控制并发,从JDK1.7版本的ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。
1.数据结构:取消了Segment分段锁的数据结构,取而代之的是数组+链表+红黑树的结构。
2.保证线程安全机制:JDK1.7采用segment的分段锁机制实现线程安全,其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
3.锁的粒度:原来是对需要进行数据操作的Segment加锁,现调整为对每个数组元素加锁(Node)。
4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时,会将链表转化为红黑树进行存储。
5.查询时间复杂度:从原来的遍历链表O(n),变成遍历红黑树O(logN)。
各种IO交互(AIO/ NIO/ BIO)
同步与异步
同步: 同步就是发起一个调用后,被调用者未处理完请求之前,调用不返回。
异步: 异步就是发起一个调用后,立刻得到被调用者的回应表示已接收到请求,但是被调用者并没有返回结果,此时我们可以处理其他的请求,被调用者通常依靠事件,回调等机制来通知调用者其返回结果。
同步和异步的区别最大在于异步的话调用者不需要等待处理结果,被调用者会通过回调等机制来通知调用者其返回结果。
阻塞和非阻塞
阻塞: 阻塞就是发起一个请求,调用者一直等待请求结果返回,也就是当前线程会被挂起,无法从事其他任务,只有当条件就绪才能继续。
非阻塞: 非阻塞就是发起一个请求,调用者不用一直等着结果返回,可以先去干其他事情。
那么同步阻塞、同步非阻塞和异步非阻塞又代表什么意思呢?
举个生活中简单的例子,你妈妈让你烧水,小时候你比较笨啊,在哪里傻等着水开(同步阻塞)。等你稍微再长大一点,你知道每次烧水的空隙可以去干点其他事,然后只需要时不时来看看水开了没有(同步非阻塞)。后来,你们家用上了水开了会发出声音的壶,这样你就只需要听到响声后就知道水开了,在这期间你可以随便干自己的事情,你需要去倒水了(异步非阻塞)。
1. BIO (Blocking I/O)
同步阻塞I/O模式,数据的读取写入必须阻塞在一个线程内等待其完成。
1.1 传统 BIO
BIO通信(一请求一应答)模型图如下(图源网络,原出处不明):
image采用BIO 通信模型的服务端,通常由一个独立的 Acceptor 线程负责监听客户端的连接。我们一般通过在while(true)
循环中服务端会调用accept()
方法等待接收客户端的连接的方式监听请求,请求一旦接收到一个连接请求,就可以建立通信套接字在这个通信套接字上进行读写操作,此时不能再接收其他客户端连接请求,只能等待同当前连接的客户端的操作执行完成, 不过可以通过多线程来支持多个客户端的连接,如上图所示。
如果要让BIO 通信模型能够同时处理多个客户端请求,就必须使用多线程(主要原因是socket.accept()
、socket.read()
、socket.write()
涉及的三个主要函数都是同步阻塞的),也就是说它在接收到客户端连接请求之后为每个客户端创建一个新的线程进行链路处理,处理完成之后,通过输出流返回应答给客户端,线程销毁。这就是典型的一请求一应答通信模型。我们可以设想一下如果这个连接不做任何事情的话就会造成不必要的线程开销,不过可以通过线程池机制改善,线程池还可以让线程的创建和回收成本相对较低。使用FixedThreadPool
可以有效的控制了线程的最大数量,保证了系统有限的资源的控制,实现了N(客户端请求数量):M(处理客户端请求的线程数量)的伪异步I/O模型(N 可以远远大于 M),下面一节"伪异步 BIO"中会详细介绍到。
我们再设想一下当客户端并发访问量增加后这种模型会出现什么问题?
在 Java 虚拟机中,线程是宝贵的资源,线程的创建和销毁成本很高,除此之外,线程的切换成本也是很高的。尤其在 Linux 这样的操作系统中,线程本质上就是一个进程,创建和销毁线程都是重量级的系统函数。如果并发访问量增加会导致线程数急剧膨胀可能会导致线程堆栈溢出、创建新线程失败等问题,最终导致进程宕机或者僵死,不能对外提供服务。
1.2 伪异步 IO
为了解决同步阻塞I/O面临的一个链路需要一个线程处理的问题,后来有人对它的线程模型进行了优化一一一后端通过一个线程池来处理多个客户端的请求接入,形成客户端个数M:线程池最大线程数N的比例关系,其中M可以远远大于N.通过线程池可以灵活地调配线程资源,设置线程的最大值,防止由于海量并发接入导致线程耗尽。
伪异步IO模型图(图源网络,原出处不明):
采用线程池和任务队列可以实现一种叫做伪异步的 I/O 通信框架,它的模型图如上图所示。当有新的客户端接入时,将客户端的 Socket 封装成一个Task(该任务实现java.lang.Runnable接口)投递到后端的线程池中进行处理,JDK 的线程池维护一个消息队列和 N 个活跃线程,对消息队列中的任务进行处理。由于线程池可以设置消息队列的大小和最大线程数,因此,它的资源占用是可控的,无论多少个客户端并发访问,都不会导致资源的耗尽和宕机。
伪异步I/O通信框架采用了线程池实现,因此避免了为每个请求都创建一个独立线程造成的线程资源耗尽问题。不过因为它的底层任然是同步阻塞的BIO模型,因此无法从根本上解决问题。
总结
在活动连接数不是特别高(小于单机1000)的情况下,这种模型是比较不错的,可以让每一个连接专注于自己的 I/O 并且编程模型简单,也不用过多考虑系统的过载、限流等问题。线程池本身就是一个天然的漏斗,可以缓冲一些系统处理不了的连接或请求。但是,当面对十万甚至百万级连接的时候,传统的 BIO 模型是无能为力的。因此,我们需要一种更高效的 I/O 处理模型来应对更高的并发量。
NIO 简介
NIO是一种同步非阻塞的I/O模型,在Java 1.4 中引入了NIO框架,对应 java.nio 包,提供了 Channel , Selector,Buffer等抽象。
NIO中的N可以理解为Non-blocking,不单纯是New。它支持面向缓冲的,基于通道的I/O操作方法。 NIO提供了与传统BIO模型中的Socket
和ServerSocket
相对应的SocketChannel
和ServerSocketChannel
两种不同的套接字通道实现,两种通道都支持阻塞和非阻塞两种模式。阻塞模式使用就像传统中的支持一样,比较简单,但是性能和可靠性都不好;非阻塞模式正好与之相反。对于低负载、低并发的应用程序,可以使用同步阻塞I/O来提升开发速率和更好的维护性;对于高负载、高并发的(网络)应用,应使用 NIO 的非阻塞模式来开发。
2.2 NIO的特性/NIO与IO区别
如果是在面试中回答这个问题,我觉得首先肯定要从 NIO 流是非阻塞 IO 而 IO 流是阻塞 IO 说起。然后,可以从 NIO 的3个核心组件/特性为 NIO 带来的一些改进来分析。如果,你把这些都回答上了我觉得你对于 NIO 就有了更为深入一点的认识,面试官问到你这个问题,你也能很轻松的回答上来了。
1)Non-blocking IO(非阻塞IO)
IO流是阻塞的,NIO流是不阻塞的。
Java NIO使我们可以进行非阻塞IO操作。比如说,单线程中从通道读取数据到buffer,同时可以继续做别的事情,当数据读取到buffer中后,线程再继续处理数据。写数据也是一样的。另外,非阻塞写也是如此。一个线程请求写入一些数据到某通道,但不需要等待它完全写入,这个线程同时可以去做别的事情。
Java IO的各种流是阻塞的。这意味着,当一个线程调用read()
或write()
时,该线程被阻塞,直到有一些数据被读取,或数据完全写入。该线程在此期间不能再干任何事情了
2)Buffer(缓冲区)
IO 面向流(Stream oriented),而 NIO 面向缓冲区(Buffer oriented)。
Buffer是一个对象,它包含一些要写入或者要读出的数据。在NIO类库中加入Buffer对象,体现了新库与原I/O的一个重要区别。在面向流的I/O中·可以将数据直接写入或者将数据直接读到 Stream 对象中。虽然 Stream 中也有 Buffer 开头的扩展类,但只是流的包装类,还是从流读到缓冲区,而 NIO 却是直接读到 Buffer 中进行操作。
在NIO厍中,所有数据都是用缓冲区处理的。在读取数据时,它是直接读到缓冲区中的; 在写入数据时,写入到缓冲区中。任何时候访问NIO中的数据,都是通过缓冲区进行操作。
最常用的缓冲区是 ByteBuffer,一个 ByteBuffer 提供了一组功能用于操作 byte 数组。除了ByteBuffer,还有其他的一些缓冲区,事实上,每一种Java基本类型(除了Boolean类型)都对应有一种缓冲区。
3)Channel (通道)
NIO 通过Channel(通道) 进行读写。
通道是双向的,可读也可写,而流的读写是单向的。无论读写,通道只能和Buffer交互。因为 Buffer,通道可以异步地读写。
4)Selectors(选择器)
NIO有选择器,而IO没有。
选择器用于使用单个线程处理多个通道。因此,它需要较少的线程来处理这些通道。线程之间的切换对于操作系统来说是昂贵的。 因此,为了提高系统效率选择器是有用的。
2.3 NIO 读数据和写数据方式
通常来说NIO中的所有IO都是从 Channel(通道) 开始的。
从通道进行数据读取 :创建一个缓冲区,然后请求通道读取数据。
从通道进行数据写入 :创建一个缓冲区,填充数据,并要求通道写入数据。
数据读取和写入操作图示:
2.4 NIO核心组件简单介绍
NIO 包含下面几个核心的组件:
Channel(通道)
Buffer(缓冲区)
Selector(选择器)
什么是BIO
BIO:同步并阻塞,服务器实现一个连接一个线程,即客户端有连接请求时服务器端就需要启动一个线程进行处理,没处理完之前此线程不能做其他操作(如果是单线程的情况下,我传输的文件很大呢?),当然可以通过线程池机制改善。BIO方式适用于连接数目比较小且固定的架构,这种方式对服务器资源要求比较高,并发局限于应用中,JDK1.4以前的唯一选择,但程序直观简单易理解。
什么是NIO
NIO:同步非阻塞,服务器实现一个连接一个线程,即客户端发送的连接请求都会注册到多路复用器上,多路复用器轮询到连接有I/O请求时才启动一个线程进行处理。NIO方式适用于连接数目多且连接比较短(轻操作)的架构,比如聊天服务器,并发局限于应用中,编程比较复杂,JDK1.4之后开始支持。
什么是AIO
AIO:异步非阻塞,服务器实现模式为一个有效请求一个线程,客户端的I/O请求都是由操作系统先完成了再通知服务器应用去启动线程进行处理,AIO方式使用于连接数目多且连接比较长(重操作)的架构,比如相册服务器,充分调用操作系统参与并发操作,编程比较复杂,JDK1.7之后开始支持。.
AIO属于NIO包中的类实现,其实IO主要分为BIO和NIO,AIO只是附加品,解决IO不能异步的实现
在以前很少有Linux系统支持AIO,Windows的IOCP就是该AIO模型。但是现在的服务器一般都是支持AIO操作
- ==与equals
==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
==是指对内存地址进行比较
equals()是对字符串的内容进行比较
==指引用是否相同 equals()指的是值是否相同
- String和Stringbuffer和Stringbuilder的区别
String 类不可变,内部维护的char[] 数组长度不可变,为final修饰,String类也是final修饰,不存在扩容。字符串拼接,截取,都会生成一个新的对象。频繁操作字符串效率低下,因为每次都会生成新的对象。
StringBuilder 类内部维护可变长度char[] , 初始化数组容量为16,存在扩容, 其append拼接字符串方法内部调用System的native方法,进行数组的拷贝,不会重新生成新的StringBuilder对象。非线程安全的字符串操作类, 其每次调用 toString方法而重新生成的String对象,不会共享StringBuilder对象内部的char[],会进行一次char[]的copy操作。
StringBuffer 类内部维护可变长度char[], 基本上与StringBuilder一致,但其为线程安全的字符串操作类,大部分方法都采用了Synchronized关键字修改,以此来实现在多线程下的操作字符串的安全性。其toString方法而重新生成的String对象,会共享StringBuffer对象中的toStringCache属性(char[]),但是每次的StringBuffer对象修改,都会置null该属性值。
二、 JVM相关(bookname:深入理解java虚拟机)
- jvm分区
- java文件加载到gc全流程,双亲委派和怎样打破双亲委派
- fullGC触发条件
- 内存分代逻辑
- gc收集算法(标记计数算法,可达性算法)gc清理逻辑
- G1/CMS收集器
- 堆栈溢出原因,处理
- 内存分配和回收策略
- 虚拟机监控和故障处理工具
- jvm调优
- web容器加载器架构实现(tomcat,jetty……)
三、多线程
- 线程池的创建有几种方式,队列,异常处理
- submit和excute使用的区别,怎样避免死锁
- 线程的锁机制(lock和synchronized)原子类,锁,同步锁,自旋锁,CAS
- 线程调度相关
- 线程安全,锁优化
四、数据库
- mysql中innodb myisam 两种引擎区别,是否支持事物,索引实现(B+,Hash)复合索引/二叉树
- 数据库索引,所有优缺点 最左前缀原则
- InnoDB聚集索引
- 为什么用B+树,减少io,一颗B+树的节点大小为多大
- 为什么一个节点为1页
- group by和order by
- 数据库调优
- 大量数据下分库分表处理
- 跨多数据库查询
- cap,CAP即,一致性(Consistency), 可用性(Availability), 分区容忍性(Partition tolerance);
- redis有什么优点(单线程,分布式,持久化,事务,原子性)
- redis持久化,分布式锁,redis为什么快,原理?
- redis的主从 、哨兵的实现原理
- redis支持的数据操作类型,发布订阅,计数器
- redis作为注册中心的优点,和zk的区别
- 缓存更新,缓存穿透,缓存雪崩
- MQ,activeMQ,kafka相关
五、Spring框架相关
- ioc实现原理
- aop具体实现,动态代理
- 工厂bean和bean工厂
- 反射使用
- 注解实现
六、分布式
- dubbo具体调用原理(消费者&服务者)
- 多注册中心的使用场景
- 负载均衡策略
- 注册中心的注册原理(zk/redis/nacos 注册中心,配置中心)
- 网关,配置中心,限流熔断,入伍治理
看完三件事❤️
如果你觉得这篇内容对你还蛮有帮助,我想邀请你帮我三个小忙:
- 点赞,转发,有你们的 『点赞和评论』,才是我创造的动力。
- 关注公众号 『 java烂猪皮 』,不定期分享原创知识。
- 同时可以期待后续文章ing
网友评论