哈希函数

哈希函数（散列函数，Hash Function）是一种从任何数据中创建数字指纹的方法，如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。

常用构造方法

直接定址法：hash(key) = a*key + b
折叠法：取数据的某部分进行折叠计算： 12536798 ——> 1253 + 6798
平方取中：类似随机数产生的算法，取中间一部分作为地址
除数取余法：hash(key) = key mod p（p一般取质素或者不包含小于20质因数的合数）
随机数法：hash(key) = rand(key) key作为随机数的种子。（1-4方法都可以归入这类。因为平方取中和取余是常见随机数算法）
根据数据特征分析
综合法

BloomFilter

BloomFilter（布隆过滤器）是一种多哈希映射的快速查找算法，一般用来快速判断一个对象是否属于某个集合，例如最常用的网络爬虫中的地址去重策略。

将一个对象放入集合时，BloomFilter的多个独立哈希函数把同一对象映射到不同的Bit位，并将这些比特位置位；判断对象是否属于集合时，查找哈希函数映射到的bit位是否已经被置位过，如果没有被置位过，那么该元素一定不属于集合。但是，如果映射到的位全部都被置位过，该元素有可能不属于集合（false positive）。如果m表示bit个数，n表示已经放入BloomFilter的元素个数，k表示哈希函数的个数，那么元素被误判为属于集合的概率为公式一：
$误判概率$
当k=ln2*(m/n)时，可以使误差概率最小，此时误差为公式二：
$此处输入图片的描述$

BloomFilter的实现

该实现中bit位个数m = 1 << 30(1073741824约10亿)，独立Hash函数的个数K为9，假设已插入的字符串个数n = 10000000（1千万）。则根据公式一，再次插入一个新字符串时，误判为字符串已存在的概率为1.4041653253261077E-10（10亿分之1.4）。根据公式二，此时最佳的K值为74.42611179548929。

class BloomFilter implements Serializable {
    private final int BITS_NUM = 1 << 30;
    private final int K_NUM = 9;
    private BitSet bits;
    private int[] seeds;
    private HashFunc[] hashs;

    private static final BloomFilter bloomFilter = new BloomFilter();

    private BloomFilter() {
        bits = new BitSet(BITS_NUM);
        seeds = new int[]{3, 5, 7, 11, 13, 17, 19, 23, 29};
        hashs = new HashFunc[K_NUM];
        for (int i = 0; i < K_NUM; ++i)
            hashs[i] = new HashFunc(seeds[i], BITS_NUM);
    }

    public static BloomFilter getBloomFilter() {
        return bloomFilter;
    }

    public boolean isIn(String s) {
        for(HashFunc hashFunc : hashs)
            if(!bits.get(hashFunc.hash(s)))
                return false;
        return true;
    }

    public void insert(String s) {
        System.out.println(bits);
        for(HashFunc hashFunc : hashs)
            bits.set(hashFunc.hash(s));
        System.out.println(bits);
    }
}

哈希函数的实现选择BKDR Hash模板，选择了3, 5, 7, 11, 13, 17, 19, 23, 29这9个质数作为BKDR Hash的种子。

 public class HashFunc {
    private int seed;
    private int size;

    public HashFunc(int seed, int size) {
        this.seed = seed;
        this.size = size;
    }

    public int hash(String s) {
        int result = 0;
        for (char c : s.toCharArray())
            result = seed * result + c;
        return (size - 1) & result;
    }
}

参考资料

Hash原理及常用hash函数：http://gubaojian.blog.163.com/blog/static/1661799082010103126182/
各种字符串哈希函数比较：https://www.byvoid.com/blog/string-hash-compare
BloomFilter–大规模数据处理利器(解决空查问题):http://www.dbafree.net/?p=36
BloomFilter:https://en.wikipedia.org/wiki/Bloom_filter
从头到尾彻底解析Hash表算法：http://blog.csdn.net/v_JULY_v/article/details/6256463#comments
哈希表之bkdrhash算法解析及扩展：http://blog.csdn.net/wanglx_/article/details/40400693

Noob

常见Hash函数与BloomFilter

哈希函数

常用构造方法

BloomFilter

BloomFilter的实现

参考资料