ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Java > bloom filter的一种实现

bloom filter的一种实现

原创 Java 作者：quickpoint 时间：2012-05-20 15:08:15 0 删除 编辑
/**
* quickpoint, jkltk2000 AT 126 DOT com.
* Copyright (c) 2012 All Rights Reserved.
* Code is licensed with BSD. See COPYRIGHT.BSD file.
*/
package com.quickpoint.bloomfilter;
/**
* BloomFilter
*
*

* 具体原理见: http://en.wikipedia.org/wiki/Bloom_filter
*

*
* @author kui.lijk
* @version $Id: BloomFilter.java, v 1.0 2012-5-19 kui.lijk Exp $
*/
public interface BloomFilter {
/**
* 增加字符串。
*
*
    *
  • 向过滤器中增加字符串，改变过滤器的内容
    • *
  • 如果字符串已经在过滤器中存在，则不增加。
    • *
    *
    * @param str 待增加的字符串
    */
    void add(String str);
    /**
    * 判断字符串是否在过滤器中。
    *
    *
      *
    • 如果字符串为null，返回不存在
      • *
    • 如果过滤器中内容表明不存在，则实际的存储中一定不存在
      • *
    • 如果过滤器中内容表明存在，则实际的存储中不一定是实际存在(false positive)
      • *
      *
      * @param str 待判断的字符串
      * @return true表示存在，false表示不存在。
      */
      boolean contains(String str);
      /**
      * 清除所有的标记位。
      */
      void clear();
      /**
      * 获取位图的大小。
      *
      * @return 位图大小
      */
      int size();
      /**
      * 获取过滤器中的字符串个数。
      *
      * @return 字符串实际个数
      */
      int count();
      /**
      * 获取位图的某位的实际值。
      *
      * @param index 位图中的位索引
      * @return true表示已经设置，false表示未设置。
      */
      boolean getBit(int index);
      }
      /**
      * quickpoint, jkltk2000 AT 126 DOT com.
      * Copyright (c) 2012 All Rights Reserved.
      * Code is licensed with BSD. See COPYRIGHT.BSD file.
      */
      package com.quickpoint.bloomfilter;
      import com.quickpoint.bloomfilter.hashfunc.HashFunction;
      /**
      * BloomFilter工厂。
      *
      *

      * 设计此工厂的目的是为了封装BloomFilter的创建过程。
      *

      *
      * @author kui.lijk
      * @version $Id: BloomFilterFactory.java, v 1.0 2012-5-19 kui.lijk Exp $
      */
      public interface BloomFilterFactory {
      /**
      * 创建BloomFilter。
      *
      *
        *
      • 固定大小的位图
        • *
      • 字符串字符大小写敏感
        • *
        *
        * @param size 位图的大小
        * @return BloomFilter
        */
        BloomFilter createFilter(int size);
        /**
        * 创建BloomFilter。
        *
        *
          *
        • 固定大小的位图
          • *
          *
          * @param size 位图的大小
          * @param caseSensitive true 字符大小写敏感，false 字符大小写不敏感
          * @return BloomFilter
          */
          BloomFilter createFilter(int size, boolean caseSensitive);
          /**
          * 增加哈希函数。
          *
          * @param hashFunc 哈希函数
          */
          void addHashFunction(HashFunction hashFunc);
          /**
          * 删除哈希函数。
          *
          * @param hashFunc 哈希函数
          */
          void removeHashFunction(HashFunction hashFunc);
          }
          /**
          * quickpoint, jkltk2000 AT 126 DOT com.
          * Copyright (c) 2012 All Rights Reserved.
          * Code is licensed with BSD. See COPYRIGHT.BSD file.
          */
          package com.quickpoint.bloomfilter.hashfunc;
          import java.io.Serializable;
          /**
          * 哈希函数
          *
          *

          * 定义了对于哈希函数的封装。
          *

          *
          * @author kui.lijk
          * @version $Id: HashFunction.java, v 1.0 2012-5-19 kui.lijk Exp $
          */
          public interface HashFunction extends Serializable {
          /**
          * 对内容进行哈希。
          *
          * @param content 待哈希的内容
          * @return 哈希结果，哈希值。
          */
          int hash(Object content);
          }
          /**
          * quickpoint, jkltk2000 AT 126 DOT com.
          * Copyright (c) 2012 All Rights Reserved.
          * Code is licensed with BSD. See COPYRIGHT.BSD file.
          */
          package com.quickpoint.bloomfilter;
          import java.util.BitSet;
          import com.quickpoint.bloomfilter.hashfunc.HashFunction;
          /**
          * 默认的BloomFilter实现。
          *
          * @author kui.lijk
          * @version $Id: DefaultBloomFilter.java, v 1.0 2012-5-19 kui.lijk Exp $
          */
          public class DefaultBloomFilter implements BloomFilter {
          /** 字符串个数 */
          private int count;
          /** 位图大小 */
          private int size;
          /** 位图 */
          private BitSet bits;
          /** 哈希函数 */
          private HashFunction[] hashFuncs;
          /** 是否字符串大小写敏感, 默认为敏感 */
          private boolean caseSensitive;
          /**
          * 创建大小写敏感的BloomFilter。
          *
          * @param size 位图大小
          * @param hashFuncs 哈希函数
          */
          public DefaultBloomFilter(int size, HashFunction[] hashFuncs) {
          // 大小写敏感
          this(size, hashFuncs, true);
          }
          /**
          * 创建BloomFilter。
          *
          * @param size 位图大小
          * @param hashFuncs 哈希函数
          * @param caseSensitive 字符串大小写敏感,true表示敏感，false表示不敏感
          */
          public DefaultBloomFilter(int size, HashFunction[] hashFuncs, boolean caseSensitive) {
          if (0 > size) {
          throw new IllegalArgumentException("illegal size:" + size);
          }
          if (null == hashFuncs || hashFuncs.length < 0) {
          throw new IllegalArgumentException("illegal functions.");
          }
          this.count = 0;
          this.size = size;
          this.bits = new BitSet(size);
          this.hashFuncs = hashFuncs;
          this.caseSensitive = caseSensitive;
          }
          /**
          * @see com.quickpoint.bloomfilter.hashfunc.BloomFilter#add(java.lang.String)
          */
          @Override
          public void add(String str) {
          if (null == str) {
          return;
          }
          if (contains(str)) {
          return;
          }
          for (HashFunction eachFunc : hashFuncs) {
          bits.set(eachFunc.hash(str), true);
          }
          count++;
          }
          /**
          * @see com.quickpoint.bloomfilter.hashfunc.BloomFilter#contains(java.lang.String)
          */
          @Override
          public boolean contains(String str) {
          if (null == str) {
          return false;
          }
          if (!caseSensitive) {
          str = str.toLowerCase();
          }
          for (HashFunction eachFunc : hashFuncs) {
          boolean exist = bits.get(eachFunc.hash(str));
          if (!exist) {
          return false;
          }
          }
          return true;
          }
          /**
          * @see com.quickpoint.bloomfilter.hashfunc.BloomFilter#clear()
          */
          @Override
          public void clear() {
          bits.clear();
          this.count = 0;
          }
          /**
          * @see com.quickpoint.bloomfilter.hashfunc.BloomFilter#size()
          */
          @Override
          public int size() {
          return size;
          }
          /**
          * @see com.quickpoint.bloomfilter.hashfunc.BloomFilter#count()
          */
          @Override
          public int count() {
          return count;
          }
          /**
          * @see com.quickpoint.bloomfilter.hashfunc.BloomFilter#getBit(int)
          */
          @Override
          public boolean getBit(int index) {
          if (index < 0 || index > size) {
          throw new IllegalArgumentException("index is out of scope, " + index);
          }
          return bits.get(index);
          }
          }
          /**
          * quickpoint, jkltk2000 AT 126 DOT com.
          * Copyright (c) 2012 All Rights Reserved.
          * Code is licensed with BSD. See COPYRIGHT.BSD file.
          */
          package com.quickpoint.bloomfilter;
          import java.util.HashSet;
          import java.util.Set;
          import com.quickpoint.bloomfilter.hashfunc.HashFunction;
          /**
          * 默认的BloomFilter工厂实现。
          *
          * @author kui.lijk
          * @version $Id: DefaultBloomFilterFactory.java, v 1.0 2012-5-19 kui.lijk Exp $
          */
          public class DefaultBloomFilterFactory implements BloomFilterFactory {
          /** 哈希函数 */
          private Set hashFuncs = new HashSet();
          public DefaultBloomFilterFactory() {
          }
          /**
          * @see com.quickpoint.bloomfilter.BloomFilterFactory#createFilter(int)
          */
          @Override
          public BloomFilter createFilter(int size) {
          return createFilter(size, true);
          }
          /**
          * @see com.quickpoint.bloomfilter.BloomFilterFactory#createFilter(boolean)
          */
          @Override
          public BloomFilter createFilter(int size, boolean caseSensitive) {
          return new DefaultBloomFilter(size, getHashFunctions(), caseSensitive);
          }
          /**
          * @see com.quickpoint.bloomfilter.BloomFilterFactory#addHashFunction(com.quickpoint.bloomfilter.hashfunc.HashFunction)
          */
          @Override
          public void addHashFunction(HashFunction hashFunc) {
          if (null == hashFunc) {
          return;
          }
          if (hashFuncs.contains(hashFunc)) {
          return;
          }
          hashFuncs.add(hashFunc);
          }
          /**
          * @see com.quickpoint.bloomfilter.BloomFilterFactory#removeHashFunction(com.quickpoint.bloomfilter.hashfunc.HashFunction)
          */
          @Override
          public void removeHashFunction(HashFunction hashFunc) {
          if (null == hashFunc) {
          return;
          }
          hashFuncs.remove(hashFunc);
          }
          /**
          * 返回所有的哈希函数。
          *
          * @return 哈希函数数组
          */
          private HashFunction[] getHashFunctions() {
          return hashFuncs.toArray(new HashFunction[0]);
          }
          }
          /**
          * quickpoint, jkltk2000 AT 126 DOT com.
          * Copyright (c) 2012 All Rights Reserved.
          * Code is licensed with BSD. See COPYRIGHT.BSD file.
          */
          package com.quickpoint.bloomfilter.hashfunc;
          /**
          * 抽象的哈希函数，是哈希函数类层次基础。
          *
          * @author kui.lijk
          * @version $Id: AbstractHashFunction.java, v 1.0 2012-5-19 kui.lijk Exp $
          */
          public abstract class AbstractHashFunction implements HashFunction {
          /** serialVersionUID. */
          private static final long serialVersionUID = -1731119065054580294L;
          /**
          * @see com.quickpoint.bloomfilter.hashfunc.HashFunction#hash(java.lang.Object)
          */
          @Override
          public int hash(Object content) {
          if (null == content) {
          return 0;
          }
          return doHash(content);
          }
          /**
          * 实际的hash计算。
          *
          * @param content 待计算的内容
          * @return hash值
          */
          protected abstract int doHash(Object content);
          }
          /**
          * quickpoint, jkltk2000 AT 126 DOT com.
          * Copyright (c) 2012 All Rights Reserved.
          * Code is licensed with BSD. See COPYRIGHT.BSD file.
          */
          package com.quickpoint.bloomfilter.hashfunc;
          /**
          * 简单的字符串哈希函数。
          *
          * @author kui.lijk
          * @version $Id: SimpleStringHashFunction.java, v 1.0 2012-5-19 kui.lijk Exp $
          */
          public class SimpleStringHashFunction extends AbstractHashFunction {
          /** serialVersionUID. */
          private static final long serialVersionUID = 174034376328516223L;
          /** 位数过滤范围 */
          private int cap;
          /** 种子数 */
          private int seed;
          /**
          * 创建简单的字符串哈希函数。
          *
          * @param cap 位数过滤范围
          * @param seed 种子数
          */
          public SimpleStringHashFunction(int cap, int seed) {
          this.cap = cap;
          this.seed = seed;
          }
          /**
          * @see com.quickpoint.bloomfilter.hashfunc.AbstractHashFunction#doHash(java.lang.Object)
          */
          @Override
          protected int doHash(Object content) {
          String str = content.toString();
          int result = 0;
          for (int len = str.length(), i = 0; i < len; i++) {
          result = seed * result + str.charAt(i);
          }
          return (cap - 1) & result;
          }
          }
          /**
          * quickpoint, jkltk2000 AT 126 DOT com.
          * Copyright (c) 2012 All Rights Reserved.
          * Code is licensed with BSD. See COPYRIGHT.BSD file.
          */
          package com.quickpoint.bloomfilter;
          import junit.framework.TestCase;
          import com.quickpoint.bloomfilter.hashfunc.SimpleStringHashFunction;
          /**
          * BloomFilterTest
          *
          * @author kui.lijk
          * @version $Id: BloomFilterTest.java, v 1.0 2012-5-19 kui.lijk Exp $
          */
          public class BloomFilterTest extends TestCase {
          private static final int DEFAULT_SIZE = 1 << 25;
          private BloomFilter filter;
          protected void setUp() throws Exception {
          super.setUp();
          BloomFilterFactory factory = new DefaultBloomFilterFactory();
          int seeds[] = {5, 7, 11, 13, 31, 37};
          for(int i = 0, len = seeds.length; i < len; i++) {
          factory.addHashFunction(new SimpleStringHashFunction(DEFAULT_SIZE, seeds[i]));
          }
          filter = factory.createFilter(DEFAULT_SIZE);
          }
          public void test_add() {
          String str = "quickpoint";
          filter.add(str);
          assertTrue(filter.contains(str));
          }
          public void test_not_contain() {
          String str = "quickpoint";
          filter.add(str);
          assertFalse(filter.contains("QUICKPOINT"));
          }
          public void test_size() {
          String str = "any";
          filter.add(str);
          assertTrue(filter.contains(str));
          assertEquals(filter.count(), 1);
          }
          }
          [@more@]

          来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/755041/viewspace-1058280/ ，如需转载，请注明出处，否则将追究法律责任。

          0
          0
          上一篇： ubuntu7.0.4 setup via harddisk
          下一篇： 没有了~
          请登录后发表评论 登录
          全部评论
          quickpoint

          注册时间：2008-08-31

          • 博文量
            3
          • 访问量
            4740

          最新文章

          支持我们 作者招募 用户协议 FAQ Contact Us

          北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

          广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

          违法和不良信息举报电话:18101376593