2

我有一组由 uint16_t 唯一标识的结构。这些结构永远不会超过 256 个（由于我不会进入的原因，必须使用 uint16_t 来识别结构）。

我想通过指针数组存储这些结构。由于不会有超过 256 个结构，我想静态分配一个大小为 256 的结构指针数组。不过，为此，我需要一个函数来将 uint16_t 唯一地映射到 uint8_t。

鉴于我将在运行时知道所有键（尽管在运行前我不会知道），是否存在一种算法，它通常会给我一个唯一的映射（即完美的哈希）？

需要注意的是，我使用的系统有 16 位地址。因此，出于效率原因，我不想使用任何大于 uint16_t 的类型。

4

2 回答 2

2

鉴于我将在运行时知道所有键（尽管在运行前我不会知道），是否存在一种算法，它通常会给我一个唯一的映射（即完美的哈希）？

鉴于您要映射多达 256 个（16 位）值，原则上您可以使用许多映射。但是，如果要支持的键不相关，则任何计算映射的算法都需要所有 256 个键或它们的函数作为参数。例如，在评论中，讨论了 256次多项式的概念，参数将是多项式的系数。

现在考虑由于映射需要 256 个参数，它也会以某种方式使用所有这些参数。那么，如何才能有效地计算具有这些一般特征的东西呢？

我看到的不相关键的最佳解决方案是将所有键放入一个数组中，对它们进行排序，然后使用排序后的数组中每个键的索引作为所需的哈希值。（因此，在这种情况下，参数本身就是键。）您可以通过二进制搜索相当有效地计算这些索引。假设您在程序期间存储排序后的数组，我认为您无法比这更有效地进行任何此类计算，而且它足够简单，您可以确信它的正确性。

这假设您在需要对其中任何一个进行散列之前知道所有密钥。如果不是这种情况，那么至少您可以使用未排序的数组和线性搜索（尽管也可能存在中间方法）。线性搜索可能看起来不是特别有效，但平均而言，它不会比涉及 256 个参数的纯算术计算差。

于 2018-06-20T21:33:46.433 回答
-1

我最终使用第一个拟合算法将 16 位值唯一地映射到 8 位值（在不超过 256 个 16 位值的假设下工作）。下面是一个非常简短的示例，我编写了代码来测试它。虽然映射函数相当昂贵（下面称为创建映射），但 get_value 函数是恒定的。因此，一旦建立映射，计算散列应该相当快（在我的示例中由余数 + 偏移 [除数] 给出）并获得相关值。

uint16_t keys[256];
uint16_t actual_mapping[256];
uint8_t offset[256];
uint8_t num_keys = 0;

void 
create_mapping()
{
    uint8_t mapping_matrix[num_keys][2];

    uint8_t index;
    uint8_t test_index;
    for(index = 0; index < num_keys; index++)
    {
        mapping_matrix[index][0] = (uint8_t) (keys[index] / 256);
        mapping_matrix[index][1] = keys[index] % 256;
    }

    for(index = 0; index < num_keys - 1; index++)
    {
        uint8_t hash_not_found = 1;
        while(hash_not_found)
        {
            hash_not_found = 0;
            for(test_index = index + 1; test_index < num_keys; test_index++)
            {
                if(mapping_matrix[index][0] != mapping_matrix[test_index][0])
                {
                    if((uint8_t) (mapping_matrix[index][1] + offset[mapping_matrix[index][0]]) == (uint8_t) (mapping_matrix[test_index][1] + offset[mapping_matrix[test_index][0]]))
                    {
                        hash_not_found = 1;
                        offset[mapping_matrix[index][0]]++;
                        break;
                    }
                }
            }
        }

        actual_mapping[(uint8_t) (mapping_matrix[index][1] + offset[mapping_matrix[index][0]])] = keys[index];
    }
}

uint16_t
get_value(uint16_t value)
{
    uint8_t divisor = (uint8_t) (value / 256);
    uint8_t remainder = value % 256;
    return actual_mapping[(uint8_t) (remainder + offset[divisor])];
}

int main(int argc, char** argv) {

    keys[0] = 0;
    keys[1] = 256;
    keys[2] = 4;
    keys[3] = 13000;
    keys[4] = 14000;
    keys[5] = 15000;
    keys[6] = 16000;
    keys[7] = 3500;
    keys[8] = 69;
    keys[9] = 15;
    keys[10] = 16;
    keys[11] = 789;
    keys[12] = 12001;

    num_keys = 13;

    create_mapping();

    uint8_t index;
    for(index = 0; index < num_keys; index++)
    {
        printf("%hu\n", get_value(keys[index]));
    }  


}
于 2018-06-20T22:01:53.143 回答