0

我正在研究一个哈希函数，它通过将该字符串映射到一个键来为给定的字符串提供一个“ID”。我需要使用的算法描述如下：

  • 给定字符串NOTE，我们为每个字母分配一个值，例如：

    N = 14, O =15, T = 20, E = 5

  • 然后我们相乘和相加：

    14 * 32^3 + 15 * 32^2 + 20 * 32^1 + 5 * 32^0

  • 通过分解这个表达式，我们得到：

    ((14 * 32 + 15) * 32 + 20) * 32 + 5

  • 但是这个值可能会变得太大，所以我们在每组括号之后使用 mod 除法：

    ((14 * 32 + 15)%tableSize *32 + 20)%tableSize * 32 + 5

我怎样才能创建一个算法来完成这个？我曾尝试这样做，但我的实施效率极低。我的教授说它不应该超过7行。任何人都可以就如何有效地实现上述算法提供建议吗？

如果有人关心，我的算法是：

int HashDictionary::getKey(string word) const{
    int wordLength = word.length();
    int* values = new int[wordLength];
    for ( int i = 0; i < wordLength; i++ ) {
        values[i] = int(word[i]);
    }

    int productSoFar = 0;
    for(int i = 0; i < wordLength;i++){
        productSoFar *= 32;

        if(i == 0){
            productSoFar = values[i] * 32;
            productSoFar = productSoFar + values[i+1];
            productSoFar %= tableSize;
            i++;
        }
        else{
            productSoFar += values[i];
            productSoFar %= tableSize;
        }

    }
    delete [] values;
    return productSoFar;
}
4

2 回答 2

1

你不应该需要 2 个循环；因为第一个所做的唯一事情是将字符转换为整数，您可以根据需要翻译每个字符，并完全避免使用 values 数组。这应该加快速度并减少您的行数。

于 2012-05-01T01:35:40.727 回答
0

尝试这个：

int HashDictionary::getKey(string word) const{
    int wordLength = word.length();
    int* values = new int[wordLength];
    values[0] = int(word[0]);
    values[1] = int(word[1]);

    int productSoFar = 0;
    productSoFar = values[0] * 32;
    productSoFar = productSoFar + values[1];
    productSoFar %= tableSize;

    for(int i = 1; i < wordLength;i++){
        productSoFar *= 32;
        productSoFar += values[i];
        productSoFar %= tableSize;
        values[i] = int(word[i]);
        }
    delete [] values;
    return productSoFar;
}
于 2012-05-01T01:41:57.410 回答