继续,第五波女朋友面试4个月的面试题复盘,这次是关于Java基础的题目。
作为Java程序员,Java基础应该是最需要掌握的的基本功,今天一起来看看常问的题目吧。
还是老套路,高频的面试题已经标星,有面试需要的同学可以先点星星收藏起来。
下面开始复盘题目
基础数据结构
- HashMap原理
HashMap本身是一个key,value存储容器,Jdk1.7之前使用数据+单链表两种数据结构实现hash存储,由于防止单个hash槽里的单链表过长,导致查询效率降低,jdk1.8将hashMap升级为数组+链表+红黑树来存储提升效率。针对容器的原理主要就是数据存储,查询,扩缩容的设计机制,HashMap也一样。实际工作中jdk8的使用应该比较多,我们以jdk8为例,来回答存,查,扩容机制并说明它的原理。
put函数分别有两个参数key,value
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
他的主线核心逻辑其实就两步
细节可以大致说下:
首先通过
hash函数
计算key的hash值
再判断hash数组是否为空,为空调用
resize函数
初始化
通过
&运算符
计算确定key的存储位置
p = tab[i = (n - 1) & hash]
判断存储位置是否hash冲突,不冲突,直接存入数据
newNode(hash, key, value, null)
如果发生了冲突,判断key是否重复,key重复判断依据:key的hash相同并且key值相同
(p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
如果是同一个key,则覆盖旧值。
如果不是同一个key,判断value是链表还是一棵红黑树。
如果是链表,遍历到链表尾部并插入新节点,也就是尾插法插入新key
。
如果是红黑树,使用前序遍历法搜索红黑树,如果找到了相同key,则替换旧值,否则插入树中
。
最后判断是否超过扩容的阀值,默认0.75,超过了就进行扩容操作。
get流程和put流程有相同的地方,都需要计算key的hash值和所在位置,然后到所在位置查找数据
根据key.hashCode计算数组位置
判断数组下标所在的第一个元素,根据hash值相等并且key相等equals也相等,则直接返回这个元素
如果不止一个元素,一个一个遍历元素
如果是树形,使用前序遍历搜索红黑树。
如果不是则遍历单链表查找。
其实HashMap设计的最精妙的地方就是扩容机制了。
扩容前先要计算新数组大小,扩容大小采用原数组大小的2倍
创建新数组后,需要进行原始数据迁移
遍历原始数组,如果数组下标位置有值,且只有一个元素,则将原始赋值给newTab[e.hash & (newCap - 1)] = e;
如果原数组下标的数据是一棵红黑树
如果数组下标是链表,要么是还是老位置,要么是老位置+老容量的位置上
精妙之处就在这里,由于是2倍扩容,并且map大小都是n次幂,他们的二进制有规律可循。
比如容量大小n由16扩容到32
16 = 0001
0000
15 = 0000
1111
32 = 001
0 0000
31 = 0001
1111
由于计算key的存储位置,等于(n-1)& key.hash
扩容一倍后,二进制形式的容量-1刚好左边多了一个1,记为位置n,多了位置n参与计算
与运算:相同位的两个数字都为1,则为1;若有一个不为1,则为0。
结合&运算的特征,只要判断k.hash的位置n是不是1,就可以确定出key在新数组的位置了。
如果是0, 相当于位置n不起作用,数据还是存在老位置上
`如果是1, 相当于位置n起作用,数据存储在老位置+老容量大小的位置上。
- 为什么重写了hashcode方法就要重写equals方法
对于对象集合的判重,如果一个集合含有10000个对象实例,仅仅使用equals()方法的话,那么对于一个对象判重就需要比较10000次,随着集合规模的增大,时间开销是很大的。但是同时使用哈希表的话,就能快速定位到对象的大概存储位置,并且在定位到大概存储位置后,后续比较过程中,如果两个对象的hashCode不相同,也不再需要调用equals()方法,从而大大减少了equals()比较次数。
比如上文提到hashmap扩容,hashmap中会缓存key的hash值,避免在扩容时进行再次计算,提升性能。
总体来就说是为了考虑性能提速。
对象复制
- 对象序列化作用
对象在Java应用中存储的字符,而我们一般涉及到系统之间数据交换,这个时候字符类型的数据,网络底层传输是不识别的,网络传输实际是比特流,在tcp协议层传输的是二进制流,因此需要一种序列化技术将我们理解的数据转换成网络协议层能之别的二进制流。
在Java原生的api中,主要是通过ObjectOutputStream
完成序列化和反序列化。
由于Java原生序列化技术效率不高,市面上出现了很多开源的序列化方案,常见的开源序列化方案有:
Hessian是一个支持跨语言传输的二进制序列化协议,相对于 Java 默认的序列化机制来说,Hessian 具有更好的性能和易用性,而且支持多种不同的语言。
google开发的开源的序列化方案protocol buffer(简称protobuf),它使用proto文件来描述数据结构,然后通过Google开发的ProtoBuf编译器生成Java代码,从而实现对数据的序列化和反序列化。
总结
Java基本功非常重要,所有的上层框架和中间件都是利用了Java基础构建起来的,上文提到的知识只是Java基础技术中的冰山一角,希望我们都可以保持不断学习,不断加强基础技能的理解和深入。