如何在算法上分配密钥空间？

Question

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

我想分割一个给定的密钥空间（比如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; 
} 

Answer 1

任何特定分区中的最高密钥显然将由所有1位组成。如果您的密钥的密钥位数为n，而您的分区ID为m位，则您只需运行一个m位计数器，并将其与n连接在一起。
为了说明，假设一个8位密钥空间与用于分区（所以num_partitions = 2^2 = 4高2位，和下部6的钥匙中的每个分区中的最高关键将是这四个：

00 111111 
01 111111 
10 111111 
11 111111 

在为了生成它们，所有你需要做的是：

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是二的幂

当然，对于关键的空间一样大，你也不会简单如上所述，因为你不能将所有东西都放入单个变量中。尽管如此，原则仍然是一样的。只要你的num_partitions足够小，你可以将计数器放入一个普通的int变量中，将它复制到高位中，然后用余数填充其余部分。

Answer 2

我不知道我理解你的问题的情况下 - 我没研究一致散列。

---

这个问题几乎相当于“我如何排序而无需排序”。

另一种方法可能是这样：

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

这是线性时间。然而，它不需要关键空间的先验知识，除了有下一个顺序。

如果您正在对[0,2^128] - > {values}进行分区，例如，您正在执行一些分布式计算或您有什么，那么您的运气会好得多，因为整数结构良好。

我会建议在结构中有4个32位整数并编写你自己的bigint例程来解决你需要解决的问题。

如果你有自由而不是使用C++，Common Lisp内置bigint。我发现这很方便。

---

如果有表示的钥匙......

然而，寻求与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. 
} 

Answer 3

根据tzaman的回答，这里是我的解决方案。它允许多达255个分区（尽管这可能会改变）。它不需要2个num_partitions的功能......它只会让最后一个分区占用剩下的部分。

让我知道，如果你看到任何错误... :)

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; 
}