布隆过滤器 跳表

布隆过滤器 跳表

 哈希表的缺点就是在于占用的空间内存比较多 ：

举个例子：有可能存储2个元素 最后哈希表使用了十个数组空间的大小

因为它是为了减少哈希冲突而把空间搞大一点

但是时间复杂度较低

———————————————————————————————————————————

 

 

查询元素是否存在：

第一条：如果有一个位置哈希函数生成索引位置对应的值是不为1的 那么这个元素肯定不存在

第二条：因为有可能这个索引位置对应的值：这个1不一定是同一个元素生成的

有可能是A 生成的1  后来B也指向这里，，，，，

布隆过滤器一般用在数据规模特别大的地方  公式等价于下面 

 

 一般吧实现删除 特别的麻烦 为了实现查询的高效 我们不实现删除

如果要删除A 我们把所指向索引处的值改为0 但是有可能别的元素也可能在利用指向这个地方

因此我们不易删除

 细节语法：Java当中的语法问题 ln2

一个亿怎么表示？

 

bitSize表示要装的比特位数 但是这样计算可能不太准确

我们常用的公式：

 我们知道数据量：n，并且知道每一页所要显示的数据量 ：pageSize

那么我们可以通过这个算出需要多少页：pageCount=(n+pageSize-1)/pageSize

代码： 省略______

 

跳表：

 由于我们的链表和数组不一样  它不可以随机直接跳转到指定位置去

 因为红黑树实现起来真的是太难了。。。。

在链表的基础上，增加了跳跃的功能。每间隔一个 ，跳跃一个

越上面的路线它是走的越快的

如图：(doge）

查找18是否存在的过程如图：：：-------------------------------------------------------

1.先从最高处进行查找，发现21大于18 那么就退回上一步

2.从上一步的下一层开始找 以此类推的找即可

3.最好发现找到地下了 还是找不到 所以18不存在，，，，，

 ——————————————————————————————————————————

Node[ ] nexts;表示是一个节点数组

first.nexts[ ]表示指向节点

 

 添加删除

删除：

添加：

源码如下：

package 数据结构与算法.图.跳表;

public class SkipList {
    private static final int Max_value=32;
    private static final double P=0.25;
    private int size;
    private Comparable comparactor;
    
    public SkipList() {
        this(null);
    }
    
    private Node first;
    public SkipList(Comparable comparactor) {
        this.comparactor = comparactor;
        
        first=new Node<>(null,null,Max_value);
        
        first.nexts=new Node[Max_value];
    }

    
    private int level;
    private int size(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }

    
    private int randomlevel(int level){
        while (Math.random() node=first;
        Node[] prevs=new Node[level];
        for (int i =level-1; i>=0 ; i++) {
            int cmp=-1;
            while (node.nexts!=null&&(cmp=comparable(key,node.nexts[i].key))>0){
                node=node.nexts[i];
            }
            
            if(cmp==0){
                V oldvalue=node.nexts[i].value;
                node.nexts[i].value=value;
                return oldvalue;//返回旧节点的value
            }
            
            prevs[i]=node;
        }
        //添加新节点随机生成的高度
        int newnodelevel=randomlevel(level);
        Node newnode=new Node<>(key,value,newnodelevel);
        for (int i = 0; i =level){
                //更新前驱
                first.nexts[i]=newnode;
                //后继默认是空的 因此可省略 newnode.nexts[i]=null
            } else {
                //更新前驱
                newnode.nexts[i]=prevs[i].nexts[i];
                //更新后继
                prevs[i].nexts[i]=newnode;
            }
        }
        size++;
        
        level=Math.max(level,newnodelevel);
        return null;
    }

    
    public V get(K key){
       checkNull(key);
       Node node=first;
        for (int i =level-1; i>=0 ; i++) {
            int cmp=-1;
            while (node.nexts[i]!=null&&(cmp=comparable(key,node.nexts[i].key))>0){
                node=node.nexts[i];
            }
            if(cmp==0){
                return node.nexts[i].value;
            }
        }
        return null;
    }

    
    //返回的是要删除节点的value值
    public V remove(K key){
        checkNull(key);
        Node node=first;
        Node[] prevs=new Node[level];
        boolean falg=false;
        for (int i =level-1; i>=0;i--) {
            int cmp=-1;
            while (((cmp=comparable(key,node.nexts[i].key))>0)&&node.nexts[i]!=null){
                node=node.nexts[i];
            }
            prevs[i]=node;
            
            if(cmp==0){
                falg=true;
            }
        }
        
        if(!falg){
            return null;
        }
        //需要被删除的节点至少存在第一层
        Node removenode=node.nexts[0];
        //更改后继
        for (int i = 0; i =0&&first.nexts[level]==null){
            level=newlevel;
        }
        return removenode.value;
    }
    private void checkNull(K key){
        if(key==null){
            throw new IllegalArgumentException("that not null");
        }
    }
    public int comparable(K k1,K k2){
        return comparactor!=null?comparable(k1,k2)
                :((Comparable)k1).compareTo(k2);
    }
    private static class Node{
        
        K key;
        V value;
        
        Node[] nexts;
        
        public Node(K key,V value,int level){
            this.key=key;
            this.value=value;
            Node[] nexts=new Node[level];//这一句话等价于nexts=new Node[level];
        }
    }
}