你有任何简单的哈希函数，取前三个字母吗？

Question

我在

cs50

拼写器工作。 这是我的哈希函数。效果很好。但我认为这并不是很好，因为有很多

if

的情况。 我尝试为前两个字母带有撇号的每个单词制作一个不同的表格（例如，A'，B'，C'）。

所以我用了桶（26 x 26 x 26）+ 26 = 17602；

unsigned int hash(const char *word)
{
    /*
        this is HASHING algorithms in which we return value with checking first three letter
        make sure every word set to lowercase so we can easily convert as integer value or alphabetical index
        and also set every first element before first letter to be a place for every apostrophe that comes at second word

        [A'=0] [Aaa=1] [Aab=2] ... [Aay=25] [Aaz=26] ... [B'=677] [Baa=678] --- base 676 number
                n = ( 677*first(word ) 26*second(word) + third(word) ) + 1;
    */

    int hash_value = 0;

    if(strlen(word) <= 1)                                       // if there's only one word calculate that word, store to element after apostrophe
    {
        hash_value = ((677 * (tolower(word[0]) - 97)) + 1);
        return hash_value;
    }
    else if(!isalpha(word[1]))                                  // if second word contain apostrophe just calucalte first word
    {
        hash_value = (677 * (tolower(word[0]) - 97));
        return hash_value;
    }
    else if(strlen(word) <= 2)                                  // if there's two word calculate that two word, store to element after apostrophe
    {
        hash_value = ((677 * (tolower(word[0]) - 97)) + (27 * (tolower(word[1]) - 97))) + 1;
        return hash_value;
    }
    else if(!isalpha(word[2]))                                  // if third word contain apostrophe just calucalte first and two word
    {
        hash_value = ((677 * (tolower(word[0]) - 97)) + (27 * (tolower(word[1]) - 97))) + 1;
        return hash_value;
    }
    else
    {
        hash_value = ((677 * (tolower(word[0]) - 97)) + (27 * (tolower(word[1]) - 97)) + (tolower(word[2]) - 97)) + 1;
        return hash_value;
    }
}

实际上效果很好。

./speller texts/lalaland.txt
WORDS MISSPELLED:     955
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756
TIME IN load:         0.02
TIME IN check:        0.02
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.05

我只是不喜欢它，因为我使用了很多

ELSE..IF

条件。 所以也许你想帮助我编写更好的代码（取前三个字母）。

Answer 1

在某些方面，您正在使用

for

语句实现

if

循环。像这样的想法

int hash = 0;
for (char *current = word; *current != '\0'; current++) {
    if (current == &word[2]) break;
    hash += hash(*current);
}

可能允许您避免使用 if 语句，因为现在索引结束处理在循环中重复。

Answer 2

我不知道我是否理解这个哈希的逻辑，但是：

如果参数不是大写字母，
1. tolower 返回相同的字符。无需检查是否是alpha

unsigned int hash1(const char *word)
{

    unsigned int result;

    result = (!!word[0]) * (677 * (tolower(word[0]) - 97));
    result += (word[0] && word[1]) * (27 * (tolower(word[1]) - 97));
    result += (word[0] && word[1] && word[2]) * (tolower(word[2]) - 97) + 1;

    return result;
}

Answer 3

简单地测试

isalpha()

并利用

isalpha(0)

是假的。
最多只有 3 个

char

，几个

if()

就足够了。

_Static_assert(isalpha(0) == 0, "isalpha(0) unexpectedly true");

unsigned int hashf(const char *word) {
  // best to use unsigned char access for tolower() to avoid UB.
  const unsigned char *uword = word;

  unsigned hash = 677u * (tolower(uword[0]) - 'a') + 1;
  if (isalpha(uword[0]) && isalpha(uword[1])) {
    hash += 27u * (tolower(uword[1]) - 'a');
    if (isalpha(uword[2])) hash += tolower(uword[2]) - 'a';
  }
  return hash;  // see below
}

---

简化的可能性：不需要

- 97

或

- 'a'

。我们正在创建一个 hash，但需要最后的模数。

  #define BUCKET_N 17602u
  return hash % BUCKET_N;

IAC，最终对存储桶大小进行取模，从而实现稳健的哈希。考虑一下OP的

hash("~")

。 OP 的代码假设字符值 - 97 在 0 到 25 的范围内，但是当字符为

á

时会发生什么？注意外部的字符值

[0  CHAR_MAX]

。

Answer 4

这是我写的一个 for 循环，它基本上和你的做同样的事情。通过更改 for 循环中的 3，当然还可以更新存储桶大小，可以很容易地添加要散列的字母数量，最多可达 4、5 等。

// Hashes word to a number
unsigned int hash(const char *word)
{
    // Get word length
    int word_len = strlen(word);
    int hash_code = 0;

    // Numbers for multiplying via indexing in a for loop
    int multiplier = 1;

    // Loop over letters in the word
    for (int i = 0; i < word_len && i < 3; i++)
    {
        if (!isalpha(word[i]))
            return hash_code;

        hash_code += (tolower(word[i]) - 'a') * multiplier;

        if (word_len == 1)
            return hash_code;

        multiplier *= 26;
    }

    return hash_code + 1;
}

这是输出：