从头学数据结构和算法

补上长期欠缺的算法了,注意是算法,数据结构是工具

Posted by tomlao的博客 on June 22, 2020 本文字数:483 | 阅读量:

1. 数据结构

1.1 数组

课后思考1:前面我基于数组的原理引出 JVM 的标记清除垃圾回收算法的核心理念。我不知道你是否使用 Java 语言,理解 JVM,如果你熟悉,可以在评论区回顾下你理解的标记清除垃圾回收算法。

答:JVM标记清除算法:大多数主流虚拟机采用可达性分析算法来判断对象是否存活,在标记阶段,会遍历所有 GC ROOTS,将所有 GC ROOTS 可达的对象标记为存活。(可达:方法区里的常量和静态变量,栈空间的引用对象作为root起点,可以找到的关联对象形成gc roots链,也即可达)只有当标记工作完成后,清理工作才会开始。不足:1.效率问题。标记和清理效率都不高,但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。

课后思考2:前面我们讲到一维数组的内存寻址公式,那你可以思考一下,类比一下,二维数组的内存寻址公式是怎样的呢?

答:对于 m * n 的数组,a[i][j](i < m,j < n)的地址为:

address = base_address + ( i * n + j) * type_size