Java中成对独立的哈希函数

问题描述

我正在寻找一种使用(通用)系列成对独立哈希的快速简便的方法功能在我的Java项目中.

I'm looking for a quick and easy way to use a (universal) family of pairwise independent hash functions in my Java projects.

理想情况下，我会有一些对象UniversalFamily(代表Family)，该对象将使用散列整数的方法hash()向我返回对象.

Ideally, I would have some object UniversalFamily (representing the Family) which would return me objects with a method hash() which hashes integers.

示例用法:

// use this object to generate pairwise independent hash functions
UniversalFamily family = new UniversalFamily();

// these objects represent the pairwise independent hash functions
HashF hashF1 = fam.getHashFunction();
HashF hashF2 = fam.getHashFunction();
// ...

/* here the hash functions are being used to hash the integers 1, 2 and 
   1337, the return values (not stored) are the results of the 
   corresponding hash functions. */
hashF1.hash(1);
hashF1.hash(2);
hashF2.hash(1337);
// ...

在我开始修补之前，已经有类似的东西了吗?

Before I start tinkering around, is there anything like this already available?

推荐答案

使用类似这样的内容:

/* Used to generate and encapsulate pairwise independent hash functions.
See see https://people.csail.mit.edu/ronitt/COURSE/S12/handouts/lec5.pdf , claim 5 for more information.
 */
private static class HashF {

    private final int a;
    private final int b;
    private final int p = 1610612741; // prime

    HashF(int a, int b) {
        Random rand = new Random();

        this.a = rand.nextInt(p);
        this.b = rand.nextInt(p);
    }

    // hashes integers
    public int hash(int x) {
        return (a*x + b) % p;
    }

}

这篇关于Java中成对独立的哈希函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！