资讯专栏INFORMATION COLUMN

bloomfilter的简单实现

马龙驹 / 2206人阅读

摘要:一般情况下不能从布隆过滤器中删除元素实现哈希算法在年发布了一个新的散列函数。能够迅速走红得益于其出色的速度和统计特性。比如哈希函数个数取,位数组大小设为字符串个数的倍时,发生的概率是。

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的,可以用于检索一个元素是否在一个集合中。

原理

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。

优点

运行快速,内存占用小。一般方法是将集合中所有元素保存起来,然后通过比较确定。链表、树、哈希表等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢。

缺点

随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

一般情况下不能从布隆过滤器中删除元素.

实现
public class BloomFilter {
    private final int size;
    private final int hashCount;
    private final BitSet bitSet;

    public BloomFilter(int size, int hashCount) {
        this.size = size;
        this.hashCount = hashCount;
        bitSet = new BitSet(size);
    }

    public void add(String key) {
        for (int seed = 1; seed <= hashCount; seed++) {
            int hash = Hashing.murmur3_32(seed).hashBytes(key.getBytes()).asInt();
            int index = Math.abs(hash) % size;
            bitSet.set(index);
        }
    }

    public boolean lookup(String key) {
        for (int seed = 1; seed <= hashCount; seed++) {
            int hash = Hashing.murmur3_32(seed).hashBytes(key.getBytes()).asInt();
            int index = Math.abs(hash) % size;
            if (!bitSet.get(index)) return false;
        }
        return true;
    }
}
murmur哈希算法

Austin Appleby在2008年发布了一个新的散列函数——MurmurHash。其最新版本大约是lookup3速度的2倍(大约为1 byte/cycle),它有32位和64位两个版本。32位版本只使用32位数学函数并给出一个32位的哈希值,而64位版本使用了64位的数学函数,并给出64位哈希值。根据Austin的分析,MurmurHash具有优异的性能,虽然Bob Jenkins 在《Dr. Dobbs article》杂志上声称“我预测MurmurHash比起lookup3要弱,但是我不知道具体值,因为我还没测试过它”。MurmurHash能够迅速走红得益于其出色的速度和统计特性。

guava自带的Murmur3_32HashFunction:

final class Murmur3_32HashFunction extends AbstractStreamingHashFunction implements Serializable {
  private static final int C1 = 0xcc9e2d51;
  private static final int C2 = 0x1b873593;

  private final int seed;

  Murmur3_32HashFunction(int seed) {
    this.seed = seed;
  }

  @Override
  public int bits() {
    return 32;
  }

  @Override
  public Hasher newHasher() {
    return new Murmur3_32Hasher(seed);
  }

  @Override
  public String toString() {
    return "Hashing.murmur3_32(" + seed + ")";
  }

  @Override
  public boolean equals(@Nullable Object object) {
    if (object instanceof Murmur3_32HashFunction) {
      Murmur3_32HashFunction other = (Murmur3_32HashFunction) object;
      return seed == other.seed;
    }
    return false;
  }

  @Override
  public int hashCode() {
    return getClass().hashCode() ^ seed;
  }

  @Override
  public HashCode hashInt(int input) {
    int k1 = mixK1(input);
    int h1 = mixH1(seed, k1);

    return fmix(h1, Ints.BYTES);
  }

  @Override
  public HashCode hashLong(long input) {
    int low = (int) input;
    int high = (int) (input >>> 32);

    int k1 = mixK1(low);
    int h1 = mixH1(seed, k1);

    k1 = mixK1(high);
    h1 = mixH1(h1, k1);

    return fmix(h1, Longs.BYTES);
  }

  // TODO(kak): Maybe implement #hashBytes instead?
  @Override
  public HashCode hashUnencodedChars(CharSequence input) {
    int h1 = seed;

    // step through the CharSequence 2 chars at a time
    for (int i = 1; i < input.length(); i += 2) {
      int k1 = input.charAt(i - 1) | (input.charAt(i) << 16);
      k1 = mixK1(k1);
      h1 = mixH1(h1, k1);
    }

    // deal with any remaining characters
    if ((input.length() & 1) == 1) {
      int k1 = input.charAt(input.length() - 1);
      k1 = mixK1(k1);
      h1 ^= k1;
    }

    return fmix(h1, Chars.BYTES * input.length());
  }

  private static int mixK1(int k1) {
    k1 *= C1;
    k1 = Integer.rotateLeft(k1, 15);
    k1 *= C2;
    return k1;
  }

  private static int mixH1(int h1, int k1) {
    h1 ^= k1;
    h1 = Integer.rotateLeft(h1, 13);
    h1 = h1 * 5 + 0xe6546b64;
    return h1;
  }

  // Finalization mix - force all bits of a hash block to avalanche
  private static HashCode fmix(int h1, int length) {
    h1 ^= length;
    h1 ^= h1 >>> 16;
    h1 *= 0x85ebca6b;
    h1 ^= h1 >>> 13;
    h1 *= 0xc2b2ae35;
    h1 ^= h1 >>> 16;
    return HashCode.fromInt(h1);
  }

  private static final class Murmur3_32Hasher extends AbstractStreamingHasher {
    private static final int CHUNK_SIZE = 4;
    private int h1;
    private int length;

    Murmur3_32Hasher(int seed) {
      super(CHUNK_SIZE);
      this.h1 = seed;
      this.length = 0;
    }

    @Override
    protected void process(ByteBuffer bb) {
      int k1 = Murmur3_32HashFunction.mixK1(bb.getInt());
      h1 = Murmur3_32HashFunction.mixH1(h1, k1);
      length += CHUNK_SIZE;
    }

    @Override
    protected void processRemaining(ByteBuffer bb) {
      length += bb.remaining();
      int k1 = 0;
      for (int i = 0; bb.hasRemaining(); i += 8) {
        k1 ^= toInt(bb.get()) << i;
      }
      h1 ^= Murmur3_32HashFunction.mixK1(k1);
    }

    @Override
    public HashCode makeHash() {
      return Murmur3_32HashFunction.fmix(h1, length);
    }
  }

  private static final long serialVersionUID = 0L;
}
关于参数值

哈希函数个数k、位数组大小m、加入的字符串数量n的关系:对于给定的m、n,当 k = ln(2)* m/n 时出错的概率是最小的。比如哈希函数个数k取10,位数组大小m设为字符串个数n的20倍时,false positive发生的概率是0.0000889。
guava提供的BloomFilter则直接提供了false positive的参数给你配置。

public static  BloomFilter create(Funnel funnel, long expectedInsertions) {
    return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
  }
doc

BloomFilter——大规模数据处理利器

Bloom Filters by Example

Guava教程-BloomFilter

Hash 函数概览

陌生但默默一统江湖的MurmurHash

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67569.html

相关文章

  • 说一说布隆过滤器

    摘要:介绍布隆过滤器在上的介绍布隆过滤器是年由布隆提出的。通过介绍已经知晓布隆过滤器的作用是检索一个元素是否在集合中。控制布隆过滤器的误判率如果集合的大小相比于输入对象的个数过小,失误率就会变高。 介绍 布隆过滤器在wiki上的介绍: 布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集...

    terasum 评论0 收藏0
  • 基于RedisBloomFilter实现

    摘要:再来看怎么结合一起使用根据给定的布隆过滤器添加值不能为空根据给定的布隆过滤器判断值是否存在不能为空很简单,只有两个方法,往里面添加元素,检查元素是否在里面这里的客户端使用的是封装的,可以在我的项目中查看完整的使用代码。 前言 最近在研究布隆过滤器(如果不了解什么是布隆过滤器的,推荐看这篇如何判断一个元素在亿级数据中是否存在?了解),发现Guava提供了封装好的类,但是只能单机使用,一般...

    phodal 评论0 收藏0
  • [轮子系列]Google Guava之BloomFilter源码分析及基于Redis重构

    摘要:方法,即表示自动扩容,这个函数名是从中搬过来的。自动扩容最后,也是最重要的,其中用了布隆过滤器中计算型数组长度的方法,得到之后使用命令初始化一个全部为的位数组。 本文源地址:http://www.fullstackyang.com/...,转发请注明该地址或segmentfault地址,谢谢! 一、背景知识 在网上已经有很多关于布隆过滤器的介绍了,这里就不再赘述,下面简单地提炼几个要点...

    xiangchaobin 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<