如何在算法上分配密鑰空間？

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