变强日记7

主要内容

布隆过滤器
有序链表的合并

布隆过滤器

什么是布隆过滤器

布隆过滤器是一种概率型数据结构。布隆过滤器的基本结构就是一个bit数组和一些hash函数。

如图所示，比如插入“baidu”，首先通过对“baidu”使用三个hash函数，得到三个值，并将这三个值作为bit数组的下标，进行标记。这样我们就记录了“baidu”这个字符串的存在性。（只能说明它可能存在）

假如我们要判断“baidu”这个字符串是否存在，首先使用之前一样的三个hash函数，得到三个hash值，在到bit数组中查看这三个位置是否被标记。如果都被标记了，说明”baidu“可能存在;否则，说明一定不存在。

很重要的一点是，布隆过滤器能说明一定不存在，但不能说明一定存在。而且布隆过滤器是不能删除的，因为一些值所使用的bit位会重合。

布隆过滤器的用途

减少磁盘IO或者网络请求。比如我们在使用redis作为缓存的数据库的情况下，为了避免缓存穿透。我们就可以使用布隆过滤器，我们可以使用布隆过滤器存储那些有的数据。每次请求时，使用布隆过滤器判断是否有这个数据，通过布隆过滤器判断没有的数据，可以直接返回，而不需要取查数据库了。这样就可以避免缓存击穿。

什么是缓存击穿？
在使用了缓存的系统中，有些黑客会恶意构造一些不存在的数据，使得缓存每次都不命中，导致每次都需要取数据库中查询（验证）。使得缓存失去了它存在的意义。

有序链表的合并

题目：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解答：

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //合并后的链表的头，首先创建一个头，可以shi'de
        ListNode head = new ListNode(0); 
        ListNode cur=head;
        ListNode curA=list1;
        ListNode curB=list2;
        while (curA!=null&&curB!=null){
            if(curA.val<=curB.val){
                cur.next=curA;
               curA=curA.next;
            }else {
                cur.next=curB;
                curB=curB.next;
            }
            cur=cur.next;
        }
        //处理剩下的节点，下面两个while循环只会执行一个
        while (curA!=null){
            cur.next=curA;
            cur=cur.next;
            curA=curA.next;
        }
        while (curB!=null){
            cur.next=curB;
            cur=cur.next;
            curB=curB.next;
        }
        //舍弃刚才为了方便创建的头节点
        return head.next;

    }
}

图解：

还是画图来得直接