2019-07-02

BSGS 算法

缘起

BSGS算法（拔山盖世是否或者北上广深算法）的全名是大小步算法（Baby Step Giant Step）目的是求满足如下同余方程中的t.
$$
x^t ≡ y(mod m)
$$

2019-06-30

替罪羊树洛谷 P3369 【模板】普通平衡树

缘起

平衡二叉树是为了解决二叉树退化为链表导致O(n) 查询复杂度而诞生的数据结构. 现在有一款平衡二叉树比较暴力，就是所谓的替罪羊树（scapegoat tree，下面简称SGT）（虽然其实我觉得这个名字叫的觉得不是很贴切，但是市面上都这么叫它）.

SGT最大的特点就是一旦失衡，就暴力重建，检查是否失衡就是在插入和删除节点的时候. 其他的和典型的BST没什么两样. 本文以洛谷 P3369 【模板】普通平衡树为板子，讲解一下这种数据结构。

2019-06-28

为什么尽量不要Override finalize方法

缘起

我们在java.lang.Object中的约莫10个方法中能看到 finalize方法的身影. 但是java官方并不推荐 Override此方法. 这是为什么呢?

2019-06-28

WeakHashMap 源码解读

缘起

【1】中我们介绍了弱引用的一种应用场景——ThreadLocal. 当时是为了解决内存泄漏问题而必须要使得ThreadLocalMap的key（ThreadLocal类型）是弱引用. 但是带来的问题就是ThreadLocalMap的value的内存泄漏问题. 解决办法就是在get、set的时候顺便清理一下key已经为null的Entry. 而本文介绍弱引用另一种应用场景——WeakHashMap. 它的key同样是弱引用. 对弱引用不清楚的同学可以参考【2】

2019-06-28