代码之家 › 专栏 › 技术社区 › BenAlabaster

如何用算法划分一个键空间?

data-partitioning hash

0

BenAlabaster · 技术社区 · 14 年前

这与一致的散列有关,虽然我在概念上理解了我需要做什么,但我很难将其转换为代码。

我试图将给定的键空间(比如128位)划分为大小相等的分区。我想要每个分区的上限(最高键)。

基本上,我要如何完成这个?

#define KEYSPACE_BYTE_SIZE  16
#define KEYSPACE_BIT_SIZE   (KEYSPACE_BYTE_SIZE * 8)

typedef struct _key
{ 
    char byte[KEYSPACE_BYTE_SIZE];
} key;

key * partition_keyspace( int num_partitions )
{
    key * partitions = malloc( sizeof(key) * num_partitions );

    // ...

}

编辑:

我想另一种说法是:

for (i = 0; i < num_partitions; i++)
{
    partitions[i] = ((2 ^ KEYSPACE_BIT_SIZE) / num_partitions) * i;
}

当然问题是2^128是一个非常数字很大,不能包含在C中用于计算数学的任何单个整数变量中(因此是char[16]结构)。

我真的不想用大量的图书馆(或任何图书馆)来做这个。

编辑:

不过,事实上,我要找的数字是:

for (i = 0; i < num_partitions; i++)
{
    partitions[i] = (((2 ^ KEYSPACE_BIT_SIZE) / num_partitions) * (i + 1)) - 1;
}

3 回复 | 直到 7 年前

1

2

tzaman 14 年前

任何特定分区中的最高键显然都由 1 -比特。如果你有更低的 n 你的钥匙和上面的 m 分区ID的位,那么您所需要做的就是运行一个 米 -位计数器,并将其与 n 那些。
举例来说,假设一个8位的键空间,上面2位用于分区(所以 num_partitions = 2^2 = 4 ,键的下6。每个分区中的最高键是这四个:

为了生成它们,您需要做的就是:

for (int i = 0; i < num_partitions; i++)
    highest_key = (i << 6) | 0x3f // where 6 is key_bits and 0x3f is six ones.

当然,这是假设 num_partitions 是二的力量。

当然,对于像您这样大的密钥空间,它不会像上面那样简单,因为您不能将所有内容都放入一个变量中。不过,原则是一样的。只要你 数字分割 足够小,你可以把柜台装到普通的 int 变量,将其复制到高位,然后用一个值填充其余的值是微不足道的。

2

0

Paul Nathan 14 年前

我不确定我理解你问题的背景-我没有研究一致的散列。

这个问题几乎等于,“我怎样才能在没有排序的情况下进行排序”。

另一种方法可能是这样做:

iter = seed() #initialize to the bottom of the hash keys
for(i = 0 to partitionbound)
{
   iter = nextIter(iter);
}

这是线性时间。但是,它不需要对关键空间有先验的了解,除非有一些nextiter遵循的顺序。

如果您正在对[0,2^128]->值进行分区,例如,您正在进行一些分布式计算或其他操作,那么您的运气会更好,因为整数结构良好。

我建议有一个稍微愚蠢的想法,在一个结构中有4个32位的int,然后编写自己的bigint例程来解决需要解决的问题。

如果你有自由不使用C++,普通LISP内置了BIGNITS。我觉得这很方便。

如果你有可代表的钥匙…

但是,当在一些空间A中使用n个元素查找一些大小相等的k分区时,我会这样处理问题:

if( n % k)
{
   return "not equal-sized partition!"
}
//could be forking/threading, whatever.
for(int i = 0; i < n; i+=k)
{
   process(i, i+k-1);
}


process(bottom, top)
{
   sort(a[bottom], a[top]);
   return a[top]; //you'll have to figure out where to dump the results.
}

3

0

BenAlabaster 14 年前

根据Tzaman的回答,这是我的解决方案。它最多允许255个分区(尽管可以更改)。它不需要2个num_分区的幂…它只会让最后一个分区占据剩下的部分。

如果你看到虫子,告诉我…:)

key * partition_keyspace( unsigned int num_partitions )
{
    assert( num_partitions > 0 );
    assert( num_partitions < 0xFF );

    key * partitions = (key *) malloc( sizeof(key) * num_partitions );

    // fill every bit
    memset( partitions, 0xFF, sizeof(key) * num_partitions );

    // calculate how many bits of the top byte needs to be filled by 1's
    unsigned char fill_bits = 0;
    while (num_partitions > (1 << fill_bits)) fill_bits++;
    fill_bits = 8 - fill_bits;

    // fill the top byte with the base number of 1's
    unsigned char fill_part = 0;
    for (unsigned int i = 0; i < fill_bits; i++) fill_part |= 1 << i;

    // last partition takes up whatever remains, so don't process it (hence the -1)
    for (unsigned char i = 0; i < num_partitions - 1; i++)
    {
        partitions[i].byte[0] = fill_part | (i << fill_bits);
    }

    return partitions;
}