参照这篇文章

Java部分

谈谈Java的优势

  • 面向对象(相较于C的面向过程)
  • 核心类库丰富
  • 跨平台性,一次编写,到处运行
  • 内存管理。和上一部分都是依赖于Java虚拟机(JVM)程序员不需要去关心操作系统带来的差异,不需要关心内存分配与回收

JVM,JRE,JDK之间的关系

jre

Java文件执行过程

Java源码 —> 编译器 —> 字节码文件class —> 再JVM中解释 —> 机器可执行的二进制机器码 —> 程序运行

数据类型

基本数据和引用数据

基本有8种按占用内存分别为,byte(1),boolean(1),short(2),char(2),int(4),float(4),long(8),double(8)

type

访问权限

private

面向对象与面向过程的区别

面向过程:性能高,适用于单片机,嵌入式开发,Linux/unix,比较看重性能,缺点就是难维护,扩展与复用

面向对象:上面的反过来

面向过程强调一步步的过程实现,流程化的解决问题,面向对象是抽象的,只需要使用就可以,不需要关心是怎么去实现的

反射应用场景

  • 框架(spring通过xml装在bean)
  • jdbc

OSI模型

OSI

三次握手

确保双方的一个收发数据的能力

A发给B,B收到了,B知道了自己的的收数据能力和A的发数据能力是可以的

B发给A,A收到了,A知道了B的发数据与自己的收数据能力

而此时B还不知道自己的发件和A的收件能力,所以A还会给B再发送一次

总之就是AB都需要确保四点,我的发送,我的接收,他的发送,他的接收

为什么是4次挥手

3次只是标名我同意你关闭连接了,但还不确定是否还有剩余的数据需要发送

DNS解析过程

缓存 —> 本地hosts —> LDNS —> RDNS

  1. 首先去浏览器缓存中寻找,如果缓存中有,则解析停止
  2. 如果1没有则去操作系统本身去做域名解析,windows的路径(C:\Windows\System32\drivers\etc\hosts)
  3. 向本地域名解析器(LDNS)发起域名请求,在win中可以通过ipconfig/all 查询。LDNS一般保存了大部分的解析结果,缓存时间受到域名失效时间控制,LDNS负责了大部分的解析工作
  4. 如果还没有解析,转向根域名解析服务器(RDNS),它返回通用顶级域名解析服务器(gTDL)的地址(返回给LDNS)
  5. LDNS向返回的这个地址发请求
  6. 接受请求的gTLD查找并返回这个域名对应的Name Server的地址,这个Name Server就是网站注册的域名服务器
  7. Name Server根据映射关系表找到目标ip,返回给LDNS
  8. LDNS缓存这个域名和对应的ip
  9. LDNS把解析的结果返回给用户,用户根据TTL值缓存到本地系统缓存中,域名解析过程至此结束

CDN原理

内容分发网络(Content Delivery Network),通过网络发到最靠近用户的节点,访问的时候可以就近获取,加快访问速度,如同迅雷的种子链接

通过给源站添加CNAME别名,向源站发送请求,会通过dns解析访问CNAME域名,调用加速节点的域名

servlet声明周期

web容器加载servlet将其实例化,开始声明周期,执行init方法初始化,调用doService()方法,会根据请求去调用doGet或者doPost方法

init和destory只会调用一次

String为什么被final修饰

  • final表示不可被继承,如果在常量池创建,则不可被修改,可以直接拿来用
  • 这样也保证了线程安全,不可变对象不可以被写
  • 在创建的时候也缓存了hashcode,不需要重新计算。这也是hashmap键为何常使用String的原因,相比于其他对象更快

集合部分

Collection集合主要有List、Set和Queue接口

聊聊List

Java的一个接口,常见的实现类有ArrayList和LinkedList,开发中常用的时ArrayList,底层结构是数组,另一个是链表

直接用数组不行?为什么要有arraylist

数组需要指定大小,而al可以进行动态扩容。在每次添加元素的时候都会判断空间是否足够

怎么进行扩容

其中有个grow方法,每一次扩之前的1.5倍,扩完会利用arraycopy进行拷贝

为什么日常使用不用linked而是array

由底层的数据结构决定,平时遍历比增删元素要多,而且al增删也进行过优化,在尾部增删的化时间复杂度在O(1),速度也不会比linekd慢

了解vector吗

线程安全,但不怎么使用了,扩容为之前的两倍。为什么不用?缺点是效率低,而且有好的替代品copyonwritearraylist

说说CopyOnWriteArrayList

文件在进行操作的时候,不直接在上面的基础上修改,而是重新找个位置修改,好处就是可以保证数据完整性,挂掉可以瞬间恢复。

cow是一个线程安全的list,底层通过赋值数组的方式实现。简述add方法,执行的时候会使用lock上锁,复制一个新的数组,在新数组中add元素,最后将array指向新数组。缺点就是耗费内存,每次add都会申请一块内存,只能保证数据最终一致性,而不能保证实时一致性

ArrayList

底层由数组实现,默认容量10,以无参方式构造时,赋值的是一个空数组,在添加元素的时候才会为其扩容,即扩为10,如果容量不够,则会触发grow()进行扩容,grow是扩容的核心方法,将新容量扩为之前的1.5倍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private void grow(int minCapacity) {
// oldCapacity为旧容量,newCapacity为新容量
int oldCapacity = elementData.length;
//将oldCapacity 右移一位,其效果相当于oldCapacity /2,
//我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE,
//如果minCapacity大于最大容量,则新容量则为`Integer.MAX_VALUE`,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法,以减少增量重新分配的次数。

1
2
3
4
5
6
7
8
9
10
11
12
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA({}))
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY(10);

if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

常用的add方法

1
2
3
4
5
6
7
8
//添加一个特定的元素到list的末尾
public boolean add(E e) {
//先确保elementData数组的长度足够,size是数组中数据的个数,因为要添加一个元素,所以size+1,先判断size+1的这个个数数组能否放得下,在这个方法中去判断数组长度是否够用
ensureCapacityInternal(size + 1); // Increments modCount!!
//在数据中正确的位置上放上元素e,并且size++
elementData[size++] = e;
return true;
}

根据索引删除元素

会把指定下标到数组末尾的元素挨个向前移动一个单位,并且会把数组最后一个元素设置为null,这样是为了方便之后将整个数组不被使用时,会被GC,可以作为小的技巧使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//根据索引删除指定位置的元素
public E remove(int index) {
//检查index的合理性
rangeCheck(index);
//这个作用很多,比如用来检测快速失败的一种标志。
modCount++;
//通过索引直接找到该元素
E oldValue = elementData(index);

//计算要移动的位数。
int numMoved = size - index - 1;
if (numMoved > 0)
//移动元素,挨个往前移一位。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将--size上的位置赋值为null,让gc(垃圾回收机制)更快的回收它。
elementData[--size] = null; // clear to let GC do its work
//返回删除的元素。
return oldValue;
}

什么是集合快速失败“fail-fast”?

多线程操作,在用增强for循环,其实就是集合的迭代器遍历时,如果同时进行遍历修改,就会抛出ConcurrentModificationException异常

原因:ArrayList的父类AbstarctList中有一个modCount变量,每次对集合进行修改时都会modCount++。ArrayList的Iterator中有一个expectedModCount变量,该变量会初始化和modCount相等,每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount的值和expectedmodCount的值是否相等,如果集合进行增删操作,modCount变量就会改变,就会造成expectedModCount!=modCount,此时就会抛出ConcurrentModificationException异常

解决方式

  • 使用普通for循环
  • 加锁synchronized
  • 使用CopyOnWriteArrayList

HashSet如何检查重复元素?如何保证数据是不可重复的?

add()添加时,不仅比较hash值,还会使用equlas比较,HashSet的add()会调用HashMap的put()

底层就是利用HashMap实现的,在添加相同的key时会覆盖原有的value值,返回原有的value值,所以不会重复

部分源码

1
2
3
4
5
6
7
8
9
10
11
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;

public HashSet() {
map = new HashMap<>();
}

public boolean add(E e) {
// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
return map.put(e, PRESENT)==null;
}

HashSet和HashMap的区别

  • map实现Map接口,set实现Set接口
  • map存储k,v,set存储对象
  • map使用put,set使用add()
  • map使用key计算hashcode,对于set的对象需要判断hashcode是否相同,如果相同还需判断equlas是否相同
  • map比set获取值的速度要快

谈谈Map

HashMap由数组 + 链表 / 红黑树组成
LinkedHashMap = 数组 + 链表 + 双向链表
TreeMap底层是红黑树
ConcurrentHashMap同HashMap

new一个HashMap的时候发生了什么

默认大小为16,加载因子为0.75。HashMap大小只能是2次幂(tableSzieFor)。当放入一个元素的时候需要算出

为什么是线程不安全的

1.7。在临界点将要扩容的时候,都会进行reseize和rehash操作,而rehash在并发的情况下可能形成闭环,造成死循环的问题,这是put引发的,导致cpu利用率接近100%,所以在并发情况下不能使用hashmap。使用的entry数组,包括key,value,hash,next

一些名词

哈希冲突:当key的hash值对数组大小取模后,如果值相同,那么就是哈希冲突,将会形成一条entry链

加载因子:为了减少哈希冲突,官方设定了一个值为0.75,当键值对达到总容量的75%时,则进行扩容。可以空间换时间,将加载因子手动调低

与hashTable和treeMap的区别

hashTable键值不能为null,treeMap同样是,而hashMap可以,但键只能有一个null

除了treeMap另外两个都是无序的,所以tree会效率低一点

HashMap

基于哈希散列实现,调用put添加元素时,调用对象的hashcode方法计算hash值,找到相应的bucket位置。get获取元素时,通过键对象的equals方法找到正确的键值对,找到返回对象。hashMap使用链表来解决冲突,当发生冲突时,对象会储存在链表的头节点中。1.7之前采取头插的方式,扩容会改变元素原本的顺序,在并发场景下会导致链的问题,1.8尾插就不会出现这个问题了

允许由null值作为key只能有一个。初始化大小为16,扩容变为原来的2的幂次方大小。如何保证有参构造都是2的幂次tableSizeFor方法,可以保证返回的值为大于=n的2的幂次方的数

1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= 1 << 30) ? 1 << 30 : n + 1;
}

HashMap的put过程

首先计算key的hash值,调用hash(),实际上是key.hashCode() ^ key.hashCode() >>> 16,高位补0。

计算下标为index = (table.length - 1) & hash

put

相关源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//实现Map.put和相关方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤①:tab为空则创建
// table未初始化或者长度为0,进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②:计算index,并对null做处理
// (n - 1) & hash 确定元素存放在哪个桶中,桶为空,新生成结点放入桶中(此时,这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素
else {
Node<K,V> e; K k;
// 步骤③:节点key存在,直接覆盖value
// 比较桶中第一个元素(数组中的结点)的hash值相等,key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e,用e来记录
e = p;
// 步骤④:判断该链为红黑树
// hash值不相等,即key不相等;为红黑树结点
// 如果当前元素类型为TreeNode,表示为红黑树,putTreeVal返回待存放的node, e可能为null
else if (p instanceof TreeNode)
// 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤⑤:该链为链表
// 为链表结点
else {
// 在链表最末插入结点
for (int binCount = 0; ; ++binCount) {
// 到达链表的尾部

//判断该链表尾部指针是不是空的
if ((e = p.next) == null) {
// 在尾部插入新结点
p.next = newNode(hash, key, value, null);
//判断链表的长度是否达到转化红黑树的临界值,临界值为8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//链表结构转树形结构
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等,跳出循环
break;
// 用于遍历桶中的链表,与前面的e = p.next组合,可以遍历链表
p = e;
}
}
//判断当前的key已经存在的情况下,再来一个相同的hash值、key值时,返回新来的value这个值
if (e != null) {
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性修改
++modCount;
// 步骤⑥:超过最大容量就扩容
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}

源码翻译

  1. 判断键值对数组table[i]是否为空或为null,是的话执行resize()进行扩容;
  2. 根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向6,如果table[i]不为空,转向3;
  3. 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向4,这里的相同指的是hashCode以及equals;
  4. 判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向5;
  5. 遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
  6. 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

为什么用异或计算hash

得到的值更加均匀

个人观点:补充一些,hashcode为int类型,4个字节32位,为了确保散列性,肯定是32位都能进行散列算法计算是最好的。 首先要明白,为什么用亦或计算,二进制位计算,a 只可能为0,1,b只可能为0,1。a中0出现几率为1/2,1也是1/2,b同理。 位运算符有三种,|,&,……,或,与,亦或。 a,b进行位运算,有4种可能 00,01,10,11 a或b计算 结果为1的几率为3/4,0的几率为1/4 a与b计算 结果为0的几率为3/4,1的几率为1/4, a亦或b计算 结果为1的几率为1/2,0的几率为1/2 所以,进行亦或计算,得到的结果肯定更为平均,不会偏向0或者偏向1,更为散列。 右移16位进行亦或计算,我将其拆分为两部分,前16位的亦或运算,和后16位的亦或运算, 后16位的亦或运算,即原hashcode后16位与原hashcode前16位进行亦或计算,得出的结果,前16位和后16位都有参与其中,保证了 32位全部进行计算。 前16位的亦或运算,即原hasecode前16位与0000 0000 0000 0000进行亦或计算,结果只与前16位hashcode有关,同时亦或计算,保证 结果为0的几率为1/2,1的几率为1/2,也是平均的。 所以为什么是右移16位,个人觉得博主说的原因是一部分, 也有一个原因是右移16位进行亦或计算的结果中, (1)结果的后16位保证了hashcode32位全部参与计算,也保证了0,1平均,散列性 (2)结果的前16位保证hashcode前16位了0,1平均散列性,附带hashcode前16位参与计算。 (3) 16与16位数相同,利于计算,不需要补齐,移去位数数据 更多情况,hashmap只会用到前16位(临时数据一般不会这么大),所以(1)占主因

如何散列

直接进行hash取余操作,可能导致散列不均匀的情况(参与运算的只有hashcode的低位),最坏情况会形成一个单链表。所以对hashCode做了一定的优化,让高位也参与运算,使其更加平均,减少哈希碰撞,这样的操作叫做扰动

1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或)
}

这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动);

解决hash冲突

1.8之前,如果有冲突将值加入链表中,又叫拉链法

1.8之后,链表长度大于8,调用treeifyBin方法,会判断hashmap数组长度是否大于等于64,如果是则转为红黑树,以减少搜索时间,否则执行resize方法扩容

扩容条件

大于容量*扩容因子(默认0.75f),loadFactor 越大数组越密,越少越稀疏。0.75是官方给出的一个比较好的临界值。threshold = capacity \* loadFactor,用来衡量是否需要扩容

扩容怎么实现的

  1. 在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容;
  2. 每次扩展的时候,新容量为旧容量的2倍;
  3. 扩展后元素的位置要么在原位置,要么移动到原位置 + 旧容量的位置;

在putVal()中使用到了2次resize()方法,resize()方法在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其临界值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+旧容量的位置

resize源码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//如果oldCap不为空的话,就是hash桶数组不为空
if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了,就赋值为整数最大的阀值
threshold = Integer.MAX_VALUE;
return oldTab;//返回
}//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold
}
// 旧的容量为0,但threshold大于零,代表有参构造有cap传入,threshold已经被初始化成最小2的n次幂
// 直接将该值赋给新的容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 无参构造创建的map,给出默认容量和threshold 16, 16*0.75
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新的threshold = 新的cap * 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;
// 计算出新的数组长度后赋给当前成员变量table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
table = newTab;//将新数组的值复制给旧的hash桶数组
// 如果原先的数组没有初始化,那么resize的初始化工作到此结束,否则进入扩容元素重排逻辑,使其均匀的分散
if (oldTab != null) {
// 遍历新数组的所有桶下标
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 旧数组的桶下标赋给临时变量e,并且解除旧数组中的引用,否则就数组无法被GC回收
oldTab[j] = null;
// 如果e.next==null,代表桶中就一个元素,不存在链表或者红黑树
if (e.next == null)
// 用同样的hash映射算法把该元素加入新的数组
newTab[e.hash & (newCap - 1)] = e;
// 如果e是TreeNode并且e.next!=null,那么处理树中元素的重排
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// e是链表的头并且e.next!=null,那么处理链表中元素重排
else { // preserve order
// loHead,loTail 代表扩容后不用变换下标,见注1
Node<K,V> loHead = null, loTail = null;
// hiHead,hiTail 代表扩容后变换下标,见注1
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历链表
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
// 初始化head指向链表当前元素e,e不一定是链表的第一个元素,初始化后loHead
// 代表下标保持不变的链表的头元素
loHead = e;
else
// loTail.next指向当前e
loTail.next = e;
// loTail指向当前的元素e
// 初始化后,loTail和loHead指向相同的内存,所以当loTail.next指向下一个元素时,
// 底层数组中的元素的next引用也相应发生变化,造成lowHead.next.next.....
// 跟随loTail同步,使得lowHead可以链接到所有属于该链表的元素。
loTail = e;
}
else {
if (hiTail == null)
// 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 遍历结束, 将tail指向null,并把链表头放入新数组的相应下标,形成新的映射。
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

底层实现

1.8之前

数组+链表也就是链表散列,链表用来解决hash冲突,在并发条件下rehash会造成元素之间形成一个循环链表 ,头插。通过key的扰动函数(hash处理hash值),目的是为了减少碰撞,1.8之前扰动4次,性能比1.8稍差

1.8之后

数组+链表/红黑树。当链表长度大于8且当前数组长度大于64,则将链表转为红黑树存储,减少搜索时间。否则先进行扩容。

rehash

hash表在数据插入的时候都会检查有没有超过给定容量,若超过,需要进行扩容,整个hash表的元素都需要重算一遍,这个就叫rehash,成本非常大

ConcurrentHashMap

1.7底层使用segment数组 + hashmap数组 + 链表

Java7 中 ConcurrentHashMap 使用的分段锁,也就是每一个 Segment 上同时只有一个线程可以操作,每一个 Segment 都是一个类似 HashMap 数组的结构,它可以扩容,它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。

map7

1.8与hashmap一样,node数组 + 链表 / 红黑树

Java8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树,Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树,在冲突小于一定数量时又退回链表。

谈谈NIO

同步非阻塞。由三部分组成:buffer(缓冲区),channel(通道),selector(选择器)

  • buffer:存储数据的地方
  • channel:运输数据的载体
  • selector:检查channel变更状态

谈谈反射

运行期读取类的信息

谈谈CAS

compare and swap 比较并交换,是一个原子性操作

如何操作?有三个操作数,当前值A,内存值V,要修改的值B。假设A == V,将V改为B。如果A != V要么重试,要么放弃

为什么要用CAS?synchronized每次仅允许一个线程去操作共享资源,CAS相当于没有加锁,多个线程都可以操作资源,在实际修改的时候再去判断,所以要比synchronized高效

CAS的缺点?带来ABA的问题,假设线程A读到的值为10,B为修改为了20,C又修改为了10,在A来说,与内存中的值是一致的,认为没有变过,但实际是变过的。这就是ABA问题。通常使用内存值 + 版本号的方式去解决

谈谈synchronized

互斥锁,每次只能允许一个线程访问共享资源

修饰的是方法 / 代码块,锁的是对象实例

修饰的静态方法,锁的类实例

原理?通过反编译会生成ACC_SYNCRONIZED关键字来标识。修饰代码块会依赖monitorenter和monitorexit指令

对象由三部分组成:对象头、实际数据、对齐填充。重点在于对象头,分为几部分,重点是mark word信息会记录锁的信息。每个对象对应一个monitor对象,持有当前锁的线程和等待的线程队列

在1.6之前是重量级锁,来了就阻塞别的线程。之后进行了锁升级。引入了偏向锁和轻量级锁,在JVM层面加锁,不依赖操作系统,没有切换的消耗

如果没有竞争的线程会加一个偏向锁,在mark word直接记录线程ID,如果有线程来执行代码了,会比较id,如果相同则执行代码,不同CAS修改,如果CAS失败说明有别的线程在竞争,此时会撤销偏向锁,升级为轻量级锁。在轻量级锁状态下,当前线程栈帧插件Lock Record把mork word信息拷贝进去,并用owner指针指向加锁对象,线程执行代码时,使用CAS试图将mark word指向到线程栈帧的lock record,假设CAS成功,获得轻量级锁,失败自旋重试,重试一定次数后升级为重量级锁

偏向锁—只有一个线程进入临界区
轻量级锁—多个线程交替进程临界区
重量级锁—多个线程进入临界区

谈谈AQS

全称叫做AbstractQueuedSyncronizer,实现锁的一个框架,内部实现关键在于维护了一个先进先出的队列与state状态变量

为什么匿名内部类要用final常量

生命周期不一致,局部变量存于栈中,当方法执行结束后,非final被销毁,而局部内部类的引用还存在,此时内部类在调用的时候就会出错,加了final,确保内部类和外部类使用分开,避免了此问题

BIO,NIO,AIO的区别

简答

BIO:Block IO 同步阻塞式 IO,就是我们平常使用的传统 IO,它的特点是模式简单使用方便,并发处理能力低。
NIO:Non IO 同步非阻塞 IO,是传统 IO 的升级,客户端和服务器端通过 Channel(通道)通讯,实现了多路复用。
AIO:Asynchronous IO 是 NIO 的升级,也叫 NIO2,实现了异步非堵塞 IO ,异步 IO 的操作基于事件和回调机制。
详细回答

BIO (Blocking I/O): 同步阻塞I/O模式,数据的读取写入必须阻塞在一个线程内等待其完成。在活动连接数不是特别高(小于单机1000)的情况下,这种模型是比较不错的,可以让每一个连接专注于自己的 I/O 并且编程模型简单,也不用过多考虑系统的过载、限流等问题。线程池本身就是一个天然的漏斗,可以缓冲一些系统处理不了的连接或请求。但是,当面对十万甚至百万级连接的时候,传统的 BIO 模型是无能为力的。因此,我们需要一种更高效的 I/O 处理模型来应对更高的并发量。
NIO (New I/O): 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 的非阻塞模式来开发
AIO (Asynchronous I/O): AIO 也就是 NIO 2。在 Java 7 中引入了 NIO 的改进版 NIO 2,它是异步非阻塞的IO模型。异步 IO 是基于事件和回调机制实现的,也就是应用操作之后会直接返回,不会堵塞在那里,当后台处理完成,操作系统会通知相应的线程进行后续的操作。AIO 是异步IO的缩写,虽然 NIO 在网络操作中,提供了非阻塞的方法,但是 NIO 的 IO 行为还是同步的。对于 NIO 来说,我们的业务线程是在 IO 操作准备好时,得到通知,接着就由这个线程自行进行 IO 操作,IO操作本身是同步的。查阅网上相关资料,我发现就目前来说 AIO 的应用还不是很广泛,Netty 之前也尝试使用过 AIO,不过又放弃了。

ArrayList 和 LinkedList 的区别?

  • A是动态数组数据结构进行实现,L是双向链表的方式实现
  • A的查询效率高,插入删除低,L次之
  • L更占内存,除了存数据还存向前向后的引用
  • 都是线程不安全的

如何设计一个秒杀系统

秒杀系统就是一个“三高”系统,即高并发、高性能和高可用的分布式系统
秒杀设计原则:前台请求尽量少,后台数据尽量少,调用链路尽量短,尽量不要有单点
秒杀高并发方法:访问拦截、分流、动静分离
秒杀数据方法:减库存策略、热点、异步、限流降级
访问拦截主要思路:通过CDN和缓存技术,尽量把访问拦截在离用户更近的层,尽可能地过滤掉无效请求。
分流主要思路:通过分布式集群技术,多台机器处理,提高并发能力。

Java内存模型

JVM是一种内存分区,Java内存模式是一种虚拟机规范

Java memory model,用于屏蔽掉各种硬件与操作系统内存的访问差异,让Java可以在各种平台下达到一致的并发效果。

JMM规范了JVM与计算机内存是如何协同工作的:规定了一个线程如何看到共享变量的值,以及如何同步的访问共享变量

JMM内存模型从1.5重新修订,1.8仍然在使用

JMM1
JMM2

扩展

更多内容可点击参照这篇文章

集合相关文章